基于系统层次结构的大图并行处理框架研究

As the development of social networks, processing, analyzing and mining huge real-world graph is active. Graphs are used to express the relationships among objects, and thus have great value. As the scale and dependencies of graph data are increasing, designing efficient systems and algorithms for large-scale graph processing is challenging. This study proposed a new parallel framework for large-scale graph processing, which optimizes graph partitioning algorithms towards hierarchical structures of distributed systems. This proposal analyzes the partitioning cost on each system structure level, and builds a cost model. Efficient partitioning methods are proposed which exploits the architecture features of each level. A unified large-scale graph partitioning mechanism is proposed together with performance optimization techniques, including data placement, data replication, node communication, I/O and task scheduling techniques. A self-adaptive and self-optimization mechanism is also proposed towards natural graphs and streaming graphs. Open source framework and prototypes are proposed, and evaluations are made on several application domains.

随着社交网络的兴起，基于大规模图结构上的计算、分析与挖掘，成为具有重要价值的研究热点。数据的持续增加和关联关系的日益复杂，对并行系统结构设计和图划分算法的设计都提出了挑战。本项目拟针对大规模图并行处理中高性能、高效率和易编程的需求，通过将大图划分算法与系统层次化结构有机结合，提出一种新颖的大图处理框架。该框架利用分布式系统中各层级的结构特性，建立划分代价分析模型，设计适应各自层级需求的高效划分方法。在此基础上，建立统一的层次化大图划分框架。为了进一步提升效率，通过分析大图数据存储与访问的模式，优化数据分布、数据复制、节点通信、I/O访问和任务调度等机制。针对自然图及动态图等多种类型图结构，提出自适应、自优化的处理机制。最后，构建开源框架和原型系统，并在社交网络及电信网络等应用领域中进行评估验证。

随着社交网络的兴起，基于大规模图结构上的计算、分析与挖掘，成为具有重要理论意义和应用价值的研究热点。本项目面向大规模图结构数据，研究如何高效处理，检索、分析与应用。研究主要分为四个方面：（1）基于并行体系结构的大图划分与子图检索研究，包括在并行节点上的大图划分方法，子图增强技术、查询图分解算法、子图通信算法、顶点索引构建方法以及任务划分和同步机制等。基于该研究，第一次实现了在以顶点为中心的图结算模式下的子图检索和子图同构算法，八节点集群上可以将子图同构处理规模扩展到几十万甚至百万级；（2）基于社交网络拓扑结构的信息传播算法，考虑消息间的相互作用和网络拓扑结构，基于进化博弈论和贝叶斯模型，分别提出信息传播预测算法，为促进或抑制信息传播提供了依据；（3）基于顶点影响力的社团发现算法，我们分析了高度数节点在大规模网络社团结构中的特别作用，基于此提出了基于顶点可变影响力的社团划分算法。该算法可以根据实际应用场景和需求，调整划分的方案；（4）并行体系结构的存储性能优化。本项目还对并行系统地城架构开展研究，力图提升存储系统的性能和效率。针对多任务并行存储空间分配的问题，提出了一种面向伪LRU算法的cache容量划分机制。针对新型相变内存和固态硬盘写延迟高的问题，提出了非对称的读写替换算法。所提算法都具有良好的性能和较低的存储和实现代价。本项目执行过程中已发表8篇论文，其中4篇SCI期刊论文，4篇EI会议论文，包括CCF A类会议论文。申请专利一项，出版专著一部，基本达到了立项之初的要求和目的。