平 宇，向 阳，张 波，黄寅飞

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

基于MapReduce的并行PageRank算法实现

平 宇1，向 阳1，张 波2，黄寅飞3

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

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

搜索引擎；PageRank算法；MapReduce框架；并行计算；Hadoop平台

1 概述

搜索引擎是近年来海量信息数据挖掘应用领域中的一个热点。搜索引擎的研究方向主要是在爬虫机制、切词机制、索引机制、排序机制、搜索内容[1]等方面。其中，排序机制[2]一直是搜索引擎技术中的一个难点。由于传统信息检索(IR)领域的检索方法忽略了 Web上的某些特性，因此不能得到较准确的结果。

文献[3]引入了基于网页拓扑结构的网页排序算法。该算法通过分析网页中的反向链接，计算每一个网页的重要性从而进行打分。……