小型微型计算机系统
小型微型計算機繫統
소형미형계산궤계통
MINI-MICRO SYSTEMS
2012年
6期
1195-1201
,共7页
廖松博%陶岳%何震瀛%汪卫
廖鬆博%陶嶽%何震瀛%汪衛
료송박%도악%하진영%왕위
PageRank%MapReduce%压缩%图划分
PageRank%MapReduce%壓縮%圖劃分
PageRank%MapReduce%압축%도화분
随着应用的扩展,大规模图数据不断涌现,如何对拥有大量结点的图进行分析成为研究者关注的焦点问题之一.结点的海量性与分析的复杂性使得图分析任务需要借助MapReduce平台多机并行完成.在该平台上,现有的PageRank算法每轮迭代都须扫描、传输所有网页的完整状态,I/O和网络传输的开销严重影响了计算效率.为此,本文提出一种在MapReduce平台上基于图划分的PageRank加速方法:GCPR(Graph-clustering PageRank).GCPR利用图划分、数据两层压缩技术在MapReduce平台上进行PageRank迭代计算,不仅减少了Map到Reduce中间阶段I/O和网络传输的开销(MapReduce运算的主要瓶颈之一),而且平衡了计算资源.实验证明GCPR能极大提升MapReduce平台上的PageRank计算效率.
隨著應用的擴展,大規模圖數據不斷湧現,如何對擁有大量結點的圖進行分析成為研究者關註的焦點問題之一.結點的海量性與分析的複雜性使得圖分析任務需要藉助MapReduce平檯多機併行完成.在該平檯上,現有的PageRank算法每輪迭代都鬚掃描、傳輸所有網頁的完整狀態,I/O和網絡傳輸的開銷嚴重影響瞭計算效率.為此,本文提齣一種在MapReduce平檯上基于圖劃分的PageRank加速方法:GCPR(Graph-clustering PageRank).GCPR利用圖劃分、數據兩層壓縮技術在MapReduce平檯上進行PageRank迭代計算,不僅減少瞭Map到Reduce中間階段I/O和網絡傳輸的開銷(MapReduce運算的主要瓶頸之一),而且平衡瞭計算資源.實驗證明GCPR能極大提升MapReduce平檯上的PageRank計算效率.
수착응용적확전,대규모도수거불단용현,여하대옹유대량결점적도진행분석성위연구자관주적초점문제지일.결점적해량성여분석적복잡성사득도분석임무수요차조MapReduce평태다궤병행완성.재해평태상,현유적PageRank산법매륜질대도수소묘、전수소유망혈적완정상태,I/O화망락전수적개소엄중영향료계산효솔.위차,본문제출일충재MapReduce평태상기우도화분적PageRank가속방법:GCPR(Graph-clustering PageRank).GCPR이용도화분、수거량층압축기술재MapReduce평태상진행PageRank질대계산,불부감소료Map도Reduce중간계단I/O화망락전수적개소(MapReduce운산적주요병경지일),이차평형료계산자원.실험증명GCPR능겁대제승MapReduce평태상적PageRank계산효솔.
