《基于pregel模型的分布式图着色算法》由会员分享，可在线阅读，更多相关《基于pregel模型的分布式图着色算法（16页珍藏版）》请在金锄头文库上搜索。
1、基于 Pregel 模型的分布式图着色算法 甘瀛，王鑫，冯志勇，杨雅君 天津大学 计算机科学与技术学院 天津市认知计算与应用重点实验室 天津大学 软件学院 摘 要： 图着色问题一直是计算机科学和数学领域最著名和经典的研究问题之一, 研究者们将其应用于解决各类实际问题, 包括频道分配问题、安全装箱问题等.由于目前图数据规模的不断增加, 现有的单机图着色算法性能受到限制.现有的分布式图着色算法大多基于 MPI 等共享内存的消息传递模型, 而无共享 Pregel 计算模型的提出与发展提高了大规模图数据的处理能力, 其已成为现今大数据处理的主流框架之一, 但目前尚缺少将现有的分布式图着色算法适配到 P
2、regel 模型下进行算法研究与实验比较的工作.为了提高图着色算法的性能, 受经典图着色算法 MIS 启发, 设计了一种基于 Pregel 模型的分布式图着色算法 MIS-Pregel.结合着色时间和所需颜色数等方面对其提出了两种不同的优化策略, 第一种优化策略基于 JP 算法, 第二种优化策略基于 LDF 算法;在实现了主流图数据处理模型 Pregel 的 Spark GraphX 框架下开发了上述 MIS-Pregel 算法和两种改进算法 JP-Pregel 算法和 LDF-Pregel 算法, 在合成数据集和真实数据集上进行了实验, 大量实验结果表明所提分布式图着色算法能够高效地完成图着
3、色任务, 且JP-Pregel 算法和 LDF-Pregel 算法的着色时间比 MIS-Pregel 算法分别平均缩短了 26.4%和 30.9%.关键词： 分布式图着色; Pregel; Spark; GraphX; 作者简介：甘瀛 (1994) , 男, 天津人, 天津大学硕士研究生, 主要研究领域为语义网, 图数据库。作者简介：王鑫 (1981) , 男, 天津人, 2009 年于南开大学获得博士学位, 天津大学副教授, CCF 高级会员, 主要研究领域为语义数据管理, 图数据库, 大规模知识处理。作者简介：冯志勇 (1965) , 男, 内蒙古呼和浩特人, 1996 年于天津大学获得博
4、士学位, 天津大学教授, 博士生导师, CCF 高级会员, 主要研究领域为知识工程, 服务计算, 安全软件工程。作者简介：杨雅君 (1983) , 男, 天津人, 2013 年于哈尔滨工业大学获得博士学位, 天津大学讲师, CCF 会员, 主要研究领域包括图数据库, 图挖掘和海量数据管理。基金：国家自然科学基金 61572353, 61402323Distributed Graph Coloring Algorithm Based on Pregel ModelGAN Ying WANG Xin FENG Zhiyong YANG Yajun School of Computer Scienc
5、e and Technology, Tianjin University; Tianjin Key Laboratory of Cognitive Computing and Application; Abstract： The graph coloring problem is one of the most famous and classic research questions in the field of computer science and mathematics. It is applied to solve all kinds of practical problems,
6、 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.
7、 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 for large-scale graph-data processing. But there is no related work to improve the existing distributed graph coloring algorithms to adapt
8、share-nothing Pregel model and make an algorithm research and experimental comparison. In order to improve the performance of graph coloring algorithms, this paper devises a distributed graph coloring algorithm based on the Pregel model and proposes two optimized strategies to optimize the time for
9、coloring and total number of colors. We implement the basic algorithm and two optimized algorithms based on above optimized strategies on Spark GraphX. Finally, extensive experiments show that the proposed basic algorithm have high efficiency of coloring and the performance of the optimization algor
10、ithms is improved by 26.4% and 30.9% than the basic algorithm over both synthetic and real datasets.Keyword： distributed graph coloring; Pregel; Spark; GraphX; 1 引言近来, 由于以 RDF 为代表的图数据量日益增加, 图数据管理开始受到越来越多的关注.如何有效地对 RDF 图数据进行加载、存储和查询成为现在研究的一个热点问题.目前, 已经有很多工作对如何有效管理 RDF 图数据进行了研究, 并提出了很多有效的解决方案.其中 DB2RD
11、F1是一种将 RDF 图存储到关系数据库的有效方法, 但由于 RDF 图数据规模的不断增长, 单机版本的 DB2RDF 的数据加载和存储方案的性能受到限制, 因此需要一种分布式的加载和存储方案来提高已有方案的性能.同时, DB2RDF 需要使用图着色算法进行 RDF 图存储模式的构建, 因此使用相对应的分布式图着色算法来获得可伸展的 RDF 图数据装载性能成为需要解决的问题.图着色问题是最著名的 NP-完全问题之一2, 其的最简单形式是顶点着色问题, 即为图中的每个顶点分配一个颜色, 以保证任何相邻的顶点不具有相同的颜色.图着色算法可以应用于很多实际问题中, 包括频道分配问题、任务调度问题、安
12、全装箱问题等.由于图着色问题是 NP-完全问题, 目前没有在多项式时间内解决这个问题的确定算法.但很多启发式的单机或者分布式算法已经被提出, 其中使用了贪心策略的启发式算法是解决图着色问题的最基本和经典的算法.由于现在需要处理的数据量越来越大, 单机图着色算法的性能渐渐不能满足用户的需要, 因此, 很多的并行图着色算法被提出, 这些算法通过分布式计算使得图着色算法的效率进一步提高.然而, 目前大多数分布式图着色算法3,4,5,6是基于传统的共享内存模型, 如 MPI, Open MP 等.根据我们的调查, 目前尚缺少相关研究工作对现有的分布式图着色算法加以改进调整, 适配到 Pregel7模型
13、下进行算法研究与实验比较.Pregel 模型具有“以顶点为中心”计算的特点, 因此更适合并行图计算, 使用 Pregel 消息传递模型来进行并行图计算可以进一步提高图计算效率.本文旨在设计和实现一种基于 Pregel 模型的分布式 RDF 图着色算法来进一步提高图着色的效率.本文的主要贡献如下:(1) 基于 Pregel 模型设计了分布式图着色算法 MIS-Pregel 算法.将主流的寻找最大独立集的图着色方法适配到 Pregel 模型下.通过使用“以顶点为中心”的Pregel 消息传递机制, 完成寻找独立集和着色过程.(2) 为进一步提高算法的性能, 包括减少着色时间和所需颜色数, 引入了两
14、种启发式规则, 设计了所提基本算法的两种优化版本 JP-Pregel 算法和 LDF-Pregel 算法, 并对三种算法进行了比较分析.(3) 在主流大数据处理框架 Spark Graph X 下实现了上述三种算法, 并在合成数据集和真实数据集上进行了大量实验, 验证了 JP-Pregel 算法和 LDF-Pregel算法对于 MIS-Pregel 算法的性能提升, 分析了图着色过程的时间花费, 以及最终所需总颜色数与数据集规模及数据集中谓语数量的关系.需要说明的是, 本文所提分布式图着色方法具有通用性, 除了 RDF 图, 还可用于其他任何类型的图数据着色问题.本文的剩余部分组织如下:第 2
15、 节介绍相关工作.在第 3 节介绍理解本文工作需具备的基础知识.在第 4 节提出了基于 Pregel 模型的分布式 RDF 图着色算法MIS-Pregel 算法.第 5 节给出上述图着色算法的两种改进优化算法 JP-Pregel算法和 LDF-Pregel 算法.第 6 节进行实验, 大量实验结果验证了所提算法及其优化策略的有效性和高效性.第 7 节对全文工作进行总结.2 相关工作鉴于目前使用贪心策略的启发式算法是解决图着色问题最经典和有效的算法, 本节将对目前已有的基于贪心策略的启发式图着色算法进行介绍, 其主要分为以下两类:(1) 单机的情况.基于贪心策略的图着色算法首先按照一定的顺序寻找
16、图中的所有顶点, 当寻找到某一顶点, 为其分配可用的最小的颜色, 即这个颜色不能与当前着色点的邻居点的颜色相同.First Fit (FF) 8算法是一种简单的贪心着色算法, 它每次从一个随机的顶点顺序中得到下一个需要着色的顶点.Largest-Degree-First-Ordering (LFO) 9算法在寻找下一个着色顶点时总是选择剩余顶点中度最大的点.Incidence-Degree-Ordering (IDO) 10算法则以邻居中已着色的顶点的数量作为是否选择的依据.Saturation-Degree-Ordering (SDO) 11算法选择下一顶点时的依据则是其邻居中颜色的数量.这些算法由于只适用于单机的情况, 不能满足大规模图数据处理的要求, 但它们仍然可以为设计图着色并行算法版本提供借鉴和参考.(2) 并行的情况.目前的大多数并行启发式图着色算法都基于寻找独立集的思想.其中, Lucy12提出了一个并行构造独立集的 Maximal-Independent-Set (MIS) 算法, 其给每个
