首页 | 官方网站   微博 | 高级检索  
     

GCPR:一种在MapReduce平台上基于图划分的PageRank加速方法
引用本文:廖松博,陶岳,何震瀛,汪卫.GCPR:一种在MapReduce平台上基于图划分的PageRank加速方法[J].小型微型计算机系统,2012,33(6):1195-1201.
作者姓名:廖松博  陶岳  何震瀛  汪卫
作者单位:复旦大学 计算机科学技术学院,上海,200433
基金项目:国家科技重大专项项目,国家自然科学基金项目,国家“八六三”高技术研究发展计划重点基金项目,上海市科委现代服务业专项基金项目
摘    要:随着应用的扩展,大规模图数据不断涌现,如何对拥有大量结点的图进行分析成为研究者关注的焦点问题之一.结点的海量性与分析的复杂性使得图分析任务需要借助MapReduce平台多机并行完成.在该平台上,现有的PageRank算法每轮迭代都须扫描、传输所有网页的完整状态,I/O和网络传输的开销严重影响了计算效率.为此,本文提出一种在MapReduce平台上基于图划分的PageRank加速方法:GCPR(Graph-clustering PageRank).GCPR利用图划分、数据两层压缩技术在MapReduce平台上进行PageRank迭代计算,不仅减少了Map到Reduce中间阶段I/O和网络传输的开销(MapReduce运算的主要瓶颈之一),而且平衡了计算资源.实验证明GCPR能极大提升MapReduce平台上的PageRank计算效率.

关 键 词:PageRank  MapReduce  压缩  图划分

GCPR:an Acceleration Method for PageRank Based on Graph-clustering on MapReduce
LIAO Song-bo , TAO Yue , HE Zhen-ying , WANG Wei.GCPR:an Acceleration Method for PageRank Based on Graph-clustering on MapReduce[J].Mini-micro Systems,2012,33(6):1195-1201.
Authors:LIAO Song-bo  TAO Yue  HE Zhen-ying  WANG Wei
Affiliation:(School of Computer Science,Fudan University,Shanghai 200433,China)
Abstract:As various applications spring up,the uses of large-scale graphs mushroom.How to analyze the graphs of abundant nodes draws the attention of researchers.The magnanimity of nodes and the complexity of the analysis make the task of analyzing the large-scale graphs resort to MapReduce for parallel computing on the distributed system.On MapReduce,the classical PageRank algorithm calls for scanning and transferring the entire state of the graph at each iteration.The cost of I/O and network transmitting increases the total time of computing.Given this problem,this paper proposes an algorithm with better efficiency for PageRank based on Graph-clustering on MapReduce: GCPR,which makes use of graph-clustering and twice compression.By means of GCPR,the cost of I/O and network transmitting between Map and Reduce(the major bottleneck of MapReduce) has been lessened and the computational resources have been balanced.Experiments demonstrate that GCPR could greatly enhance the computing efficiency of PageRank on MapReduce.
Keywords:PageRank  MapReduce  compression  graph-clustering
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号