Hadoop上的PageRank算法优化

发布时间：2019-09-29 21:19

【摘要】：近年来随着社交网络和语义网络的兴起,海量数据挖掘成为学术界和工业界关注的焦点问题。在大规模数据的分析计算中,单台服务器的存储和计算能力已无法满足其对数据量和计算复杂度的需求。Apache基金会开发的开源项目Hadoop作为一种流行的分布式计算平台,在很多涉及海量数据挖掘的产品和应用中发挥着重大作用。 在传统的单机数据挖掘算法的实现中,数据集中存储在本地硬盘上,在计算时读入内存中相应的数据结构里,辅以一些高效的索引。在算法执行过程中程序反复的读取内存中的数据进行计算,最终输出结果到本地硬盘,控制台或远程客户端。对于单机算法来说,我们只需考虑算法的有效性,时间空间复杂度,数据结构的选择和结果的展示。 随着数据量的增加,单台服务器的硬盘无法存储全部的输入输出数据,内存也无法容纳下计算中所产生的中间数据,这时一种行之有效的方法是将单机算法改造成分布式算法,利用多台机器进行分布式并行计算。在算法的分布式移植过程中需要考虑很多问题,例如数据的分布,计算的分布,结果的收集,各节点之间的网络传输,集群节点的故障恢复等等。而Hadoop分布式计算平台使开发者只需关注于计算本身,而网络通信,故障恢复都由Hadoop来负责,这样极大提高了分布式应用的开发效率。 当单机算法扩展到Hadoop分布式平台上时,即成为Map(本地计算及数据再分配)-网络传输Reduce(结果收集,合并计算)的模式。如何将原有的单机算法在Hadoop平台上予以实现对学术界和工业界来说都是一个新的挑战。在算法迁移过程中,数据如何分布,Map和Reduce的key,value执行单元的选择,如何节省网络传输的开销都是开发者需要考虑的问题。 PageRank算法是谷歌公司提出的网页排序算法,用于在搜索引擎中对网页进行打分,随着互联网的发展,网页的数量以指数级增长,远远超过了单台机器的存储和计算能力。如果能将PageRank算法迁移到Hadoop上实现多机并行计算,就可以实现可扩展性,即当网页数量不断增加时,通过动态增加Hadoop集群中机器的数量,满足新的计算需求。 但经过实验发现,将PageRank迁移到Hadoop上虽然满足了可扩展性的需求,但是计算效率一般,本文提出了一种在Hadoop平台上PageRank优化算法,算法的核心思想是通过图聚类改变Map和Reduce的key,value执行单元的粒度,节省Map和Reduce之间的网络传输的开销,平衡MapReduce计算资源,以提高整体的PageRank计算效率。考虑到PageRank算法的执行对象不仅有网页数据,还可能有其他的图数据,当图本身很稀疏或聚类效果不佳时,优化算法可能并不适用,本文针对上述情况建立了一个Cost Model,其目的是在PageRank迭代执行前判断优化算法的效果,如果优化效果不佳则选择原算法进行PageRank计算。 本文详细阐述了如何在Hadoop平台上实现和优化PageRank迭代算法。提出了以图划分将MapReduce计算单元由图结点变为子图,以降低Map和Reduce之间的网络开销,平衡计算资源,实现整体性能提升的优化方法,为其他涉及迭代的图挖掘迭代算法在Hadoop上的优化提出了一种新的思路。
【图文】：

MapReduce 任务中有两种主要的进程：JobTracker 和 TaskTracker。JobTracker运行在 Namenode 上，TaskTracker 运行在 Datanode 上：客户端会向JobTracker提交计算任务JobTracker从NameNode上得到需要的数据在HDFS上存储的具体节点和位置。JobTracker找到有空闲或离所需数据最近的TaskTracker，用来执行相应的计算任务。执行中的TaskTracker会被监控，如果其没有及时向JobTracker发送心跳信息，就会被JobTracker认为该节点岩机，JobTracker会在其他的TaskTracker上重启任务。当执行失败时，TaskTracker会通知JobTracker，，JobTracker会决定如何应对：JobTracker可能会在其他TaskTracker上重启任务，甚至可能将此TaskTracker列入黑名单。当计算任务完成后，JobTracker会更新状态，客户端从JobTracker得到返回

对比两种方法在不同阶段产生的数据量图18的横坐标代表每轮PageRank迭代中的3个阶段，1代表Map开始时，
【学位授予单位】：复旦大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP311.13

【相似文献】

相关期刊论文 前10条

1 戚华春,黄德才,郑月锋;具有时间反馈的PageRank改进算法[J];浙江工业大学学报;2005年03期

2 黄德才;戚华春;;PageRank算法研究[J];计算机工程;2006年04期

3 杨彬;康慕宁;;基于概念的权重PageRank改进算法[J];情报杂志;2006年11期

4 张丽;;PageRank算法的改进[J];科学技术与工程;2007年05期

5 孔娟;马亨冰;;PageRank算法的原理与解析[J];福建电脑;2007年01期

6 姜鑫维;赵岳松;;Topic PageRank——一种基于主题的搜索引擎[J];计算机技术与发展;2007年05期

7 刘松彬;都云程;施水才;;基于分解转移矩阵的PageRank迭代计算方法[J];中文信息学报;2007年05期

8 田甜;倪林;;基于PageRank算法的权威值不均衡分配问题[J];计算机工程;2007年18期

9 刘彤彤;伍小芹;;融入权威性与相关性的PageRank算法[J];信息技术;2008年11期

10 李吉平;吴陈;曾庆军;;基于转移概率的PageRank算法研究[J];科学技术与工程;2008年08期

相关会议论文 前10条

1 ;Key Nodes Mining in Transport Networks Based on PageRank Algorithm[A];2009中国控制与决策会议论文集（3）[C];2009年

2 刘松彬;都云程;施水才;;基于分解转移矩阵的PageRank迭代计算方法[A];内容计算的研究与应用前沿——第九届全国计算语言学学术会议论文集[C];2007年

3 蔺继国;徐锡山;;一种基于用户点击数据的个性化PageRank算法[A];第六届全国信息检索学术会议论文集[C];2010年

4 李文;李淼;张建;朱海;陈雷;;基于混淆网络和PageRank的Nbest重排序[A];少数民族青年自然语言处理技术研究与进展——第三届全国少数民族青年自然语言信息处理、第二届全国多语言知识库建设联合学术研讨会论文集[C];2010年

5 陈小飞;王轶彤;冯小军;;一种基于网页质量的PageRank算法改进[A];第26届中国数据库学术会议论文集（B辑）[C];2009年

6 刘菁菁;林鸿飞;杨志豪;;基于PageRank和锚文本的网页排序研究[A];第三届学生计算语言学研讨会论文集[C];2006年

7 李洋涛;李川;许超;雷晓;徐洪宇;唐常杰;杨宁;;空间评分:基于PageRank的信息网络可视化中节点重要性度量[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

8 Jonathan J.H.Zhu;;PPS Sampling of Web Graph Using Preferential Jumping Strategy[A];Proceedings 2010 IEEE 2nd Symposium on Web Society[C];2010年

9 刘建毅;王菁华;王枞;;基于语言网络的关键词抽取[A];第三届全国信息检索与内容安全学术会议论文集[C];2007年

10 ;Thinking with simple computer models:Modeling of social-economic systems[A];全国复杂系统研究论坛论文集（一）[C];2005年

相关硕士学位论文 前10条

1 蔡建超;基于PageRank算法的搜索引擎优化研究[D];江南大学;2008年

2 邵晶晶;基于PageRank排序算法改进的若干研究[D];华中师范大学;2009年

3 王磊;PageRank的算法改进[D];上海交通大学;2009年

4 张巍;基于PageRank算法的搜索引擎优化策略研究[D];四川大学;2005年

5 姜sバ

本文编号：2544141