GCPR:一种在MapReduce平台上基于图划分的PageRank加速方法

摘要：

随着应用的扩展,大规模图数据不断涌现,如何对拥有大量结点的图进行分析成为研究者关注的焦点问题之一.结点的海量性与分析的复杂性使得图分析任务需要借助MapReduce平台多机并行完成.在该平台上,现有的PageRank算法每轮迭代都须扫描、传输所有网页的完整状态,I/O和网络传输的开销严重影响了计算效率.为此,本文提出一种在MapReduce平台上基于图划分的PageRank加速方法:GCPR(Graph-clustering PageRank).GCPR利用图划分、数据两层压缩技术在MapReduce平台上进行PageRank迭代计算,不仅减少了Map到Reduce中间阶段I/O和网络传输的开销(MapReduce运算的主要瓶颈之一),而且平衡了计算资源.实验证明GCPR能极大提升MapReduce平台上的PageRank计算效率.

关键词：PageRank、MapReduce、压缩、图划分

所属期刊栏目：33

分类号：TP301(计算技术、计算机技术)

资助基金：国家科技重大专项项目2010ZX01042-003-004;国家自然科学基金项目61033010;国家“八六三”高技术研究发展计划重点基金项目2009AA062803;上海市科委现代服务业专项基金项目10dz1511000

在线出版日期：2012-11-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1195-1201