学位论文 > 优秀研究生学位论文题录展示

基于MapReduce的个性化PageRank算法研究

作　者: 刘记云
导　师: 杨静
学　校: 哈尔滨工程大学
专　业: 计算机软件与理论
关键词: MapReduce 个性化 PageRank算法归并算法
分类号: TP393.092
类　型: 硕士论文
年　份: 2013年
下　载: 67次
引　用: 0次
阅　读: 论文下载

内容摘要

近年来，随着计算机处理能力的不断提高，互联网技术取得了飞速发展，各种基于Web2.0技术的新兴网络应用的出现使得越来越多的数据被收集和整合在一起，互联网中的网页数目激增。在当今以信息化为主要标志的时代里，海量的数据是社会宝贵而又重要的财富。互联网上的信息量呈现指数式上升，互联网上到处都是垃圾邮件和多余信息，人们必须消耗大量时间，寻找有用信息。现在大量冗余信息已严重影响人们获取信息的效率，所以，快捷、方便、高效地获取所需信息成为越来越多用户和运营商关心的一个焦点问题。随着互联网的发展，通过检索获得信息已经融入到普通人的日常生活之中了。本文首先对基于MapReduce的个性化 PageRank算法相关背景和理论进行了阐述，然后分析并总结了MapReduce框架下的个性化PageRank算法的研究现状。在此基础上，进一步对基于MapReduce的个性化PageRank算法进行了更深一层的研究，着重分析算法中影响性能和效果的瓶颈因素，即迭代次数和I/O成本并非最优，进而提出了归并算法。然后对归并算法进行分析，包括算法的正确性分析、迭代次数分析和I/O成本分析。通过分析得出在所有随机游走算法中，归并算法的迭代次数最优，I/O成本也比舍入算法和SQRT算法要好。最后，本文使用SougouQ数据集，在MapReduce编程模型上实现个性化PageRank算法及其改进算法，并对所获得的实验数据进行对比和分析。通过对所需的机器时间、时钟时间和准确性的比较，表明了归并算法的可行性、合理性。改进后的算法不仅具有最低的迭代次数，而且所取得的误差也较低。

全文目录

摘要  5-6
Abstract  6-10
第1章绪论  10-15
  1.1 研究背景及意义  10-11
  1.2 国内外研究现状与热点  11-14
    1.2.1 个性化 PageRank 算法研究现状  11-13
    1.2.2 MapReduce 研究现状  13-14
  1.3 论文主要研究内容  14
  1.4 论文组织结构  14-15
第2章相关理论与技术  15-31
  2.1 MapReduce基本理论  15-20
    2.1.1 MapReduce 简介  15
    2.1.2 MapReduce编程模式  15-16
    2.1.3 MapReduce实现框架  16-18
    2.1.4 MapReduce执行概述  18-19
    2.1.5 MapReduce控制节点的数据结构和容错机制  19-20
  2.2 PageRank 算法介绍  20-25
    2.2.1 PageRank 算法基本概念  20-23
    2.2.2 随机冲浪模型  23-24
    2.2.3 马氏链理论  24
    2.2.4 PageRank 算法的优缺点  24-25
  2.3 基于 MapReduce 的 PageRank 算法  25-27
  2.4 个性化 PageRank 算法  27-30
    2.4.1 Personalzied 查询  27-29
    2.4.2 个性化 PageRank 算法  29-30
  2.5 本章小结  30-31
第3章基于 MapReduce 的个性化 PageRank 算法及改进  31-45
  3.1 基于 MapReduce 的个性化 PageRank 算法  31-36
    3.1.1 个性化 PageRank 算法  31-32
    3.1.2 Monte Carlo 方法  32-33
    3.1.3 快速个性化 PageRank 算法  33-34
    3.1.4 单一随机游走算法  34-36
  3.2 基于 MapReduce 的个性化 PageRank 算法改进  36-44
    3.2.1 归并算法基本思想  36-38
    3.2.2 归并算法的正确性分析  38-39
    3.2.3 归并算法的迭代次数  39-41
    3.2.4 归并算法的 I/O 成本分析  41-42
    3.2.5 完全个性化 PageRank 算法  42-44
  3.3 本章小结  44-45
第4章实验验证与结果分析  45-51
  4.1 实验平台  45
  4.2 实验数据集  45
  4.3 实验拟定和评估指标  45-46
  4.4 实验结果及分析  46-49
  4.5 本章小结  49-51
结论  51-52
参考文献  52-56
攻读硕士学位期间发表的论文和取得的科研成果  56-57
致谢  57

基于MapReduce的个性化PageRank算法研究

内容摘要

全文目录

相似论文