基于Pregel模型的分布式图着色算法

作     者：甘瀛 王鑫 冯志勇 杨雅君 GAN Ying1,2,WANG Xin1,2,FENG Zhiyong2,3,YANG Yajun1,2

作者机构：天津大学计算机科学与技术学院天津300354 天津市认知计算与应用重点实验室天津300354 天津大学软件学院天津300354 

基　　金：国家自然科学基金Nos.61572353 61402323 天津市自然科学基金No.17JCYBJC15400~~ 

出 版 物：《计算机科学与探索》 (Journal of Frontiers of Computer Science and Technology)

年 卷 期：2018年第12卷第6期

页      码：886-897页

摘      要：图着色问题一直是计算机科学和数学领域最著名和经典的研究问题之一。由于目前图数据规模的不断增加,单机图着色算法性能受到限制。现有的分布式图着色算法大多基于共享内存的消息传递模型,而无共享Pregel计算模型的提出与发展提高了大规模图数据的处理能力,其已成为现今大数据处理的主流框架之一,但尚缺少将现有的分布式图着色算法适配到Pregel模型进行算法研究与实验比较的工作。为了提高图着色算法的性能,受经典图着色算法MIS(maximal-independent-set)启发,设计了一种基于Pregel模型的分布式图着色算法MIS-Pregel。结合着色时间和所需颜色数等方面提出了两种不同的优化策略,第一种优化策略基于JP算法,第二种优化策略基于LDF算法。在实现了主流图数据处理模型Pregel的Spark Graph X框架下开发了上述MIS-Pregel算法和两种改进算法JP-Pregel和LDF-Pregel。在合成数据集和真实数据集上进行了实验,大量实验结果表明所提分布式图着色算法能够高效地完成图着色任务,且JP-Pregel算法和LDF-Pregel算法的着色时间比MIS-Pregel算法分别平均缩短了26.4%和30.9%。

主 题 词：分布式图着色 Pregel模型 Spark GraphX 

学科分类：081203[081203] 08[工学] 0835[0835] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3778/j.issn.1673-9418.1709036

馆 藏 号：203289602...