混合存储和计算模式下的大图处理优化技术研究

As the graphs with billions of vertices are constantly emerging, optimization of distributed massive graph processing becomes an increasingly important problem on graph data management. Coupling computational structure and growing size pose challenges to optimization techniques. Currently the biggest problem is that existing optimization technologies will struggle to satisfy diversified demand of massive graph processing within a single pattern.In this project,we tries to propose systematic hybrid optimization techniques with tradeoff ideas in hybird pattern.This proposal mainly focuses on four key aspects, including i)hybrid storage architecture based graph data storage technologies in order to reduce network traffic; ii) hybrid storage architecture based low-latency graph data access; iii)hybrid computational model compromises the merits of synchronization and asynchronization; and iv)multi-level scheduling to accelerate convergence. Analysis in theorem and thorough experimental tests will be conducted to evaluate the performance of the proposed methods. Such research work may provide new ideas for optimizaton on massvie graph computational model with a good tradeoff between easy of use,scalablility and high-performance, and therefore have great importance.

随着数十亿顶点级别大规模图的不断涌现，分布式大图处理优化已经成为一个日益重要的研究问题。图在结构和计算上的高耦合性以及不断增长的规模给优化技术的研究带来了挑战。单一模式下的优化技术难以适应大图计算多样化的需求。本课题拟通过建立混合的存储和计算模式，并基于此利用权衡两级的优化思路，给出系统性的混合式优化技术解决方案。本项目拟从四个方面进行探索1）研究面向混合存储的图数据存储优化技术以减少数据移动和网络通信；2）研究面向混合存储的图数据访问优化技术以降低访问延迟；3）研究融合同\异步优点的新型计算模型，在保持易用性的基础上提高执行效率；4）研究多级调度优化技术以加速迭代收敛。同时，结合理论分析和完整的实验测试来检测新模型和现有模型的差异性，相关研究成果将为易用、可扩展、高性能平衡的大图处理的进一步研究与应用提供新的解决思路和技术支撑，因而具有重要的理论和实践意义。

随着数十亿顶点级别大规模图的不断涌现，分布式大图处理优化已经成为一个日益重要的研究问题。图在结构和计算上的高耦合性以及不断增长的规模给优化技术的研究带来了挑战。单一模式下的优化技术难以适应大图计算多样化的需求。本课题通过建立混合的存储和计算模式，给出了系统性的混合式优化技术解决方案。本项目的主要研究内容包括 1）分析和洞察混合式分布式图处理技术发展趋势和挑战； 2）研究面向混合式的大图计算框架；3）研究融合同\异步优点的通用编程模型； 4）研究图算子优化和上层图应用实现技术。研究表明，在存储、计算以及编程接口层面实现混合式的优化，是未来大规模图数据处理技术的一种重要发展途径。在效率、易用性和可扩展性上能够达到较好的平衡。本项目在4年的研究周期内，取得了一系列重要的研究成果，并依据核心技术实现了混合式大图计算原型系统GraphHP，目前已经线上开源并提供研究者下载使用。项目开展期间，共发表高水平研究论文41篇。其中，在国际顶级会议（ICDE）上发表论文2篇；国际顶级期刊（TKDE）上发表论文1篇；国际著名期刊和会议（Information Sciences、JPDC、Information Systems、CIKM、ECML-PKDD、ICDM、WWW、ICDCS、DASFAA、VLDB workshop）上发表论文14篇；在SCI检索期刊上发表论文9篇，国内顶级期刊（《软件学报》、《计算机学报》）上发表论文11篇。项目本年共申请专利4项，软件著作权2项。共培养博士研究生5名，硕士研究生12名。项目的相关研究成果将为易用、可扩展、高性能平衡的大图处理的进一步研究与应用提供新的解决思路和技术支撑，具有重要的理论和实践意义。