基于MapReduce的并行PageRank算法实现

doi:10.3969/j.issn.1000-3428.2014.02.007

计算机工程

基于MapReduce的并行PageRank算法实现

平宇¹，向阳¹，张波²，黄寅飞³

(1. 同济大学计算机科学与技术系，上海 201804；2. 上海师范大学信息与机电工程学院，上海 200234；3. 上海证券交易所，上海 200120)

收稿日期:2013-04-08 出版日期:2014-02-15 发布日期:2014-02-13
作者简介:平宇(1988－)，男，硕士研究生，主研方向：数据库技术，数据挖掘；向阳，教授、博士生导师；张波，副教授；黄寅飞，高级工程师
基金项目:
国家自然科学基金资助项目(61103069, 71170148)；国家科技支撑计划基金资助项目(2012BAD35B01)；上海市科技创新计划基金资助项目(11DZ1501703)；陈家镇智慧社区和智能交通基金资助项目(11dz1210600)

Implementation of Parallel PageRank Algoirthm Based on MapReduce

PING Yu ¹, XIANG Yang ¹, ZHANG Bo ², HUANG Yin-fei ³

(1. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China; 2. College of Information, Mechanical and Electrical Engineering, Shanghai Normal University, Shanghai 200234, China;3. Shanghai Stock Exchange, Shanghai 200120, China)

Received:2013-04-08 Online:2014-02-15 Published:2014-02-13

摘要/Abstract

摘要： 分布式网络爬虫的广泛应用使得搜索引擎的数据规模呈几何式增长，面对数以TB甚至PB量级的数据，单机模式下的PageRank算法由于CPU、I/O和内存的开销过大导致效率低下。为此，提出一种基于MapReduce框架的并行PageRank算法。在算法的一次迭代过程中，利用Map函数对网页拓扑信息文件进行解析，使用Reduce函数计算网页得分，从而并行化PageRank算法的中间迭代过程。通过计算全局网页得分控制迭代次数，得到较精确的网页排序结果。实验结果表明，该算法在保持原有单机PageRank算法整体网页排序精度的基础上，具有较好的集群性能和较快的执行速度。

关键词: 搜索引擎, PageRank算法, MapReduce框架, 并行计算, Hadoop平台

Abstract: The emergence of distributed Web crawl largely expands the scale of related Web information. Since PageRank needs to process the topology of entire existed page set, the limitation of CPU, I/O and memory becomes the big issue when it confronts the data in TB or PB level. Aiming at these problems, this paper proposes a parallel PageRank algorithm based on MapReduce. In a certain iteration of algorithm, it processes the files containing the topology of Web page graph by Map function and calculates the pages’ scores by Reduce function. Using the global Web page score as convergence to control iterations and get more precise Web page sorting result. Experimental result shows that the improved algorithm has better clustering performance and faster execution speed on the basis of keeping the overall Web page sorting accuracy of single machine PageRank algorithm.

Key words: search engine, PageRank algorithm, MapReduce framework, parallel computing, Hadoop platform

中图分类号:

TP391.3

平宇，向阳，张波，黄寅飞. 基于MapReduce的并行PageRank算法实现[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2014.02.007.

PING Yu, XIANG Yang, ZHANG Bo, HUANG Yin-fei. Implementation of Parallel PageRank Algoirthm Based on MapReduce[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2014.02.007.

[1]	马慧芳, 李苗, 童海斌, 詹子俊. 基于通配符模式与随机游走的关键词提取方法[J]. 计算机工程, 2020, 46(7): 78-83.
[2]	肖成龙, 聂紫阳, 王宁, 张重鹏, 王珊珊. 基于并行约束规划的最大团识别研究[J]. 计算机工程, 2020, 46(4): 53-59,69.
[3]	童曼琪, 黄江升, 郭昆. 融合Spark与隐性兴趣的用户综合影响力度量[J]. 计算机工程, 2020, 46(11): 61-69.
[4]	李洁, 朱洪亮, 陈玉玲, 辛阳. 基于哈希存储与事务加权的并行Apriori改进算法[J]. 计算机工程, 2020, 46(11): 109-116.
[5]	徐国伟, 陈建, 成怡. 基于GPU并行计算的雷达杂波模拟研究[J]. 计算机工程, 2020, 46(11): 306-314.
[6]	宋匡时, 李翀, 张士波. 一个轻量级分布式机器学习系统的设计与实现[J]. 计算机工程, 2020, 46(1): 201-207.
[7]	薛建伟, 姜爱民. 光学综合孔径原理样机的计算与控制系统[J]. 计算机工程, 2019, 45(8): 107-112.
[8]	张浩盛伦,李翀,柯勇,张士波. 一种分布式用户浏览点击模型算法[J]. 计算机工程, 2019, 45(3): 1-6.
[9]	沈雁,戴瑜兴. 基于GPU的并行Cholesky分解及其应用[J]. 计算机工程, 2019, 45(2): 284-289.
[10]	李易禅,凌诚. 蛋白质系统发育分析并行计算方法研究[J]. 计算机工程, 2019, 45(2): 296-302.
[11]	黄贤英, 阳安志, 刘小洋, 刘广峰. 一种改进的微博用户影响力评估算法[J]. 计算机工程, 2019, 45(12): 294-299.
[12]	李文信, 周晓波, 徐仁海, 齐恒, 李克秋. 一种近似最小有效瓶颈优先的Coflow调度机制[J]. 计算机工程, 2019, 45(10): 19-25,32.
[13]	杨正龙, 高建华. 基于蜕变测试的面向用户搜索引擎性能分析[J]. 计算机工程, 2019, 45(10): 52-56,63.
[14]	宁可,孙同晶,徐洁洁. 面向海量数据的改进最近邻优先吸收聚类算法[J]. 计算机工程, 2018, 44(4): 35-40.
[15]	严锐,李石君. 基于查询意图识别与主题建模的文档检索算法[J]. 计算机工程, 2018, 44(3): 189-194.

基于MapReduce的并行PageRank算法实现

Implementation of Parallel PageRank Algoirthm Based on MapReduce

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10