面向高频多态迭代计算的超大动态图自适应数据管理关键技术

With the rapid growth of the applications like social networks, queries and analysis over large-scale graph data become the hot research topic. Particularly, in the context of big data, distributed and parallel iterative processing tasks for graph data faces severe challenges in terms of very large data scale, dynamically evolving structures, high-frequency and multi-state iterations, and controllable computation precision. Based on the sufficient investigation of the exising parallel iterative processing and distributed graph data management techniques, with the goal of I/O efficent and self-adaptive optmization, the proposal aims to conduct in-depth studies on key techniques of data partition, storage and index, data analysis and approximate query. Novel solutions to incremetal, adjustable and approximate parallel iterative processing will be explored and a graph data management prototype system supporing complex iterative processing tasks will be implemented. This study is theoretically and practically significant to exploit new distributed data management schemes, to promote large graph processing applications, and to develop big data management and analysis techniques and industries of China.

随着社交网络等应用的兴起，对大规模图数据进行查询和分析成为了近年来的热点研究问题。特别的，在大数据时代，面向图数据的分布式并行迭代处理任务面临着数据规模超大、结构动态演化、迭代高频多态和计算精度可控等方面的巨大挑战。本申请在充分调研现有并行迭代处理技术和分布式图数据管理技术局限性的基础上，计划围绕I/O高效和系统自适应的优化目标，针对数据划分、存储索引、数据分析和近似查询等关键优化技术展开深入的研究，提出可增量、可调整、可近似的并行迭代处理创新性解决方案，并实现一个面向复杂迭代计算的超大动态图数据管理原型系统。该研究对于开拓新型的分布式数据管理方法，推动大图处理领域的应用，发展我国大数据管理和分析的自主技术和产业，具有重要的理论意义和实际价值。

随着社交网络、人脑网络、知识图谱等应用的兴起，对大规模图数据进行查询和分析成为了近年来的热点研究问题。随着数据量的不断增大，分布式大图数据管理和计算成为了解决大图存储能力和提升处理效率的最有潜力的研究方向之一。特别的，大图数据处理面临着数据规模超大、结构动态演化、迭代高频多态和计算精度可控等方面的巨大挑战，而现有的分布式图数据管理和计算系统缺乏针对复杂迭代处理任务全过程的深度存储管理和动态优化机制，也缺少对增量处理和近似计算的支持。基于以上分析，本申请围绕I/O高效和系统自适应的优化目标，针对数据划分、存储索引、数据分析和近似查询等关键优化技术展开了深入的研究，提出一系列可增量、可调整、可近似的并行迭代处理创新性解决方案，包括基于定向边交换模型的图划分、基于混合推拉机制的高效大图数据存储和索引、基于弹性同步并行模型的大图迭代计算、基于主成分分析的大规模高维数据近似查询等诸多关键技术，解决了结构演化驱动的增量数据管理、非齐次收敛敏感的可调处理机制和查询精度可控的近似计算模型等重要科学问题。课题组在国内外知名刊物和会议上发表了33篇学术论文（其中SCI收录12篇、多篇论文发表在SIGMOD、ICDE、TKDE、TPDS等顶级会议和刊物上），出版了大图分布式数据处理的学术专著1部，申请发明专利5项，培养毕业博士生3人（1人获得CCF优秀博士论文奖）。此外，课题组设计和实现了一个面向复杂迭代计算的超大图数据管理原型系统HGraph。比起现有系统，HGraph可将I/O效率提高几倍至几十倍，并且具备小规模集群上百GB规模图数据的快速处理能力, 显著改善了大图处理框架的可扩展性和计算平台的性价比。