图模型大数据的分布式查询处理关键技术研究

As graph-modeled big data are widely used in various fields, the demand for highly efficient graph query processing is urgently called for. Since the inherent nature of the high computational complexity of graph queries, traditional methods are generally unable to cope with query processing tasks on big graph data. In this project, we propose to take “divide and conquer” and “trade space for time” scientific thoughts as strategies, doing the research on key technologies of distributed query processing oriented to graph-modeled big data. We will propose the partition, storage, and indexing schemes for big graph data in the distributed environment; propose distributed graph query processing algorithms for conjunctive query, regular path query, CRPQ query, and ECRPQ query based on the “partial evaluation” approach, which will use parallelized “divide and conquer + collaboration ” strategy and graph structural indexing based “holistic matching” strategy to realise the fast evaluation of distributed graph queries; propose the distributed graph query optimization cost model, based on which we study the distributed graph query optimization scheme that consists of the optimization of join order, runtime optimization, and approximate query and ranking; design the benchmark for distributed graph query, based on which we conduct extensive experimental evaluation for the propsosed methods. In this project, we will develop a graph database prototype system that will be equipped with the highly efficient distributed graph query capability for graph-modeled big data.

图模型大数据在各领域的广泛应用对高效率图查询处理提出迫切需求。由于图查询固有的高计算复杂度特性，传统方法普遍无法应对大图数据上的查询处理任务。本项目提出以“分而治之”和“空间换时间”的科学思想为策略，研究面向图模型大数据的分布式查询处理关键技术。具体包括：提出分布式环境下大图数据的划分、存储与索引方案；基于“部分求值”方法，提出合取查询、正则路径查询、CRPQ查询和ECRPQ查询的分布式图查询处理算法，利用并行化的“分治+协同”策略和基于图结构索引的“整体匹配”策略，实现分布式图查询的快速求值；提出分布式图查询优化代价模型，研究包括连接顺序优化、运行时优化和近似查询与排序在内的一揽子分布式图查询优化方案；设计分布式图查询评测基准，对所提方法进行全面的实验验证。本项目将开发面向图模型大数据的具备高效率分布式图查询功能的图数据库原型系统。

图模型大数据在各领域的广泛应用对高效率图查询处理提出迫切需求。由于图查询固有的高计算复杂度特性，传统方法普遍无法应对大图数据上的查询处理任务。本项目提出以“分而治之”和“空间换时间”的科学思想为策略，研究面向图模型大数据的分布式查询处理关键技术。.项目主要研究内容主要包括：(1) 图模型大数据的划分与存储：研究综合考虑属性图和RDF图的本质特征，定义分布式图模型，制定划分策略的最优化度量指标，提出高效的图数据分布式压缩存储方案。(2) 分布式图查询处理算法：研究分布式CQ查询处理算法、RPQ查询处理算法、CRPQ查询处理算法和ECRPQ查询处理算法。(3) 分布式图查询优化方案：研究分布式图查询处理的代价模型、最优连接顺序、运行时优化技术和近似查询方法。(4) 实验验证与原型系统：开发原型系统实现图模型大数据上的分布式查询处理方案，设计实验验证所设计算法和方案的性能效果。.项目所取得的重要成果主要包括：(1) 在图模型大数据的划分与存储方面：设计并实现了一种高效率的分布式图着色算法用于分布式图划分的重要步骤，提出了一种语义感知的RDF图划分方法，开发了本体感知的RDF图分布式存储方案，实现了RDF图和属性图的统一存储方案，实现了基于SSD存储的键值存储库底层压缩方法。(2) 在分布式图查询处理方面：提出了分布式图查询处理算法PDSM和StarMR用于高效执行大规模RDF图上的子图匹配查询，实现了基于部分求值策略的正则路径查询处理算法，同时提出了动态图上的最近邻和最短路径查询算法。(3) 在分布式图查询优化方面：提出基于代价模型的分布式正则路径查询优化方案用于减少中间结果和通信开销，开发了基于生成树的分布式子图匹配查询优化方案SP-Tree用于减少中间结果和消息传递。(4) 在实验验证与原型系统方面：开发了图模型大数据分布式存储与查询原型系统，实现了多种可视化交互式图查询语言和工具。