-
题名基于Pregel模型的分布式图着色算法
被引量：2
- 1
-
-
作者
甘瀛
王鑫
冯志勇
杨雅君
-
机构
天津大学计算机科学与技术学院
天津市认知计算与应用重点实验室
天津大学软件学院
-
出处
《计算机科学与探索》
CSCD
北大核心
2018年第6期886-897,共12页
-
基金
国家自然科学基金Nos.61572353
61402323
天津市自然科学基金No.17JCYBJC15400~~
-
文摘
图着色问题一直是计算机科学和数学领域最著名和经典的研究问题之一。由于目前图数据规模的不断增加,单机图着色算法性能受到限制。现有的分布式图着色算法大多基于共享内存的消息传递模型,而无共享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
-
Keywords
distributed graph coloring
pregel model
Spark
GraphX
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
