基于应用长时空域运行特征的图数据存储组织及系统优化研究

Due to the universal expression ability, graph data has been widely used in transportation logistics, finance, bio-information, social networking, e-commerce, public security and many other important areas. With the rapidly popularized and applied technologies， such as mobile Internet, smart terminals and social media, graph data grows rapidly in size. However, due to the complexity and the large-scale size of the graph data, there are some serious challenges during the processes of storage management and computation analysis. Existing graph-processing systems fail to support various types of graph algorithms with different features efficiently, thus leading to the low efficiency of the graph-processing cluster. Because they usually organize external storage data by using a single static and their data access scheme is inefficiently. Hence, it is one of the most important problems to organize the large-scale graph data efficiently, involving the techniques of storage, index, update and query. Based on the problem of the mismatching between the in-memory/external data organizations and the execution features of graph applications, this project proposes a long space-time application runtime characteristics based method of dynamic memory graph data organization and the external graph data organization scheme that is based on the benefit evaluation, to reduce the data access cost in the computation process, thus making the graph-processing systems more energy-efficient when processing large-scale graph-computing jobs.

图数据具有一般性表示能力，被广泛应用到交通物流、金融、生物信息、社交网络、电子商务、以及公共安全等众多重要领域。随着移动互联网、智能终端和社交媒体等技术的快速普及应用，图数据亦呈现爆炸式增长。而图数据的关系复杂性和大规模的数据量，给图数据的存储管理和计算分析带来重大技术挑战。目前图处理系统静态单一的内外存数据组织方式、低效的数据访问模式，无法高效地支持种类多样、特征各异的图算法应用，也进一步导致了大规模图处理集群系统能效不高。针对大规模图数据的高效组织，如存储、索引、更新、查找等，已成为急待解决的问题。本项目针对图数据内外存组织形态与图应用运行特征失配的问题，提出基于应用长时空域运行特征的图数据动态内存组织和基于收益评价的图数据外存组织模式，降低计算过程中数据访问开销，支持构建高效、绿色的大规模图处理系统。

图数据作为一种重要的数据结构因具有一般性表示能力，被广泛应用到交通物流、金融、生物信息、社交网络、电子商务、以及公共安全等众多重要领域。本项目针对目前图处理系统静态单一的内外存数据组织方式、低效的数据访问模式，无法高效地支持种类多样、特征各异的图算法应用以及大规模图处理集群系统的能效受到限制等问题，开展了一系列基于应用长时空域运行特征的图数据动态内存组织、基于收益评价的图数据外存组织模式和面向不同场景的高能效图计算系统的研究。具体地，（1）对于图数据的动态内存组织的研究，项目组结合了图应用及图数据的动态特征提出了基于图应用特征的高效内存数据布局策略、基于活跃度布局的图处理访存策略以及基于日志结构合并子图的时序图存储模型；（2）对于图数据的外存组织模式研究，项目组通过探寻有效的外存访问收益评价提出了基于索引定位的外存访问策略、基于I/O调度的多任务外存模式图处理系统、面向图处理的粗粒度多外存IO管理策略、基于应用特征的混合I/O 访问和顶点更新策略、外存模式图计算系统的子图构建优化、面向并发多任务的外存模式图计算模型优化以及面向随机游走的分区关联感知I/O管理方法；（3）对于构建高能效的图处理系统，项目从面向大规模图表示学习的高效随机游走算法、面向大规模图的多估测目标抽样技术、面向共享内存三角形计算的轻量压缩技术以及面向高带宽网络的分布式图处理系统的快速消息产生及交换技术等多个应用场景提出了系统优化的解决方案。.基于上述研究成果，本项目共发表学术论文16篇，其中CCF A类会议或期刊论文4篇，申请专利15项，其中获授权8项。