面向复杂超图数据分析的分布式迭代处理技术研究

In the era of big data, the data scale increases dramatically, and the relationships among data become more and more complex. Compared to the common graph model, the hypergraph model can effectively represent the complex multivariate relationships among objects to avoid the information loss during the modeling process, so that the hypergraph data analysis has been more extensively applied. Considering the complexity of hypergraph structure and the diversity of the hypergraph analysis tasks, distributed and parallel iterative processing tasks over massive hypergarphs face three major challenges: combination explosion of hypergraph data, heterogeneous polymorphism of hypergraph structure and non-linear convergence of hypergraph computation. The existing management and analysis systems designed for common graph data or hypergraph data fail to effectively solve these issues, which leads to the inefficient execution when handling large-scale hypergraph data. And thus with the goal of high efficiency and adaptability, this proposal aims to conduct in-depth studies into the key techniques involving data partition, iterative processing and message management for complex hypergraph data analysis. This research is very significant theoretically and practically in term of exploiting new distributed graph data management schemes, promoting large-scale hypergraph processing applications and developing big data analysis techniques and industries of China.

在大数据时代，数据量急剧增加，数据之间的关系也越来越复杂。与普通的图模型相比，超图模型可以有效表示对象间复杂的多元关系，避免了建模过程中信息的损失，因此超图分析任务的应用越来越广泛。超图数据结构复杂且超图分析任务种类多样，使得面向超图的分布式并行迭代处理任务面临三大挑战：超图数据的组合爆炸、超图结构的异质多态以及超图计算的非线性收敛。现有的普通图数据和超图数据的管理和分析系统不能直接解决以上挑战，在处理大规模超图数据时效率很低。因此本项目计划以高效性和自适应性为目标，拟针对超图数据的高效划分、迭代处理和消息管理等关键技术展开深入研究。该研究深入拓展了现有的分布式超图管理技术，推动了超图领域的应用，对于发展我国大数据管理和分析的自主技术和产业，具有重要的理论意义和实际价值。

在大数据时代，数据量急剧增加，数据之间的关系也越来越复杂。与普通的图模型相比，超图等异构图模型可以有效表示对象间复杂的多元关系，避免了建模过程中信息的损失，因此相关的分析应用越来越广泛。超图等异构图数据结构复杂且分析任务种类多样，使得分布式并行迭代处理任务面临三大挑战：数据的组合爆炸、结构异质多态以及计算的非线性收敛。现有的普通图数据和超图数据的管理和分析系统不能直接解决以上挑战，在处理大规模异构数据时效率较低。本项目以高效性和自适应性为目标，在面向超图等复杂异构图数据的轻量划分、迭代计算、消息管理和面向具体应用的算法优化等方面展开了深入的研究，提出一系列分布式迭代处理创新性解决方案，主要包括基于目标顶点敏感哈希的在线划分、基于超边连通图的超图迭代处理、基于相交图模型的超图迭代计算、自适应复杂图迭代混合消息管理、超图关联矩阵和消息向量通信优化，并针对超图分类和聚类等多个具体上层任务的算法进行优化。课题解决了复杂图数据计算的多态迭代的非线性收敛计算模型问题和跨层消息的非齐次组合聚散机制问题等重要科学问题，显著降低了超图分析任务的I/O、通信和计算开销，有效改善了异构图处理框架的可扩展性和计算平台的性价比。课题组在国内外知名刊物和会议上发表了16篇学术论文（其中SCI收录7篇），并申请发明专利5项，培养硕士毕业生8名。该研究在拓展现有分布式大图数据管理技术、推动超图领域应用、以及发展我国大数据分析自主技术和产业方面，都具有重要的理论意义和实际价值。