论文部分内容阅读
随着信息化时代的到来,各种信息以爆炸模式增长,导致图的规模日益增大。以互联网为例,近十几年来,随着互联网的普及和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到数据库)过程。