论文部分内容阅读
摘要： 在研究Web结构挖掘经典算法Pagerank和云计算关键技术Mapreduce的基础上，将Pagerank算法与Mapreduce编程模型结合，针对基于并行Pagerank算法运行大数据集时面临的每次迭代访问HDFS导致I/O消耗增加、每次迭代在混合阶段和排序阶段时耗过多的问题提出了两个改进算法。一个是利用矩阵分块思想的并行Pagerank改进算法；另一个是减少HDFS访问次数的并行Pagerank改进算法。最后利用Hadoop搭建云环境，在实验环境下分析了不同的BlockSize参数对于计算性能的影响。并在云环境下面向不同的Web数据集，测试了原算法和改进算法的性能。结果表明，改进后的算法分别在结果集的空间占用方面和总迭代时间方面具有一定的优越性。
关键词： 云计算； Web结构挖掘； 分布式计算； Mapreduce； Hadoop； Pagerank
中图分类号：TP391 文献标志码：A 文章编号：1006-8228(2012)10-30-04
引言
Web结构挖掘是通过研究网页之间的链接结构来发现网络的组织结构和链接关系中隐藏的知识。随着互联网的迅猛发展和快速普及，Web上蕴藏的海量信息为数据挖掘提供了无比丰富的资源，而对Web信息进行有效的知识发现具有极大的挑战性。云计算(cloud computing)是分布式处理、并行计算和网格计算的发展，或者说是这些计算机科学概念的商业实现。它是一种新兴的共享基础架构的方法，可以将巨大的系统池连接在一起以提供各种IT服务。很多因素推动了对这类环境的需求，其中包括连接设备、实时数据流、SOA的采用，以及搜索、开放协作、社会网络和移动商务等这样的Web2.0应用的急剧增长。鉴于云计算的发展前景，将相关领域的研究工作与云计算研究工作相结合是当前研究的一个热点。本文的研究工作源于上述背景，目的是对Web结构挖掘技术进行深入的学习研究，探讨Web结构挖掘中的关键算法PageRank，将Pagerank算法与云计算领域相关技术结合，改进算法，以使Web结构挖掘适应对海量数据分析与挖掘。经典的Web结构挖掘算法如Pagerank
1.1 Pagerank算法思想
Google的PageRank算法就是一种基于随机网络的检索策略。假设读者在Web上无目的浏览，其以1-d的概率沿本页面的一个链接进行访问，以d的概率输入一个随机的网址，这样不同的网页就有不同的访问率。最终，那些入链很多的网页就是流行网页。在PageRank算法中，假定网页P1…Pn有链接指向网页A，设PR(A)，PR(P1)…PR(Pn)分别表示网页A，P1…Pn的 PageRank值，参数d为一个跳转系数，介于0～1之间，通常取0.85，o(A)被定义为A的出度，则网页A的PageRank值PR(A)可由公式⑴计算得到。
1.2 Pagerank算法的不足和改进
⑴ 由于网页数量剧增导致的Web图邻接矩阵扩大，而邻接矩阵又多数是一个稀疏矩阵，造成了大量存储资源和计算资源的浪费。
⑵ 随着互联网发展，网页的信息已成为一种海量的数据，保存并计算网页链接的关系也需要通过大型的并行系统实现，并且由于Pagerank算法需要多次迭代，所以Pagerank算法的并行化也成为必然。在Pagerank的并行算法的问题上已经有许多学者进行了研究，Google提出的MapReduce分布式计算框架已经被广泛应用在了云计算平台的部署上，因此，基于开源云计算基础架构Hadoop将Pagerank算法与Mapreduce框架结合并对算法的运行效率、时空开销、即收敛性加以研究，将会对开发部署在云计算平台上的搜索引擎服务提供帮助。这也是本文研究的目的。
2 云计算与Mapreduce编程模型
2.1 云计算
云计算是新兴的技术，目前还没有标准化或规范。众多IT厂商均在连续大力投资云计算的研究，推广各自的云计算服务和产品。云计算的标准化研究、技术研究、服务产品完善以及各IT厂商的云计算技术和服务融合是一种趋势。而MapReduce是云计算的关键技术之一，最先由Google提出的分布式计算构架，它可以支持大数据量的分布式处理[3]。
2.2 Mapreduce编程模型
Mapreduce由google提出，它是一种并行编程模型。用户可利用Mapreduce将应用编程为相应的map和reduce操作，以实现应用的大规模并行化计算。
⑴ map：接收输入数据被切片产生的对，然后产生一系列中间对集，MapReduce库把具有相同key的中间value分别聚合在一起，然后发送给reduce函数。
Map过程输入输出：
3 基于Mapreduce的并行Pagerank算法研究
3.1 算法提出
⑴ 随着Web网页趋向海量，Pagerank算法会造成巨大空间和性能开销。
⑵ 基于Mapreduce原理，一方面可以解决海量Web网页存储的困难，另一方面还可将集中计算分布在集群中各节点上平摊计算消耗。
3.2 基于Mapreduce的Pagerank算法实现
Pagerank迭代阶段的map方法对输入文件中每一个行记录的目标节点序列中每个目标节点的输出为。
Mapreduce框架收集map方法的输出按每个key归类其相应value。在reduce方法中，对每个key：页面y，把其list of [partialx]中每一项加和，并带入公式⑸得到并输出每个页面新的Pagerank。把结果保存在HDFS中，用作下一次迭代。并行Pagerank算法原理如图1所示。
迭代阶段Mapper实现对每个起始点x的目标点序列生成一个与目标点对应的partialx，并为其赋值为Pagerank(x)/目标节点的数量，最后将这些partialx发送给Mapreduce框架。 迭代阶段Reducer完成对每个节点partialx的相加并计算新的Px=dPx+(1-d)，将新的Pagerank向量输出到HDFS。
算法存在的问题：
⑴ 迭代过程执行速度方面
Map过程分为读阶段、缓冲阶段和写阶段 ，Reduce过程分为混合阶段、排序阶段和约减阶段。Reduce阶段的额外性能消耗来自于混合阶段和排序阶段。当任务在排序阶段处理的key关键字越多性能消耗就越大，如果计算Pagerank的过程中将网页节点分块表示将可以在排序阶段把性能消耗降低到原来的1/分块数。
⑵ 算法总迭代次数方面
Hadoop下的并行Pagerank算法由于每次迭代需要在集群间通信和访问HDFS，达到所需收敛次数要花费大量时间。如果能够减少并行Pagerank迭代计算的次数，增加每次迭代的计算量，也就减少了与迭代次数相关的大量通信和访问HDFS的I/O操作的时间。
3.3 利用矩阵分块思想的并行Pagerank算法
⑴ 算法思想
⑵ 矩阵分块较4.2算法的优势
在时间上，Reduce阶段的额外性能消耗来自于混合阶段和排序阶段。当任务在排序阶段处理的Key关键字越多性能的消耗就越大，将块大小设为b时，Mapreduce处理的矩阵块的数量和向量块的条数就分别减少到了原来的1/b2和1/b，在第4章节两种算法的运行时间对比中也可以看到其优势。
在空间上，由于改进后的一条向量块记录可以代表之前b条向量的记录，并且如果向量块里的节点都无外链接，就无需生成此块的记录，这对于稀疏邻接矩阵可以节省很多空间。因此可以极大地减少存储中间结果时的空间消耗，在章节4将会对比两种算法生成结果的占用空间。另一方面由于生成记录的总条数减少，也就减少了内存的占用量，从而降低了在Map中因为中间信息超过缓冲区上限而Partition到本地磁盘并排序所造成的额外I/O消耗，以及Reduce过程因为待排序记录超过内存容量而溢出到磁盘上对Key进行外部排序的可能。
3.4 低迭代并行Pagerank改进算法
3.4.1 算法分析
首先要分析Pagrank算法的原始计算公式并将该公式加以递推，如公式⑶：
其中AT是公式⑶表示的矩阵的转置矩阵，Pk为第k次迭代后的如公式⑵所表示的Pagerank向量。因此希望通过初始向量P0快速推导第k次迭代的向量Pk，递推过程如下：
这里可以通过增加每次迭代Pagerank向量的计算量来达到尽量减少与迭代次数有关的集群节点间大量通信和访问HDFS的I/O操作，来加快总的并行Pagerank算法的计算速度。本文将在后面详细介绍该加速收敛过程的Mapreduce实现过程。
如公式⑸所表示，对于跨度为2的加速收敛计算P0→P2，可表示为：
3.4.2 算法实现过程
⑴ 首先要预先生成与跨度k有关的邻接矩阵(AT)…(AT)5，因此当k=2时，第一步Mapreduce过程计算AT；第二步Mapreduce过程利用第一步中的AT计算出(AT)2；第三步Mapreduce过程每次迭代都将AT、(AT)2和初始Pagerank向量作为输入文件，生成新的Pagerank向量。并在下次迭代中用新的Pagerank向量代替初始Pagrank向量，反复迭代下去直至结果收敛，如图3所示。
图3 加速收敛Mapreduce：Pagerank计算框架
⑵ “移动计算比移动数据更经济”是HDFS的特点之一。按照这一思想，应尽量避免每轮迭代后修改或移动大数据文件，而最好保持输入数据位置不变，以使要被计算的数据在所存储的位置来进行计算，这样可以消除网络的拥堵，提高系统的整体吞吐量。因此，AT、(AT)2存储在HDFS始终不随迭代改变，如图3中用Web图表示的内容。Pagerank向量相对空间占用较小，所以每次迭代结束以新Pagerank向量带取代旧值。这种实现方法充分利用了HDFS“移动计算比移动数据更经济”的思想。用于迭代计算Pagerank向量，每次迭代跨度为2，Pk→Pk+2。
首先mapper把1和2阶段的输出AT和(AT)2作为输入，每个mapper执行之前判断读入文件块的路径，如果是AT输入，则计算(1-d)e+d(1-d)ATe，针对每个目标节点Key，其Value如公式⑹：
输出结果文件就构成了新的Pagerank向量Pk+2。
最后在所有Mapreduce阶段运行完成后Run方法结束前，将新的Pagerank向量Pk+2保存在HDFS中作为静态文件删除之前保存Pk的静态文件，以便于下次迭代中的Mapper配置阶段读取。这里我们使用到了Hadoop提供的重要应用。
⑶ DistributedCache功能表示：DistributedCache可将具体应用相关的、大尺寸的、只读的文件有效地分布放置，用来放置应用程序缓存执行过程中所需的文件。DistributedCache在JobConf中通过URI或Path指定需要被缓存的文件。Mapredcue框架在作业所有任务执行之前会把必要的文件拷贝到slave节点上。它运行高效是因为每个作业的文件只拷贝一次，并且为那些没有文档的slave节点缓存文档。
3.4.3 算法的比较和扩展
4 实验分析
4.1 实验数据集
针对本次实验的目的是在云计算实验环境下测试基于Mapreduce的Pagerank算法，所以需要选取具有大容量，百万或者千万节点级别的Web图作为实验测试数据。而鉴于实验条件和实际情况很难同互联网上爬到如此海量的Web网页并把其解析为链接关系，因此我们利用了Stanford大学社会网络研究平台提供的Web图数据作为本次实验数据集。
4.2 实验平台搭建
基于Hadoop的分布式云环境可以有两种模式，一种是基于单机的Hadoop伪分布式模式，一种是Hadoop完全分布式模式。Cygwin是一个在Windows平台上运行的Linux模拟环境。由于Hadoop运行需要shell命令的支持，所以如果节点操作系统是Windows则需要先安装Cygwin。 本次实验使用Hadoop0.18.3版本，下载JDK版本jdk1.6.0_13，Hadoop的运行需要JDK的支持。开发环境是MyEclipse 6.6+IBM MapReduce eclipse plug-in。
由于实验条件有限，本实验只用了两台PC搭建云环境。在这两台PC中，我们使用PC1作为namenode和jobtracker，PC2作为Datanode和Tasktracker。配置每台机器的/etc/hosts目录，masters:192.168.10.1,slaves:192.168.10.1,192.168.10.2。在这两台机器上创建相同用户名用户，利用ssh-keygen生成PC1的密钥对，然后将其公钥拷贝至各机器home/gx/.ssh目录下的.authorized文件下，使得从PC1可以完成到各机器的无密码ssh登录。
4.3 实验结果分析
⑴ 执行时间方面
由于分块算法减少了数据条数，每条记录节省了用于表示网页节点号Integer类型记录，所以分块法相比传统方法每块节省了（块大小-1）×4byte容量。表2显示了两种算法针对不同数据集生成中间文件大小比较。
传统Pagerank算法需要将邻接矩阵存入到内存中以迭代计算Pagerank向量，而基于Mapreduce的Pagerank计算由于每次迭代都需涉及读取和写入HDFS的大量I/O操作，因此在Web图数据集比较小的相同条件下，传统方法速度上比并行方法有很大优势。但是传统方法的问题在于，对于需要保存在内存中的邻接矩阵，如果其规模达到了n×n×4byte大于内存容量的时候，程序便无法运行。对于本次实验最小31M的数据集节点数为28万，邻近矩阵内存占用了28×28×108×4byte，要远远大于32位机器所能表示的最大4GB的内存空间，因此以上数据集都无法在传统算法上运行。这也体现出了基于云计算的算法优势。
5 结束语
本文在云环境下对Web结构挖掘中Pagerank算法进行研究，针对基于Mapreduce的并行Pagerank算法运行大数据集时存在的问题提出了改进算法。实验结果表明，改进后的算法分别在结果集的空间占用和总迭代时间方面具有一定的优越性。本文的工作对于进一步研究云计算以及将相关理论应用于云计算领域具有很大的借鉴意义。
关键词： 云计算； Web结构挖掘； 分布式计算； Mapreduce； Hadoop； Pagerank
中图分类号：TP391 文献标志码：A 文章编号：1006-8228(2012)10-30-04
引言
Web结构挖掘是通过研究网页之间的链接结构来发现网络的组织结构和链接关系中隐藏的知识。随着互联网的迅猛发展和快速普及，Web上蕴藏的海量信息为数据挖掘提供了无比丰富的资源，而对Web信息进行有效的知识发现具有极大的挑战性。云计算(cloud computing)是分布式处理、并行计算和网格计算的发展，或者说是这些计算机科学概念的商业实现。它是一种新兴的共享基础架构的方法，可以将巨大的系统池连接在一起以提供各种IT服务。很多因素推动了对这类环境的需求，其中包括连接设备、实时数据流、SOA的采用，以及搜索、开放协作、社会网络和移动商务等这样的Web2.0应用的急剧增长。鉴于云计算的发展前景，将相关领域的研究工作与云计算研究工作相结合是当前研究的一个热点。本文的研究工作源于上述背景，目的是对Web结构挖掘技术进行深入的学习研究，探讨Web结构挖掘中的关键算法PageRank，将Pagerank算法与云计算领域相关技术结合，改进算法，以使Web结构挖掘适应对海量数据分析与挖掘。经典的Web结构挖掘算法如Pagerank
1.1 Pagerank算法思想
Google的PageRank算法就是一种基于随机网络的检索策略。假设读者在Web上无目的浏览，其以1-d的概率沿本页面的一个链接进行访问，以d的概率输入一个随机的网址，这样不同的网页就有不同的访问率。最终，那些入链很多的网页就是流行网页。在PageRank算法中，假定网页P1…Pn有链接指向网页A，设PR(A)，PR(P1)…PR(Pn)分别表示网页A，P1…Pn的 PageRank值，参数d为一个跳转系数，介于0～1之间，通常取0.85，o(A)被定义为A的出度，则网页A的PageRank值PR(A)可由公式⑴计算得到。
1.2 Pagerank算法的不足和改进
⑴ 由于网页数量剧增导致的Web图邻接矩阵扩大，而邻接矩阵又多数是一个稀疏矩阵，造成了大量存储资源和计算资源的浪费。
⑵ 随着互联网发展，网页的信息已成为一种海量的数据，保存并计算网页链接的关系也需要通过大型的并行系统实现，并且由于Pagerank算法需要多次迭代，所以Pagerank算法的并行化也成为必然。在Pagerank的并行算法的问题上已经有许多学者进行了研究，Google提出的MapReduce分布式计算框架已经被广泛应用在了云计算平台的部署上，因此，基于开源云计算基础架构Hadoop将Pagerank算法与Mapreduce框架结合并对算法的运行效率、时空开销、即收敛性加以研究，将会对开发部署在云计算平台上的搜索引擎服务提供帮助。这也是本文研究的目的。
2 云计算与Mapreduce编程模型
2.1 云计算
云计算是新兴的技术，目前还没有标准化或规范。众多IT厂商均在连续大力投资云计算的研究，推广各自的云计算服务和产品。云计算的标准化研究、技术研究、服务产品完善以及各IT厂商的云计算技术和服务融合是一种趋势。而MapReduce是云计算的关键技术之一，最先由Google提出的分布式计算构架，它可以支持大数据量的分布式处理[3]。
2.2 Mapreduce编程模型
Mapreduce由google提出，它是一种并行编程模型。用户可利用Mapreduce将应用编程为相应的map和reduce操作，以实现应用的大规模并行化计算。
⑴ map：接收输入数据被切片产生的
Map过程输入输出：
3 基于Mapreduce的并行Pagerank算法研究
3.1 算法提出
⑴ 随着Web网页趋向海量，Pagerank算法会造成巨大空间和性能开销。
⑵ 基于Mapreduce原理，一方面可以解决海量Web网页存储的困难，另一方面还可将集中计算分布在集群中各节点上平摊计算消耗。
3.2 基于Mapreduce的Pagerank算法实现
Pagerank迭代阶段的map方法对输入文件中每一个行记录的目标节点序列中每个目标节点的输出为
Mapreduce框架收集map方法的输出按每个key归类其相应value。在reduce方法中，对每个key：页面y，把其list of [partialx]中每一项加和，并带入公式⑸得到并输出每个页面新的Pagerank。把结果保存在HDFS中，用作下一次迭代。并行Pagerank算法原理如图1所示。
迭代阶段Mapper实现对每个起始点x的目标点序列生成一个与目标点对应的partialx，并为其赋值为Pagerank(x)/目标节点的数量，最后将这些partialx发送给Mapreduce框架。 迭代阶段Reducer完成对每个节点partialx的相加并计算新的Px=dPx+(1-d)，将新的Pagerank向量输出到HDFS。
算法存在的问题：
⑴ 迭代过程执行速度方面
Map过程分为读阶段、缓冲阶段和写阶段 ，Reduce过程分为混合阶段、排序阶段和约减阶段。Reduce阶段的额外性能消耗来自于混合阶段和排序阶段。当任务在排序阶段处理的key关键字越多性能消耗就越大，如果计算Pagerank的过程中将网页节点分块表示将可以在排序阶段把性能消耗降低到原来的1/分块数。
⑵ 算法总迭代次数方面
Hadoop下的并行Pagerank算法由于每次迭代需要在集群间通信和访问HDFS，达到所需收敛次数要花费大量时间。如果能够减少并行Pagerank迭代计算的次数，增加每次迭代的计算量，也就减少了与迭代次数相关的大量通信和访问HDFS的I/O操作的时间。
3.3 利用矩阵分块思想的并行Pagerank算法
⑴ 算法思想
⑵ 矩阵分块较4.2算法的优势
在时间上，Reduce阶段的额外性能消耗来自于混合阶段和排序阶段。当任务在排序阶段处理的Key关键字越多性能的消耗就越大，将块大小设为b时，Mapreduce处理的矩阵块的数量和向量块的条数就分别减少到了原来的1/b2和1/b，在第4章节两种算法的运行时间对比中也可以看到其优势。
在空间上，由于改进后的一条向量块记录可以代表之前b条向量的记录，并且如果向量块里的节点都无外链接，就无需生成此块的记录，这对于稀疏邻接矩阵可以节省很多空间。因此可以极大地减少存储中间结果时的空间消耗，在章节4将会对比两种算法生成结果的占用空间。另一方面由于生成记录的总条数减少，也就减少了内存的占用量，从而降低了在Map中因为中间信息超过缓冲区上限而Partition到本地磁盘并排序所造成的额外I/O消耗，以及Reduce过程因为待排序记录超过内存容量而溢出到磁盘上对Key进行外部排序的可能。
3.4 低迭代并行Pagerank改进算法
3.4.1 算法分析
首先要分析Pagrank算法的原始计算公式并将该公式加以递推，如公式⑶：
其中AT是公式⑶表示的矩阵的转置矩阵，Pk为第k次迭代后的如公式⑵所表示的Pagerank向量。因此希望通过初始向量P0快速推导第k次迭代的向量Pk，递推过程如下：
这里可以通过增加每次迭代Pagerank向量的计算量来达到尽量减少与迭代次数有关的集群节点间大量通信和访问HDFS的I/O操作，来加快总的并行Pagerank算法的计算速度。本文将在后面详细介绍该加速收敛过程的Mapreduce实现过程。
如公式⑸所表示，对于跨度为2的加速收敛计算P0→P2，可表示为：
3.4.2 算法实现过程
⑴ 首先要预先生成与跨度k有关的邻接矩阵(AT)…(AT)5，因此当k=2时，第一步Mapreduce过程计算AT；第二步Mapreduce过程利用第一步中的AT计算出(AT)2；第三步Mapreduce过程每次迭代都将AT、(AT)2和初始Pagerank向量作为输入文件，生成新的Pagerank向量。并在下次迭代中用新的Pagerank向量代替初始Pagrank向量，反复迭代下去直至结果收敛，如图3所示。
图3 加速收敛Mapreduce：Pagerank计算框架
⑵ “移动计算比移动数据更经济”是HDFS的特点之一。按照这一思想，应尽量避免每轮迭代后修改或移动大数据文件，而最好保持输入数据位置不变，以使要被计算的数据在所存储的位置来进行计算，这样可以消除网络的拥堵，提高系统的整体吞吐量。因此，AT、(AT)2存储在HDFS始终不随迭代改变，如图3中用Web图表示的内容。Pagerank向量相对空间占用较小，所以每次迭代结束以新Pagerank向量带取代旧值。这种实现方法充分利用了HDFS“移动计算比移动数据更经济”的思想。用于迭代计算Pagerank向量，每次迭代跨度为2，Pk→Pk+2。
首先mapper把1和2阶段的输出AT和(AT)2作为输入，每个mapper执行之前判断读入文件块的路径，如果是AT输入，则计算(1-d)e+d(1-d)ATe，针对每个目标节点Key，其Value如公式⑹：
输出结果文件就构成了新的Pagerank向量Pk+2。
最后在所有Mapreduce阶段运行完成后Run方法结束前，将新的Pagerank向量Pk+2保存在HDFS中作为静态文件删除之前保存Pk的静态文件，以便于下次迭代中的Mapper配置阶段读取。这里我们使用到了Hadoop提供的重要应用。
⑶ DistributedCache功能表示：DistributedCache可将具体应用相关的、大尺寸的、只读的文件有效地分布放置，用来放置应用程序缓存执行过程中所需的文件。DistributedCache在JobConf中通过URI或Path指定需要被缓存的文件。Mapredcue框架在作业所有任务执行之前会把必要的文件拷贝到slave节点上。它运行高效是因为每个作业的文件只拷贝一次，并且为那些没有文档的slave节点缓存文档。
3.4.3 算法的比较和扩展
4 实验分析
4.1 实验数据集
针对本次实验的目的是在云计算实验环境下测试基于Mapreduce的Pagerank算法，所以需要选取具有大容量，百万或者千万节点级别的Web图作为实验测试数据。而鉴于实验条件和实际情况很难同互联网上爬到如此海量的Web网页并把其解析为链接关系，因此我们利用了Stanford大学社会网络研究平台提供的Web图数据作为本次实验数据集。
4.2 实验平台搭建
基于Hadoop的分布式云环境可以有两种模式，一种是基于单机的Hadoop伪分布式模式，一种是Hadoop完全分布式模式。Cygwin是一个在Windows平台上运行的Linux模拟环境。由于Hadoop运行需要shell命令的支持，所以如果节点操作系统是Windows则需要先安装Cygwin。 本次实验使用Hadoop0.18.3版本，下载JDK版本jdk1.6.0_13，Hadoop的运行需要JDK的支持。开发环境是MyEclipse 6.6+IBM MapReduce eclipse plug-in。
由于实验条件有限，本实验只用了两台PC搭建云环境。在这两台PC中，我们使用PC1作为namenode和jobtracker，PC2作为Datanode和Tasktracker。配置每台机器的/etc/hosts目录，masters:192.168.10.1,slaves:192.168.10.1,192.168.10.2。在这两台机器上创建相同用户名用户，利用ssh-keygen生成PC1的密钥对，然后将其公钥拷贝至各机器home/gx/.ssh目录下的.authorized文件下，使得从PC1可以完成到各机器的无密码ssh登录。
4.3 实验结果分析
⑴ 执行时间方面
由于分块算法减少了数据条数，每条记录节省了用于表示网页节点号Integer类型记录，所以分块法相比传统方法每块节省了（块大小-1）×4byte容量。表2显示了两种算法针对不同数据集生成中间文件大小比较。
传统Pagerank算法需要将邻接矩阵存入到内存中以迭代计算Pagerank向量，而基于Mapreduce的Pagerank计算由于每次迭代都需涉及读取和写入HDFS的大量I/O操作，因此在Web图数据集比较小的相同条件下，传统方法速度上比并行方法有很大优势。但是传统方法的问题在于，对于需要保存在内存中的邻接矩阵，如果其规模达到了n×n×4byte大于内存容量的时候，程序便无法运行。对于本次实验最小31M的数据集节点数为28万，邻近矩阵内存占用了28×28×108×4byte，要远远大于32位机器所能表示的最大4GB的内存空间，因此以上数据集都无法在传统算法上运行。这也体现出了基于云计算的算法优势。
5 结束语
本文在云环境下对Web结构挖掘中Pagerank算法进行研究，针对基于Mapreduce的并行Pagerank算法运行大数据集时存在的问题提出了改进算法。实验结果表明，改进后的算法分别在结果集的空间占用和总迭代时间方面具有一定的优越性。本文的工作对于进一步研究云计算以及将相关理论应用于云计算领域具有很大的借鉴意义。