基于消息传递机制的MapReduce图算法研究

• 作者: 伍赛 李战怀 潘巍 陈群
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 云计算 MapReduce 大同步模型 消息传递 图算法 PageRank
• 年，卷（期）: 2011,（10）
• 所属期刊栏目: 海量数据管理架构和处理算法
• 页码范围: 1768-1784
• 分类号: TP311
• 字数: 17210字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2011.01768

摘要

单机运行环境难以满足基于海量数据的大图算法对时空开销的需求,如何设计高效的面向云计算环境的分布式大图算法越来越受到人们的关注,MapReduce作为云计算的核心计算模式受限于易并行(EP)计算模型的制约不易表达图算法.文中突破了MapReduce基于易并行计算的假设,增强了MapReduce既有的编程规范,新的大同步(BSP)计算模型既能保证兼容旧的MapReduce作业可以无改动的运行,同时引入消息传递机制允许变化的状态数据在并行任务的超级步间进行交互.系统提供高度灵活的消息自定义接口,针对不同应用需求设计了轻量级和重量级两种自适应的消息传递机制,更高效地支持有数据交互需求的包含迭代处理的一大类图算法.在真实大规模图数据集上的实验结果表明,相比于原始的MapReduce作业外部链式处理,该文提出的BSP模型下的内部超级步迭代计算模式大幅降低了大图算法的处理时间.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李战怀	西北工业大学计算机学院	254	2139	21.0	35.0
2	陈群	西北工业大学计算机学院	54	495	11.0	20.0
3	潘巍	西北工业大学计算机学院	17	221	7.0	14.0
4	伍赛	新加坡国立大学计算机学院	1	86	1.0	1.0