首页> 正文

基于MapReduce的PageRank计算系统的设计与实现

2020-12-11阅读(556)

基于MapReduce的PageRank计算系统的设计与实现

论文摘要

随着信息化时代的到来,各种信息以爆炸模式增长,导致图的规模日益增大。以互联网为例,近十几年来,随着互联网的普及和Web2.0技术的推动,网页排名计算和社交网络分析日趋成为图处理的热点问题,由网页和社交网络构成的大规模图,动辄有数十亿的顶点和上万亿的边。以PageRank为例,按邻接表形式存储100亿个图顶点,每个顶点的存储开销为100字节,那么这个图的存储开销将达到900GB左右。即便是传统的图处理应用,如最优运输路线的确定,也随着GPRS技术的发展和网络的日趋复杂而导致数据规模以几何倍数增长。如此大规模的数据量,给图的有效处理带来了挑战,也提供了机遇。快速有效地处理大规模图,已经成为经济社会发展的迫切需求。针对以上的背景情况,本文以Hadoop下的MapReduce作为编程框架,以PageRank为例,构建了一个基于MapReduce的PageRank计算系统,论文的主要工作如下：（1）采用开源工具Heritrix爬取了节点URL以及URL与URL的关系,并以特定的数据格式进行存储。（2）针对使用MapReduce计算PageRank过程中出现的数据传输量太大影响计算效率的问题,本文在数据预处理部分设计了图邻接表的生成算法,使用图邻接表来表示图节点的信息,针对实现中存在的问题,提出了算法改进。（3）本文采用了三种方案计算PageRank,分别是朴素的PageRank算法（Native-PR）,一次迭代启动一次Job的PageRank算法（OIOJ-PR）、以及基于子图划分的PageRank算法（SGPB-PR）。其中朴素的PageRank算法迭代计算一次PageRank值需要启动两个Job,执行效率并不高,但相对于直接使用URL还是存在着很大的优势。一次迭代启动一次Job计算PageRank算法是针对朴素PageRank算法的改进,在MapReduce过程中保持着图节点的外链信息,减少了作业的启动开销,并在本地节点做了数据归约,即使用Combiner。基于子图划分的PageRank算法对图顶点进行了范围划分,每个Map函数处理一个子图,提高了计算效率。（4）网页关系图展示方面,本文利用开源工具prefuse对PageRank的计算结果做了展示。由于prefuse本身没有提供HDFS的接口,本文设计了数据装载（数据从HDFS到数据库）过程。

论文目录

  • 摘要
  • Abstract
  • 目录
  • 第1章 绪论
  • 1.1 课题的研究背景
  • 1.2 国内外研究现状
  • 1.3 本文的研究内容和组织结构
  • 第2章 相关技术
  • 2.1 云计算
  • 2.2 Heritrix爬虫
  • 2.3 HDFS
  • 2.4 MapReduce编程模型
  • 2.5 PageRank计算模型
  • 2.6 图数据可视化软件prefuse简介
  • 2.7 Hama介绍
  • 2.8 本章小结
  • 第3章 系统的体系结构
  • 3.1 系统的需求设计
  • 3.1.1 系统需求概述
  • 3.1.2 功能需求
  • 3.1.3 性能需求
  • 3.2 系统的总体设计
  • 3.3 本章小结
  • 第4章 数据爬取与数据预处理
  • 4.1 HERITRIX抓取URL
  • 4.1.1 抓取原理
  • 4.1.2 抓取流程分析
  • 4.2 节点编号及初始PageRank生成
  • 4.2.1 节点编号背景
  • 4.2.2 节点编号的算法设计
  • 4.2.3 实验结果
  • 4.3 基于顶点编号的图邻接表生成
  • 4.3.1 图邻接表
  • 4.3.2 图邻接表产生算法
  • 4.3.3 实验结果展示
  • 4.3.4 类型图邻接表算法
  • 4.4 本章小结
  • 第5章 PAGERANK计算
  • 5.1 PageRank计算相关背景
  • 5.1.1 PageRank计算公式
  • 5.1.2 计算PageRank的方法
  • 5.2 朴素的计算PageRank算法NativePR
  • 5.3 一次迭代一个Job计算PageRank算法OIOJ-PR
  • 5.4 基于子图划分计算PageRank算法SGPB-PR
  • 5.5 实验结果显示
  • 5.6 网页排序
  • 5.7 网页连接图可视化
  • 5.7.1 数据加载及格式转化
  • 5.7.2 prefuse可视化显示图的原理
  • 5.7.3 图数据的局部显示
  • 5.7.4 缓存更新
  • 5.7.5 prefuse作图结果
  • 5.8 本章小结
  • 第6章 系统部署及性能评估
  • 6.1 系统部署环境要求
  • 6.2 系统配置和启动
  • 6.3 运行PageRank程序
  • 6.4 PageRank程序结果分析
  • 6.5 本章小结
  • 第7章 结束语
  • 7.1 本文总结
  • 7.2 进一步工作以及展望
  • 参考文献
  • 致谢
  • 攻读硕士期间参加的项目和发表的论文

    • 相关论文文献

    • [1].一种基于MapReduce的局部相似自连接算法[J]. 计算机技术与发展 2020(02)
    • [2].基于MapReduce云计算的智能电网数据分析方法研究[J]. 电子设计工程 2020(13)
    • [3].基于MapReduce的液晶屏缺陷检测方法[J]. 计算机工程与应用 2017(05)
    • [4].MapReduce技术在日志分析中的研究应用[J]. 计算机时代 2017(06)
    • [5].基于MapReduce的数据流频繁项集挖掘算法[J]. 华中师范大学学报(自然科学版) 2017(04)
    • [6].大数据环境下基于MapReduce和并行数据库的混合模式探究[J]. 河南广播电视大学学报 2017(01)
    • [7].一种基于MapReduce的文本聚类方法研究[J]. 计算机科学 2016(01)
    • [8].基于MapReduce的频繁闭项集挖掘算法改进[J]. 微型机与应用 2015(24)
    • [9].基于MapReduce的故障诊断方法[J]. 中国新通信 2016(16)
    • [10].基于MapReduce框架的海量数据相似性连接研究进展[J]. 计算机科学 2015(01)
    • [11].基于MapReduce的频繁项集挖掘算法研究[J]. 物流技术 2015(08)
    • [12].MapReduce并行编程模型研究综述[J]. 计算机科学 2015(S1)
    • [13].脑机接口的MapReduce计算模型[J]. 福州大学学报(自然科学版) 2013(06)
    • [14].故障诊断算法在MapReduce中的优化实现[J]. 计算机测量与控制 2016(11)
    • [15].一种基于MapReduce的实体共指消解方法[J]. 齐鲁工业大学学报(自然科学版) 2016(06)
    • [16].面向多用户环境的MapReduce集群调度算法研究[J]. 高技术通讯 2017(04)
    • [17].浅谈MapReduce与关系型数据库技术的融合[J]. 河北软件职业技术学院学报 2017(03)
    • [18].应用MapReduce的多维小波变换模型[J]. 辽宁工程技术大学学报(自然科学版) 2016(01)
    • [19].一种基于MapReduce的频繁项集挖掘算法[J]. 软件导刊 2015(04)
    • [20].支持云计算环境的MapReduce模拟器设计[J]. 信阳师范学院学报(自然科学版) 2015(03)
    • [21].基于应用程序的MapReduce性能优化[J]. 计算机技术与发展 2015(07)
    • [22].基于MapReduce模型的排序算法优化研究[J]. 计算机科学与探索 2015(04)
    • [23].基于MapReduce的频繁项目集挖掘算法在煤炭销售系统中的研究[J]. 煤炭技术 2014(02)
    • [24].基于MapReduce的数据立方体分区优化算法研究[J]. 信息安全与技术 2014(04)
    • [25].基于MapReduce的多元线性回归预测模型[J]. 计算机应用 2014(07)
    • [26].基于MapReduce的蚁群优化算法实现方法[J]. 计算机科学 2014(07)
    • [27].一种基于MapReduce的频繁闭项集挖掘算法[J]. 模式识别与人工智能 2012(02)
    • [28].MapReduce并行编程模型研究综述[J]. 电子学报 2011(11)
    • [29].基于投影寻踪和MapReduce的并行案例推理模型[J]. 计算机应用研究 2017(02)
    • [30].MapReduce编程模型及其在图像处理中的应用研究综述[J]. 测绘与空间地理信息 2015(04)

    标签：;  ;  ;  

    基于MapReduce的PageRank计算系统的设计与实现
    下载Doc文档

    猜你喜欢

    © 2024 毕速过 版权所有 鄂ICP备12018319号-5