2014, Vol. 25
2. 中国人民大学 信息学院 数据仓库与商务智能实验室, 北京 100872
2. Data Warehouse and Business Intelligence Laboratory, School of Information, Renmin University of China, Beijing 100872, China
随着大数据时代来临,很多数据挖掘算法中需要处理的数据量越来越大,于是,用于处理大规模数据的分布式系统如Hadoop[1],Giraph[2]等应运而生.Hadoop作为MapReduce计算模型的开源实现,已经被广泛应用于各种大规模数据计算;Giraph是基于hadoop平台的大规模图处理框架,它提出并实现了SuperStep(超级步)的概念.
但尽管如此,大规模数据计算所需求的计算速度仍受到限制,这在很多传统的迭代算法中尤其突出.因为很多迭代算法在使用Hadoop或者Giraph实现的时候,都受到了同步计算的限制.Hadoop系统中的Map过程和Reduce过程以及Giraph中的SuperStep过程,其本质是以一次全局磁盘读写为一次迭代,而在处理海量数据时,要完成一次全局磁盘读写是相当耗时的.在整个计算期间,总有一些处理器会先于其他处理器完成分配给它的计算任务,但是为了等待全局计算,这些早已完成任务的处理器处于赋闲的状态,这就导致了大量不必要的时间开销.因此,很多迭代算法面临这样一个问题:迭代时间(尤其是迭代过程中处理器等待的时间)越来越长,计算速度越来越慢.
这些迭代算法有一个共同点,即需要根据上一次迭代计算的结果才能开始下一次迭代.在分布式系统中,每个处理器结点只处理部分数据,由于不同数据的复杂性不同,会导致不同处理器结点的计算速度不同.因此,这些传统的迭代算法需要做到同步计算:必须等到所有处理器结点都把第k-1迭代过程计算完毕后,才能开始第k次迭代.这就导致处理器在某些时候处于一种等待状态,延长了计算时间,降低了计算速度.
为了解决这一问题,本文采用了一种迭代计算方法——异步累积更新算法(asynchronous accumulative update,简称AAU算法)[3].这个方法保证了处理器结点的高效率运行,实现了异步计算机制,即不需等到所有k-1次计算都结束后才开始第k次计算,只要有新的数据被接收,处理器就一直计算,一直处于忙碌状态,减少了处理器结点的等待时间.如此,大大提高了计算速度,节省了时间开销.
P-Rank(penetrating rank)[4]是图数据管理领域中新提出的一种相似度度量方法,被用来计算网络中任意两个结点的相似性,它是SimRank[5]的扩展形式.相比于SimRank,P-Rank可以更加准确客观地衡量结点间的相似程度,因为SimRank只考虑了结点的入度信息,而P-Rank同时考虑了结点的出度和入度信息.SimRank在实际当中有很多应用,如社会网络链接预测[6]、推荐系统[7]等.同样地,P-Rank也有非常大的潜力被应用到这类系统中.因此,本文将P-Rank作为了优化研究的对象.随着大数据技术的发展,图挖掘需要处理的数据日益增大.使用MapReduce[8]等分布式模型实现大规模P-Rank迭代计算的方法,本质上是一种同步算法,其计算时间长,收敛速度慢,因此效率低下.本文从异步的角度实现了P-Rank算法,即将异步累积更新算法应用在了P-Rank上,有效地提高了计算收敛速度.
本文第2节详细介绍P-Rank定义和异步累积更新方法AAU.第3节介绍如何将P-Rank原始形式转换成AAU异步形式,并介绍两个实现P-Rank的平台——Hadoop平台和Maiter[9]平台:前者为同步计算;后者实现了AAU算法,为异步计算.第4节是实验部分,通过与传统的MapReduce方法对比,着重介绍AAU算法的精确性和快速性.第5节对全文进行总结.
1 相关工作为满足各类图数据日益增长的需求,很多基于图的分布式模型被开发出来,如Pregel[10],GraphLab[11]等.这些系统采用以顶点为中心(vertex-centric)的方式进行图数据迭代计算.Apache Giraph[2]正是Pregel的开源实现.这些以顶点为中心的系统将原始图数据划分成很多部分,然后使用vertex-centric算法进行迭代计算,易于实现,且在很多图算法中都有应用价值.但这些算法也有缺陷,如它将Data Partition(数据划分)过程隐藏起来,使得程序员在应用不同的图算法时不能进行这方面的优化,错失了很多进行算法优化的机会.
Giraph++[9]正是为解决这一问题被提出的.Giraph++也是一个分布式图数据处理模型,在Giraph的基础上实现,从以顶点为中心(vertex-centric)的计算模型转变为以图为中心(graph-centric)的计算模型,将Partition过程对用户开放,使得用户可以自定义数据划分过程,从而为算法优化提供了另一个着眼点.并且,文献[9]证明了这种计算模型比以顶点为中心的计算模型速度更快.
iMapReduce[23]是MapReduce的优化形式,MapReduce的每次迭代都要进行一次全局数据读写,而iMapReduce只需要计算开始前从DFS读取一次,计算结束后向DFS写一次,其他只需在本地进行数据更新即可,因此在数据流方面节省了运算时间.PrIter[24]从优先级迭代的角度进行MapReduce的优化,每次进行Map前要先检查数据的优先级,只有优先级高的才会优先计算,合理设置优先条件可以极大地节省计算时间.
以上这些分布式框架,从系统实现的角度给了用户进行算法优化的机会.然而,这些系统的实现机制仍然停留在同步计算的角度,不可避免具有上文提到过的同步迭代计算的缺点.
SimRank作为图数据处理领域的热点之一,在算法应用和优化层面,有基于SimRank相似连接(similarity join)查询[12, 13]和SimRank优化计算[14, 15].从计算数据规模方面,有人提出Single- Pair SimRank[16]计算,以区别于All-Pair SimRank计算.
相似度度量可以划分为两大类[17]——基于内容的度量和基于链接的度量.SimRank,PPR,Hitting time都是基于链接的相似度度量.除了上述度量之外,P-Rank[18]是SimRank的扩展,用来处理图数据类型多样的情况,同时考虑了入度和出度(SimRank只考虑了出度链接).MatchSim[19]将两个结点的最大匹配相似邻居对的平均相似度作为它们的相似度度量.SimFusion[20]和PathSim[21]用来处理异构网络上的相似度(SimRank应用在同构网络上).RoudTripRank[22]把specificity和importance结合在一起作为一种度量方式.
这些相似度优化研究一方面着眼于改进SimRank算法以提高计算速度,另一方面则着重寻找新的相似度度量方法,很少有人从实现机制上考虑进行优化,仍然通过传统的同步迭代机制进行相关研究.
而文献[3]提出的异步累积更新方法(AAU方法)正是从实现机制考虑了算法优化,提出并实现了异步计算.作者详细阐明了异步累积更新方法的内涵、使用条件、实现模型等,很多传统迭代算法都可以用这种异步方法进行异步计算,只要满足AAU方法的使用条件,都可以使用这个模型进行优化计算,本文的P-Rank便是其中之一.Maiter系统是AAU方法的实现框架,它在文献[8]里有非常详细的介绍,并且它是一个开源系统,只要用户拥有1台或者多台PC机,就可以安装本系统进行相关研究.
2 基本定义和方法介绍 2.1P-Rank定义P-Rank是新提出的用来计算对象间相似度的度量方法.P-Rank算法的核心思想包括两方面:
(1) 如果两个对象a,b被相似的对象所指向,那么a,b是相似的;
(2) 如果两个对象a,b指向了相似的对象,那么a,b是相似的.
显然,第1条就是SimRank的定义,它根据结点的入度结点计算其相似性.相比于SimRank,P-Rank增加了第2条,将结点的出度信息也考虑进来.因此,P-Rank将同时根据结点的出度信息和入度信息计算其相似性.
P-Rank通常被用于处理有向图.如果将对象看做图的顶点,对象间的关系看做一条有向边,那么这个有向图可以表示成G=áV,Eñ,其中,V是顶点的集合,E是有向边的集合.在传统的迭代方法中,P-Rank的计算式如下:
(1)
其中,
表示结点a和b在第k次迭代时的相似度;|I(a)|和|I(b)|分别是a和b的入度数;|O(a)|和|O(b)|分别是a和b的出度数;i和j分别是a和b的入度结点;m和n分别是a和b的出度结点;c是常量,l是用来设置出度信息和入度信息权重的参数,c和l取值都在区间[0, 1]中.如果a=b,那么Sab=1.
从公式(1)可以看出,áa,bñ的相似度是由a、b的入度结点对ái,jñ的相似度和a、b的出度结点对ám,nñ共同决定的.如果i®a且j®b,那么ái,jñ就会对áa,bñ产生影响;如果a®m且b®n,那么ám,nñ也会对áa,bñ产生影响.因此,可以把Sab看做是ái,jñ和ám,nñ对áa,bñ的影响值之和.
2.2 异步累积更新方法异步累积更新算法(asynchronous accumulative updates,简称AAU)由张岩峰等人[3]提出,本文在此只作简单介绍.
迭代算法的通式为vk=F(vk-1),其中,v是需要计算的数据集,F函数是需要反复执行的操作.通常,v是一个多维向量,可以写成
,代表第k次迭代计算后的结果.在很多情况下,F函数其实是一系列函数Fj的集合,每个Fj函数只负责计算向量v的第j个元素vj,即:
(2)
在分布式系统中,多个处理器并行进行计算.向量v的n个维度v1~vn被分配成几组,每组的vj由相应的处理器负责计算.从这个公式可以明显看出,只有当所有第k-1次迭代
计算结束后,才能开始第k次计算.由于不同处理器处理的数据复杂性不同,会导致某些处理器经常处于赋闲状态.为解决这一问题,AAU算法被提出.
AAU算法首先将传统迭代公式进行变型,然后再改写成可以进行异步计算的形式.
2.2.1 AAU公式在某些情况下,公式(2)可以改写为
,
其中,
表示vi在第k-1迭代中的值对vj在第k次迭代中值的影响值;Å是某种运算,满足交换律、结合律和分配率.
令
,则通过一系列变形后,公式(2)最终转化为公式(3)的形式:
(3)
其中,
表示vj在第k次迭代后的值;表示vj在第k-1次迭代后的值;
表示从第k-1次迭代到第k次迭代的变化量;
表示i的变化量Dvi对j< span style='font-family:宋体'>的变化量Dvj的影响值;Å是某种运算,具有结合律、交换律和分配率.
公式(3)可以理解为:vj每一次迭代的值,等于上一次迭代的值加上它的变化值;而vj的变化值,等于所有对j有影响的i的变化值的累加.只有i®j存在时,i才会对j产生影响.
在分布式系统中,处理器j先收集其他处理器送来的,然后根据公式(3)更新
,进而更新
公式(3)本质上还是同步形式,因为总是需要等待更新完毕后才能更新,而又需要等待其他处理器都完成计算并且把数据发送过来后才更新.因此要作进一步改变,变为异步形式:
(4)
公式(4)可以这样理解:处理器j维护两个线程——Receive线程和Update线程:
· Receive负责接收数据,累积
· Update负责更新,并向其他处理器发送相应的影响值g.每经过一段时间,处理器就执行步骤1,及时将累计到上;当步骤2计算完毕后,将归零,再重新开始新一轮receive-update过程.
从这个公式可以看到:每个处理器上的Receive和Update操作都是彼此独立的,任意一个处理器可以在任何时间进行这两种操作.因此,处理器不需等到所有k-1次计算都结束后才开始第k次计算,只要有新数据被送来,就开始计算,一直处于忙碌状态,且彼此独立,减少了等待时间.这样便实现了异步计算.
3P-Rank异步方法和实现 3.1P-Rank的异步形式AAU算法公式的使用条件有两个:
(1) 公式(2)中的迭代公式Fj可以拆分成一系列G{i,j}(x)的形式;
(2) Å运算满足结合律、交换律和分配率.
我们先来证明P-Rank公式如何满足这两个条件.
令
,则公式(1)可改写为
(1¢)
显然,写成了一系列G{i,j}(x)的形式;又是加和运算,“+”法显然满足结合律、交换律和分配率.
至此,证明了P-Rank公式满足了AAU的两个条件,即P-Rank可以使用AAU算法.下面给出如何将P-Rank公式写成可以进行异步计算的形式.
令
,则
整合后,可以写成:
(5)
公式(5)和公式(3)是对应的.进一步地,为了实现异步,再将公式(5)带入公式(4),改写为异步形式:
(6)
公式(6)即为P-Rank实现异步累积更新计算所需的形式.在本文第3.3.2节,用分布式平台Maiter实现了这种计算.
假设处理器A负责计算结点对áa,bñ的相似度.处理器A维护两个线程——Receive线程和Update线程:
· Receive负责接收数据,累积
;
· Update负责更新,并向其他处理器发送áa,bñ对其他结点对的影响值G.每经过一段时间,处理器A就执行步骤1,及时将累计到上;当步骤2计算完毕后,将归零,再重新开始新一轮receive- update过程.
由于在实验部分需要讨论P-Rank的计算时间,所以有必要确定什么时候计算终止.对于迭代公式来说,计算终止的条件就是迭代结果足够收敛,前提是迭代公式本身是收敛的.因此在本节中,我们将证明P-Rank原始公式的收敛性和P-Rank异步形式的收敛性.
3.2.1 P-Rank公式的收敛性首先引入一个数学中的收敛性定理.
定理1. 对于"x1,x2,若$0<L<1,使得f(x)满足||f(x1)-f(x2)||≤L||x1-x2||,则xk=f(xk-1)收敛.
由公式(1¢)可知:
要证明收敛,需证明每个
和
都收敛.
令
,其中,x即为Sij.则对于任意的x1,x2,有:
由于0<l,c<1,|I(a)|≥1,|I(b)|≥1,则
.而显然,0<lC<1.令L=lC,则有:
||G(x1)-G(x2)||≤L||x1-x2||.
根据定理1可知G(x)收敛,即每个都收敛.
同理,每个也都收敛.
因此,收敛.
根据公式(5)和公式(1¢),要证明收敛,需证明:当k®¥时,
.
令:
则只需证明
先证明
收敛于0.
由于0<l,c<1,|I(i)|≥1,iÎV,显然地,当k®¥时,(lc)k®0,lk-1(1-l)ck®0,…,l(1-l)k-1ck®0.
于是,
.同理,
.
为了证明AAU算法的精确性和高效性,本文采用了两个平台来实现P-Rank算法——Hadoop平台和Maiter平台.Hadoop和Maiter系统都是开源项目,其中,Hadoop系统用来实现传统迭代,Maiter系统用来实现异步累积更新.在Hadoop平台上,P-Rank被以同步方式进行计算,即按照公式(1)的逻辑,先进行k-1次迭代,等所有k-1迭代中的计算全部结束后,再开始第k次迭代.在Maiter平台中,P-Rank以异步方式进行计算,即按照公式(6)的逻辑进行累积计算.
3.3.1 Hadoop实现在Hadoop系统中,主要通过设计Map过程和Reduce过程实现P-Rank算法.根据公式(1),Map过程用来计算每个加数,Reduce过程负责求和运算.
在进行MapReduce计算前,需要对初始数据进行处理,生成结点的出入度信息文件,以便迭代过程使用.初始数据格式为
含义为存在有向边a®b.经过处理后,数据变为更为详细的出入度形式,文件格式为
其中,I(a)表示结点a的入度数,O(a)表示结点a的出度数,o,p,q表示a的入度结点列表, x,y,z表示a的出度结点列表.
此外,在进行MapReduce计算前还要进行数据初始化,目的是为Map过程提供初始计算值.根据公式(1),每个结点和其自身的相似度为1,因此,初始化文件的格式为
Map过程和Reduce过程的核心见算法1.
算法1. MapReduce实现P-Rank同步计算.
1. Iteration BEGIN
2. t=0;
3. if (t<Iteration_time) then
4. Map:
5. 输入:key=áa,bñ, value=Sab;
6. for (a的每个出度结点h)
7. for (b的每个出度结点k){
8. 计算Dhk=Sab´lC/[I(a)´I(b)]
9. }
10. for (a的每个入度结点x)
11. for (b的每个入度结点y){
12. 计算=Sab´(1-l)C/[O(a)´O(b)]
13. }
14. 输出:key=áh,kñ,value=Dhk(或key=áx,yñ,value=D'xy).
15. Reduce:
16. 输入:key=ái,jñ,value=Dij;
17. 计算Sij=Sij+Dij
18. 输出:key=ái,jñ,value=Sij.
19. t++;
20. End of if
21. END of Iteration
3.3.2 Maiter实现Maiter和Hadoop类似,也是一个分布式集群,包括一个master结点和多个worker结点,结点之间通过MPI机制进行通信.每个worker负责计算一组数据,维护公式(4)中的Receive线程和Update线程.Maiter作为Asynchronous Accumulative Update算法的实现平台被开发出来,更为详细的介绍见文献[8].
与Hadoop一样,在使用Maiter进行计算之前,需要对数据进行预处理,也需要根据初始数据生成结点的出入度信息文件.不同的是:Hadoop处理的是单结点图,采用的是vertex-centric(以顶点为中心)的计算方式;而Maiter处理的数据是结点对图,采用的是Graph-centric(以图为中心)[9]的计算方式.因此,Maiter需要的是结点对的出入度信息.
初始数据文件格式为
含义为存在有向边a®b.经过预处理后,初始数据变为结点对的出入度形式,文件格式为
文件记录包括5部分:结点对áa,bñ,结点a的出度信息(out_a:后的内容),结点b的出度信息(out_b:后的内容),结点a的入度信息(In_a:后的内容),结点b的入度信息(In_b:后的内容).
其中,x表示a的一个出度结点,|I(x)|表示结点x的入度数;m表示b的一个出度结点,|I(m)|表示结点m的入度数;y表示a的一个入度结点,|O(y)|表示结点y的出度数;n表示b的一个入度结点,|O(n)|表示结点n的出度数.
相比于Hadoop只有每个结点的出入度信息,Maiter还增加了每个出入度结点的出入度信息.从表面上看, Maiter输入信息更多更复杂了.事实上,其进行数据预处理的时间确实比hadoop略长,但是相比于整个计算过程,这些时间是非常小的,可以忽略不计.因此在接下来的实验部分中,数据预处理的时间被略去了.
Maiter的数据初始化和Hadoop类似,将每个结点和其自身的相似度初始化为1,其他结点对初始化为0.这种初始化方式的原理很简单,结点对之间的相似度是通过有向边传递的,而最初的传递源头就是每个结点自身构成的结点对.因此,Maiter的初始化文件格式为
算法2写出了使用AAU实现P-Rank算法的代码主体.需要说明的是:AAU算法已经没有了迭代的概念,只在计算过程中定期检查计算终止条件,若条件满足,则停止计算.终止条件在这里采用的是计算DS总和的方式,若DS总和足够小,说明S已经不再变化,那么可以认为S已经足够收敛了,于是计算停止.
算法2. AAU实现P-Rank异步计算.
1. Computation BEGIN
2. read data,将结点对áa,bñ的出入度信息存入statetable;
3. 初始化Sab和DSab;
4. 计算delta的总和sum_of_delta;
5. if (sum_of_delta>阈值) then
6. 计算DSab=DSab+DDab+; //执行receive
7. if (time_interval==VALUE) then //一定时间后执行update
8. 计算Sab=Sab+DSab;
9. for (a的每个出度结点h)
10. for (b的每个出度结点k){
11. 计算DDhk=DSab´lC/[I(h)´I(k)];
12. 将DDhk发送给áh,kñ所在的worker;
13. }
14. for (a的每个入度结点x)
15. for (b的每个入度结点y){
16. 计算△D'xy=DSab´(1-l)C/[O(x)´O(y)];
17. 将△D'xy发送给áx,yñ所在的worker;
18. }
19. DSab=0;
20. End of if
21. else
22. 迭代终止
23. End of if
24. END of Computation
4 实验及结果分析 4.1 实验设置本文的数据集采用真实数据集p2p-Gnuttella08,来源于http://snap.stanford.edu/data/p2p-Gnutella08.html.这个数据集是一个对等网络文件共享数据集,数据集中的结点表示主机,有向边表示主机之间的共享关系.该数据集包含6 301个结点,20 777条边.文件大小为1 000M,实际需要计算的数据量为18 170 868条P-Rank记录.
实验的运行环境为Intel酷睿2双核CPU,2G内存和Ubuntu 12.04操作系统.Hadoop版本为1.0.0,Maiter版本为0.1.Hadoop集群和Maiter集群均采用1个master结点和3个worker结点.
本节设置了2组实验:第1组实验用来比较P-Rank同步计算方式和异步计算方式的总体运行时间;第2组实验用来研究异步计算方式的性能,即随着Worker的增加,异步计算时间的变化趋势.这两组实验都是讨论计算速度.
除了速度之外,精确度也是必须考量的因素.因此,本文在第3.2节中先讨论了P-Rank异步方法的精确度,然后在第3.3节中讨论了P-Rank异步方法的速度因素.
4.2AAU方法精确度分析本节从实验的角度证明了AAU算法的精确性.表 1是传统迭代方法MapReduce和异步累积更新方法AAU对一个P-Rank例子的计算结果比较,均保留了小数点后6位.“MapReduce结果”和“AAU结果”两列表示结点对的相似度值.其中,MapReduce结果是迭代20次后的结果.事实上,在进行10次迭代后计算结果已经足够收敛,但为了使结果更加精确,迭代了20次.
|
Table 1 Comparison of the P-Rank results computed by MapReduce and AAU 表 1 MapReduce和AAU计算结果的比较 |
从表 1可以看出:使用异步方法AAU对P-Rank的计算结果几乎和MapReduce结果完全一致,二者差值在小数点后第6位才出现,有超过50%的计算结果是一样的.因此,我们有理由相信P-Rank异步方法的精确性.
4.3AAU方法计算速度分析本节中,我们将详细讨论数据量和集群规模对P-Rank异步方法计算速度的影响.
4.3.1 总体计算时间对比为了更加清晰地分析异步方法AAU和MapReduce计算P-Rank的时间,实验中把原始数据集按有向边数分成500,1 000,3 000,5 000共4个级别,这4个级别的相关数据可见表 2.事实上,在实验中,和计算时间相关的数据是表 4中“实际计算数据条数”一列,这一列表示实际需要计算相似度的结点对的数量.
|
|
Table 2 Impacts of AAU computation time by different data scales 表 2 数据量对计算时间的影响 |
需要特别说明的是MapReduce计算时间的统计:MapReduce迭代次数越多,结果越收敛;但与此同时,计算时间也逐渐延长.实验中,经过不同迭代次数的比较,我们得出结论:迭代10次后结果变化越来越小,即迭代10次的结果已经足够接近最终的收敛值.因此,为了客观评价MapReduce和AAU的计算时间,表 2中的MapReduce计算时间以迭代10次的时间作为基准.
从表 2可以看出:无论数据量大小,异步方法AAU对P-Rank的计算时间均少于同步方法MapReduce:对于数据集2~数据集4,异步方法的计算时间大约只有同步方法的一半;对于更小的数据集1,异步计算节省了三分之二的时间.
图 1和图 2可以更加直观地感受到AAU的速度优势.从图 2我们可以得出另一个信息,即随着数据量的增长,异步方法的计算时间增长也略缓于同步方法.
 | Fig. 1 Comparison of computation time by MapReduce and AAU --column chart (s)图 1 AAU和MapReduce计算时间对比(s) |
 | Fig. 2 Comparison of computation time by MapReduce and AAU --line chart (s)图 2 AAU和MapReduce计算时间对比(s) |
通过以上分析可以得出结论:P-Rank异步方法的计算速度优于同步方法,且数据量越大,这种优势越明显.
4.3.2 集群规模对计算时间的影响为了研究集群规模对AAU计算时间的影响,本实验将Maiter集群的Worker结点数分为1,2,3共3个类别.并分别用这3个类别运行了表 2中的数据,统计了不同结点计算这4个数据集的时间.统计结果见表 3.
|
|
Table 3 Impacts of computation time by different cluster scales 表 3 集群规模对AAU计算时间的影响 |
图 3(a)和图 3(b)给出了计算时间随集群数量变化的柱形图和曲线图,从中可以更加直观地看出:无论数据集的大小,随着worker结点数量的增加,异步方法AAU处理P-Rank的计算时间均处于下降趋势,这意味着计算速度在逐步提高.从图 3(b)也可以看出:处理的数据量越大,计算时间的曲线越陡,说明下降趋势越明显.通过以上分析,我们可以得出结论:集群规模越大,计算速度越快;且数据量越大,这种速度优势越明显.
 | Fig. 3 Comparison of AAU computation time with different worker numbers --column chart (s)图 3 集群规模对AAU计算时间的影响(单位:s) |
本文首先分析了传统迭代算法的缺点,即迭代过程中由于需要同步,处理器不可避免地需要等待时间.为了解决这一问题,本文引入了异步累积更新算法,实现了异步计算,节省了处理器的等待时间,提高了计算效率.阐述了如何将P-Rank应用到异步累积更新算法上,给出了P-Rank的异步形式,实现P-Rank异步形式的平台——Maiter平台,并给出了在此平台上进行P-Rank异步计算的算法.同时,为了验证AAU算法的精确性和高效性,本文也简单介绍了P-Rank在Hadoop平台上的实现,用于和AAU进行比较.最后,用两组实验证明了异步累积更新算法AAU的计算速度优于传统同步迭代算法:集群规模越大,计算速度越快;且数据量越大,这种速度优势越明显.
由于实验环境限制,本文的分布式集群只使用了3台机器,由于机器性能有限,在处理更大规模数据方面仍有所不足.因此,更大规模的数据处理.这也是我们未来研究工作的重点.
| [1] | Bu Y, B. Balazinska HM, Ernst DM. Haloop: Efficient iterative data processing on large clusters. VLDB Endowment, 2010,3(1-2): 285-296 . |
| [2] | Ching A, Kunz C. Giraph: Large-scale graph processing infrastructure on Hadoop. Hadoop Summit, 2011,6(29):2011. |
| [3] | Zhang Y, Gao Q, Gao L, Wang CR. Accelerate large-scale iterative computation through asynchronous accumulative updates. In: Proc. of the 3rd Workshop on Scientific Cloud Computing Date. ACM Press, 2012. 13-22 . |
| [4] | Jeh G, Widom J. SimRank: A measure of structural-context similarity. In: Proc. of the 8th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2002. 538-543 . |
| [5] | Liben-Nowell D, Kleinberg J. The link-prediction problem for social networks.Journal of the American Society for Information Science and Technology , 2007,58(7):1019-1031 . |
| [6] | Abbassi Z, Mirrokni VS. A recommender system based on local random walks and spectral methods. In: Proc. of the 9th WebKDD and 1st SNA-KDD 2007 Workshop on Web Mining and Social Network Analysis. ACM Press, 2007. 102-108 . |
| [7] | Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters. Communications of the ACM Press, 2004,51(1): 107-113 . |
| [8] | Zhang Y, Gao Q, Gao L, Wang C. Maiter: A message-passing distributed framework for accumulative iterative computation. Technical Report, 2012. http://rio.ecs.umass.edu/∼yzhang/maiter-full.pdf |
| [9] | Tian YY, Balmin A, Corsten SA, Tatikonda S, Mcpherson J. From “think like a vertex” to “think like a graph”. Proc. of the VLDB Endowment, 2013,7(3). |
| [10] | Malewicz G, Austern MH, Bik AJC, Dehnert JC, Horn I, Leiser N, Czajkowski G. Pregel: A system for large-scale graph processing. In: Proc. of the 2010 ACM SIGMOD Int’l Conf. on Management of Data. ACM Press, 2010.135-146 . |
| [11] | Low Y, Gonzalez J, Kyrola A, Bickson D, Guestrin C, Hellerstein JM. Distributed GraphLab: A framework for machine learning and data mining in the cloud. Proc. of the VLDB Endowment, 2012,5(8):716-727 . |
| [12] | Sun LW, Cheng R, Li X, Cheung DW, Han JW. On link-based similarity join. Proc. of the VLDB Endowment, 2011,4(11). |
| [13] | Zheng WG, Zou L, Feng YS, Chen L, Zhao DY. Efficient SimRank-based similarity join over large graphs. Proc. of the VLDB Endowment, 2013,6(7):493-504 . |
| [14] | Fujiwara Y, Nakatsuji M, Shiokawa H, Onizuka M. Efficient search algorithm for SimRank. In: Proc. of the 2013 IEEE 29th Int’l Conf. on Data Engineering (ICDE). IEEE, 2013. 589-600 . |
| [15] | Yu W, Lin X, Zhang W. Towards efficient SimRank computation on large networks. In: Proc. of the 2013 IEEE 29th Int’l Conf. on Data Engineering (ICDE). IEEE, 2013. 601-612 . |
| [16] | Li P, Liu H, Yu J X, He J, Du XY. Fast single-pair SimRank computation. In: Proc. of the SDM. 2010. 571-582. |
| [17] | Lizorkin D, Velikhov P, Grinev M, Turdakov D. Accuracy estimate and optimization techniques forSimRank computation. Proc. of the VLDB Endowment, 2008,1(1):422-433 . |
| [18] | Zhao P, Han J, Sun Y. P-Rank: A comprehensive structural similarity measure over information networks. In: Proc. of the 18th ACM Conf. on Information and Knowledge Management. ACM Press, 2009.553-562 . |
| [19] | Lin Z, Lyu MR, King I. Matchsim: A novel neighbor-based similarity measure with maximum neighborhood matching. In: Proc. of the 18th ACM Conf. on Information and Knowledge Management. ACM Press, 2009.1613-1616 . |
| [20] | Xi W, Fox EA, Fan W, Zhang BY, Chen Z, Yan J, Zhuang D. Simfusion: Measuring similarity using unified relationship matrix. In: Proc. of the 28th Annual Int’l ACM SIGIR Conf. on Research and Development in Information Retrieval. ACM Press, 2005.130-137 . |
| [21] | Sun Y, Han J, Yan X, Yu PS, Wu TY. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks. In: Proc. of the VLDB 2011. 2011. |
| [22] | Yuan F, Chang K, Chen-Chuan W, Lauw H. RoundTripRank: Graph-Based proximity with importance and specificity. In: Proc. of the ICED. 2013. 613-624. |
| [23] | Zhang YF, Gao QX, Gao LX, Wang CR. Imapreduce: A distributed computing framework for iterative computation. Journal of Grid Computing, 2012,10(1):47-68 . |
| [24] | Zhang Y, Gao Q, Gao L, Wang CR. Priter: A distributed framework for prioritized iterative computations. In: Proc. of the 2nd ACM Symp. on Cloud Computing. ACM Press, 2011. 13 . |