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

来源 :计算机科学与探索 | 被引量 : 0次 | 上传用户:wangshucai123
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图着色问题一直是计算机科学和数学领域最著名和经典的研究问题之一。由于目前图数据规模的不断增加,单机图着色算法性能受到限制。现有的分布式图着色算法大多基于共享内存的消息传递模型,而无共享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%。
其他文献
义务教育阶段的美术教育由注重教师的教转变为注重学生的学,由注重美术技能的训练到鼓励个性化的艺术表现。体现了以学生为本,面向全体,张扬个性,重视学生学习活动过程和情感体验
本文以语言的各个表征层面——词语、句法与篇章为例,对汉英语言的差异做出分析,从而探析蕴含于语言差异之中的中西文化之差异,进一步通过分析这些差异,为母语是汉语的英语学习者
“酵母菌和霉菌”一节教学内容与学生的日常生活关系密切,学生知道酵母菌能够用于发面、酿酒,放久了的馒头会发霉等,但他们却不知道其中的道理。利用这些生活现象设计问题隋境,能
针对当前人们因不良饮食习惯导致高血压、糖尿病等慢性病问题,设计了一款基于微信小程序的智能膳食分析系统。系统由智能餐盘、云服务器及微信小程序组成,可通过智能餐盘的RFID模块自动获取用户用餐数据;调用开源食物数据库与用户用餐数据进行比对,为用户提供营养咨询服务;同时在微信小程序上为用户搭建社交平台,方便用户交流。此外还设有饮食定制功能,专门为有特定饮食需求的人群服务。系统基于用户用餐大数据完成膳食分
文中通过城市级共享单车监管平台的建设与应用,为城市管理者解决共享单车盲目投放、乱停乱放、恶性竞争与运营监管等问题提供了方法与工具,为城市绿色交通的有序化和共享单车行业的健康可持续发展提供了宝贵的应用实例与项目经验。
期刊
随着高中新课程实验的推进,高中数学教学如何设计恰当的教学情境,让学生亲历知识发生、发展以及形成的过程,“重蹈人类思维发展中那些关键性步子”,再现并体会数学家对一些重大发
目的探讨平时颅脑投射物伤的临床特点和救治原则。方法回顾性总结46例平时颅脑投射物伤的损伤特点和救治情况。本组非穿透伤9例、盲管伤36例、切线伤1例,无贯通伤。合并胸外
针对矿井安全问题,文中设计了一个应用于煤矿井下的智能监控及预警系统,主要采用ZigBee网络及实时数据关联分析技术。井下系统由ZigBee无线传感器网络构成,选用C8051F124微处理器、CC2530芯片,以及多种采集矿井环境的传感器。井上网络使用高性能服务器将采集的数据进行分离写入数据库,并进行实时关联计算,将处理结果呈现在PC端及智能终端。
针对输油管道工程中常见的架空管道因存在局部腐蚀,而在地震作用下极易破坏的问题,采用ADINA有限元软件,建立含腐蚀缺陷及腐蚀缺陷修复后的输油管道与内部液体的流固耦合模型