分布式内存环境下的大图数据管理技术研究

Big data has appeared in each area of today's industries and businesses, and has become an important factor of production. In all areas, the large data usually has relations, which results in big graphs, such as large social networks, semantic Web network, biological information networks. In this project, we propose to use distributed memories to manage big graphs by analyzing the characteristics of graph data, the nature of graph algorithms, as well as the disadvantages of current management technologies on big graphs. In this project, we focus on (1) big graph storage sensitive to memory, i.e., physical storage model, data partition and placement, data compression; (2) distributed and parallel query processing and optimization, i.e., cohesion subgraph queries, keywords search on graph and graph pattern matching; (3) query language derived from SQL for extracting graph structures and (4) execution guarantee on the system, i.e., scheduling operations and fault-tolerance. Related research results on big graphs data will provide new solutions to further broaden the applications of big graph data, and have important theoretical significances and practical values.

大数据，已经渗透到当今每一个行业和业务职能领域，成为重要的生产因素。在各领域中，大数据通常具有关联性，从而产生了大图数据，例如大型社交网络、语义Web 网络、生物信息网络等。本项目通过对大图数据特点的分析、图算法运作本质的探究、迫切的现实应用需求分析，以及对当前大图数据管理技术不足的总结，提出用分布式内存系统来管理大图数据。重点研究：（1）内存感知的大图数据存储，包括图数据的物理存储模型、图数据的划分和布局、感知压缩处理；（2）大图数据的分布并行查询处理与优化，包括凝聚子图查询、关键字图查询和图模式匹配查询；（3）扩展SQL语句的图拓扑提取查询语言；（4）分布式内存系统的执行保证，包括执行任务的调度和系统的容错恢复。相关研究成果将为大图数据管理提供新的解决方案，进一步拓宽大图数据的应用范围，具有重要的理论意义与实际应用价值。

本项目的执行时间是2016.1——2019.12，这期间项目主要研究了图数据库理论与系统的各个方面，现总结如下：. 图是计算机科学中最常用的一类抽象数据结构，在结构和语义方面比线型表和树更为复杂，更具有一般性表示能力。虽然图的应用和处理技术已经发展了很长时间。理论也日趋完善，但是随着信息化时代的到来，各种信息爆炸式增长，导致图的规模日益增大，如何对大图数据进行高效处理，成为一个新的挑战。. 1.在大图存储研究方面，提出了一种新颖的缓存机制GraphCache，GCache由离线阶段和在线阶段组成，它们继承了在线和离线缓存算法的优点；研究了Web级图数据的分布式存储技术，用来进行再Web图数据上的快速关键字查询。. 2.在大图分割方向提出了一种不确定图分割算法，用以解决不确定图的快速查询问题；研究了一种基于社会影响力的道路网KNN查询的图分割算法；研究了在分布式环境下的关键字查询技术，基于此在Web大图数据的基础上对图数据进行初始随机分区后对其进行重组，以使基于签名的技术更加有效。. 3.大图分布式查询方面，提出了一种可用于分布式计算不确定图可达性查询策略DistR，用以快速解决不确定图可达性查询问题；在图分割技术的基础上，提出了一种用以解决结合社会影响力的道路网KNN查询问题的高效索引；研究了在分布式环境中部署的Web规模图的关键字搜索，并提出了一种基于签名的搜索算法。. 4. 本项目实施过程中，项目组已在TPDS、VLDB Journal、IEEE TKDE、VLDB、ICDE、KDD等国际权威期刊和国际会议上发表论文31篇，其中SCI期刊发表论文13篇，其中CCF A类论文13篇。培养毕业研究生12名，一人获得东北大学优秀硕士论文，培养毕业博士研究生4名，一人获得2019年CCF优博提名奖。