PageRank parallel algorithm based on Web link classification

doi:10.11772/j.issn.1001-9081.2015.01.0048

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (1): 48-52.DOI: 10.11772/j.issn.1001-9081.2015.01.0048

Previous Articles Next Articles

PageRank parallel algorithm based on Web link classification

CHEN Cheng¹, ZHAN Yinwei¹, LI Ying²

1. School of Computer Science and Technology, Guangdong University of Technology, Guangzhou Guangdong 511400, China;
2. Institute of Digital Guangdong, Guangzhou Guangdong 510000, China

Received:2014-07-17 Revised:2014-08-21 Online:2015-01-01 Published:2015-01-26

基于网页链接分类的PageRank并行算法

陈诚¹, 战荫伟¹, 李鹰²

1. 广东工业大学计算机学院, 广州511400;
2. 广东省数字广东研究院, 广州510000

通讯作者: 陈诚
作者简介:陈诚(1989-),男,四川简阳人,硕士研究生,主要研究方向:云计算、分布式应用、数据挖掘;战荫伟(1966-),男,吉林长春人,教授级高级工程师,博士,主要研究方向:图像处理、模式识别、数据挖掘;李鹰(1958-),男,黑龙江哈尔滨人,教授级高级工程师,博士,主要研究方向:遥感技术、物联网、大数据分析.

Abstract

Abstract:

Concerning the problem that the efficiency of serial PageRank algorithm is low in dealing with mass Web data, a PageRank parallel algorithm based on Web link classification was proposed. Firstly, the Web was classified according to its Web link, and the weights of different Web which was from diverse websites were set variously. Secondly, with the Hadoop parallel computation platform and MapReduce which has the characteristics of dividing and conquering, the Webpage ranks were computed parallel. At last, a data compression method of three layers including data layer, pretreatment layer and computation layer was adopted to optimize the parallel algorithm. The experimental results show that, compared with the serial PageRank algorithm, the accuracy of the proposed algorithm is improved by 12% and the efficiency is improved by 33% in the best case.

Key words: link classification, Hadoop, PageRank, MapReduce, data compression

摘要：

针对串行PageRank算法在处理海量网页数据时效率低下的问题,提出一种基于网页链接分类的PageRank并行算法.首先,将网页按照网页所属网站分类,为来自不同站点的网页设置不同的权重;其次,利用Hadoop并行计算框架,结合MapReduce分而治之的特点,并行计算网页排名;最后,采用一种包含3层:数据层、预处理层、计算层的数据压缩方法,对并行算法进行优化.实验结果表明,与串行PageRank算法相比,所提算法在最好情况下结果准确率提高了12%,计算效率提高了33%.

关键词: 链接分类, Hadoop, PageRank, MapReduce, 数据压缩

CLC Number:

TP338.6

CHEN Cheng, ZHAN Yinwei, LI Ying. PageRank parallel algorithm based on Web link classification[J]. Journal of Computer Applications, 2015, 35(1): 48-52.

陈诚, 战荫伟, 李鹰. 基于网页链接分类的PageRank并行算法[J]. 计算机应用, 2015, 35(1): 48-52.

References

[1] PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: bringing order to the Web [C]// Proceedings of the 7th International World Wide Web Conference. Brisbane: [s.n.], 1998: 161-172.
[2] LANGVILLE A, MEYER C D. Google's PageRank and beyond: the science of search engine rankings [M]. Princeton: Princeton University Press, 2006: 1-2.
[3] WHITE T. Hadoop: the definitive guide [M]. Sebastopol: O'Reilly Media, 2009: 103-108.
[4] LIU P. Practice in Hadoop: open the gate of cloud computing [M]. Beijing: Publishing House of Electronics Industry, 2011: 89-91.(刘鹏.实战Hadoop:开启通向云计算的捷径[M].北京:电子工业出版社,2011:89-91.)
[5] DEAN J, CHEMAWAT S. MapReduce: simplified data processing on large clusters [C]// OSDI 2004: Proceedings of the 6th Symposium on Operating System Design and Implementation. Berkeley: USENIX Association, 2004: 137-150.
[6] CHEN G, NIU Z. Research on PageRank algorithm based on MapReduce [J]. Microelectronics and Computer, 2012, 29(5): 81-85.(陈宫,牛秦洲.基于MapReduce的PageRank算法的研究[J].微电子学与计算机,2012,29(5):81-85.)
[7] LIN J, SCHATZ M. Design patterns for efficient graph algorithms in MapReduce [C]// MLG'10: Proceedings of the Eighth Workshop on Mining and Learning with Graphs. New York: ACM, 2010: 78-85.
[8] ZHANG Y, YIN C, WU C. Research on PageRank algorithm optimization based on MapReduce [J]. Application Research of Computers, 2014, 31(2): 431-434.(张永,尹传晔,吴崇正.基于MapReduce的PageRank算法优化研究[J].计算机应用研究,2014,31(2):431-434.)
[9] LIAO S, TAO Y, HE Z, et al. CGPR: an acceleration method for PageRank based on graph-clustering on MapReduce [J]. Journal of Chinese Computer Systems, 2012, 33(6): 1195-1201.(廖松博,陶岳,何震瀛,等.CGPR:一种在MapReduce平台上基于图划分的PageRank加速方法[J].小型微型计算机系统,2012,33(6):1195-1201.)
[10] VISWANATHAN A. A guide to using LZO compression in Hadoop [J]. Linux Journal, 2012, 2012(220): Article No. 1.
[11] ZHANG Y, SONG W, LIU T, et al. Query classification based on URL topic [J]. Application Research of Computers, 2012, 49(6): 1298-1305.(张宇,宋巍,刘挺,等.基于URL主题的查询分类方法[J].计算机研究与应用,2012,49(6):1298-1305.)
[12] Wikipedia. Projects using Heritrix [EB/OL]. [2014-06-13]. http://crawler.archive.org/index.html.

[1]	LI Chong, WANG Yuchen, DU Weijing, HE Xiaotao, LIU Xuemin, ZHANG Shibo, LI Shuren. PageRank-based talent mining algorithm based on Web of Science [J]. Journal of Computer Applications, 2021, 41(5): 1356-1360.
[2]	CHEN Xiaonan, HU Jianmin, CHEN Xi, ZHANG Wei. Simulation and effectiveness evaluation of network warfare based on LightGBM algorithm [J]. Journal of Computer Applications, 2020, 40(7): 2003-2008.
[3]	DONG Cong, ZHANG Xiao, CHENG Wendi, SHI Jia. Performance optimization of distributed file system based on new type storage devices [J]. Journal of Computer Applications, 2020, 40(12): 3594-3603.
[4]	ZHANG Xianli, TANG Jianxin, CAO Laicheng. Influence maximization algorithm based on reverse PageRank [J]. Journal of Computer Applications, 2020, 40(1): 96-102.
[5]	LI Yunshu, TENG Fei, LI Tianrui. Microoperation-based parameter auto-optimization method of Hadoop [J]. Journal of Computer Applications, 2019, 39(6): 1589-1594.
[6]	CHEN Tian, ZUO Yongsheng, AN Xin, REN Fuji. Test data compatible compression method based on tri-state signal [J]. Journal of Computer Applications, 2019, 39(6): 1863-1868.
[7]	ZHENG Zhentao, ZHAO Zhuofeng, WANG Guiling, XU Yao. Ship trajectory extraction method for port parking area identification [J]. Journal of Computer Applications, 2019, 39(1): 113-117.
[8]	GUO Fangfang, CHAO Luomeng, ZHU Jianwen. Multi-source data parallel preprocessing method based on similar connection [J]. Journal of Computer Applications, 2019, 39(1): 57-60.
[9]	XIE Xiaojun, YU Hao, TAO Lei, ZHANG Xinming. Data gathering optimization based on dynamic data compression in energy harvesting wireless sensor network [J]. Journal of Computer Applications, 2018, 38(8): 2353-2358.
[10]	ZHANG Jiachen, LIU Xiaoguang, WANG Gang. Cache optimization for compressed databases in various storage environments [J]. Journal of Computer Applications, 2018, 38(5): 1404-1409.
[11]	CAO Yunpeng, WANG Haifeng. Communication optimization for intermediate data of MapReduce computing model [J]. Journal of Computer Applications, 2018, 38(4): 1078-1083.
[12]	MA Youzhong, ZHANG Zhihui, LIN Chunjie. Research progress in similarity join query of big data [J]. Journal of Computer Applications, 2018, 38(4): 978-986.
[13]	ZHANG Chengchang, ZHANG Huayu, LUO Jianchang, HE Feng. Massive data analysis of power utilization based on improved K-means algorithm and cloud computing [J]. Journal of Computer Applications, 2018, 38(1): 159-164.
[14]	LI Qiang, LIU Xiaofeng. Load balancing strategy of cloud storage based on Hopfield neural network [J]. Journal of Computer Applications, 2017, 37(8): 2214-2217.
[15]	MA Shengjun, CHEN Wanghu, YU Maoyi, LI Jinrong, JIA Wenbo. Analysis of factors affecting efficiency of data distributed parallel application in cloud environment [J]. Journal of Computer Applications, 2017, 37(7): 1883-1887.

PageRank parallel algorithm based on Web link classification

基于网页链接分类的PageRank并行算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics