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

文档介绍：基于Pregel模型的分布式图着色算法
甘瀛,王鑫,冯志勇,杨雅君
天津大学计算机科学与技术学院天津市认知计算与应用重点实验室天津大学软件学院
X
关注成功!
加关注后您将方便地在我的关注中得到本文献的被引频次变化的通知!
新浪微博
腾讯微博
人人网
开心网
豆瓣网
网易微博
摘    要:
图着色问题一直是计算机科学和数学领域最著名和经典的研究问题之一, 研究者们将其应用于解决各类实际问题, 包括频道分配问题、, , 而无共享Pregel计算模型的提出与发展提高了大规模图数据的处理能力, 其已成为现今大数据处理的主流框架之一, , 受经典图着色算法MIS启发, 设计了一种基于Pregel模型的分布式图着色算法MIS-, 第一种优化策略基于JP算法, 第二种优化策略基于LDF算法;在实现了主流图数据处理模型Pregel的Spark GraphX框架下开发了上述MIS-Pregel算法和两种改进算法JP-Pregel算法和LDF-Pregel算法, 在合成数据集和真实数据集上进行了实验, 大量实验结果表明所提分布式图着色算法能够高效地完成图着色任务, 且JP-Pregel算法和LDF-Pregel算法的着色时间比MIS-%%.
关键词:
分布式图着色; Pregel; Spark; GraphX;
作者简介:甘瀛(1994—) , 男, 天津人, 天津大学硕士研究生, 主要研究领域为语义网, 图数据库。
作者简介:王鑫(1981—) , 男, 天津人, 2009年于南开大学获得博士学位, 天津大学副教授, CCF高级会员, 主要研究领域为语义数据管理, 图数据库, 大规模知识处理。
作者简介:冯志勇(1965—) , 男, 内蒙古呼和浩特人, 1996年于天津大学获得博士学位, 天津大学教授, 博士生导师, CCF高级会员, 主要研究领域为知识工程, 服务计算, 安全软件工程。
作者简介:杨雅君(1983—) , 男, 天津人, 2013年于哈尔滨工业大学获得博士学位, 天津大学讲师, CCF会员, 主要研究领域包括图数据库, 图挖掘和海量数据管理。
基金:国家自然科学基金61572353, 61402323
Distributed Graph Coloring Algorithm Based on Pregel Model
GAN Ying WANG Xin FENG Zhiyong YANG Yajun
School puter Science and Technology, Tianjin University; Tianjin Key Laboratory of puting and Application;
Abstract:
The graph coloring problem is one of the most famous and classic research questions in the field puter science and mathematics. It is applied to solve all kinds of practical problems, including channel allocation problem, safety packing problem, and so on. With the increasing of data scale, the performance of graph coloring algorithms is limited. And existing distributed graph coloring algorithms are mostly based on shared-memory message passing model, such as MPI, Open MP, etc. However, the development of Pregel model that has a share-nothing architecture has enhanced the data processing capability and they has been the key technology