【大数据分析分享系列】之数据库离线挖掘计算模型.pdf

【大数据分析分享系列】

之数据库离线挖掘计算模型

目录

1、以节点为中心的编程模型.......................................................................1

2、GAS编程模型............................................................................................2

3、同步执行模型............................................................................................3

4、异步执行模型............................................................................................3

对于离线挖掘类图计算而言，目前已经涌现出众多各方面表现优秀而各具特
点的实际系统，典型的比如Pregel、Giraph、Hama、PowerGraph、GraphLab、
GraphChi等。通过对这些系统的分析，我们可以归纳出离线挖掘类图计算中一
些常见的计算模型。
本节将常见的计算模型分为两类，一类是图编程模型，另一类是图计算范型。
编程模型更多地面向图计算系统的应用开发者，而计算范型则是图计算系统开发
者需要关心的问题。在本节中，关于编程模型，主要介绍以节点为中心的编程模
型及其改进版本的GAS编程模型；关于计算范型，则重点介绍同步执行模型和异
步执行模型。这几类模型已经被广泛采用在目前的大规模图挖掘系统中。
1、以节点为中心的编程模型

以节点为中心的编程模型（Vertex-CenteredProgrammingModel）首先由
Pregel系统提出，之后的绝大多数离线挖掘类大规模图计算系统都采用这个模
型作为编程模型。
对图G=(V,E)来说，以节点为中心的编程模型将图节点vertexÎV看作计算
的中心，应用开发者可以自定义一个与具体应用密切相关的节点更新函数
Function(vertex)，这个函数可以获取并改变图节点vertex及与其有关联的边
的权值，甚至可以通过增加和删除边来更改图结构。对于所有图中的节点都执行
节点更新函数Function(vertex)来对图的状态（包括节点信息和边信息）进行
转换，如此反复迭代进行，直到达到一定的停止标准为止。
典型的图节点更新函数Function(vertex)基本遵循如下逻辑。

即首先从vertex的入边和出边收集信息，对这些信息经过针对节点权值的
函数f()变换后，将计算得到的值更新vertex的权值，之后以节点的新权值和

1

边原先的权值作为输入，通过针对边的函数g()进行变换，变换后的值用来依次
更新边的权值。通过vertex的节点更新函数，来达到更新部分图状态的目的。
以节点为中心的编程模型有很强的表达能力。研究表明，很多类型的问题都
可以通过这个编程模型来进行表达，比如很多图挖掘、数据挖掘、机器学习甚至
是线性代数的问题都可以以这种编程模型来获得解决。这也是为何以图节点为中
心的编程模型大行其道的根本原因。
2、GAS编程模型

GAS模型可以看作是对以节点为中心的图计算编程模型的一种细粒度改造，
通过将计算过程进一步细分来增加计算并发性。GAS模型明确地将以节点为中心
的图计算模型的节点更新函数Function(Vertex)划分为三个连续的处理阶段：
信息收集阶段（Gather）、应用阶段（Apply）和分发阶段（Scatter）。通过这种
明确的计算阶段划分，可以使原先的一个完整计算流程细分，这样在计算过程中
可以将各个子处理阶段并发执行来进一步增加系统的并发处理性能。
这里假设当前要进行计算的节点是u，并以此为基础来说明GAS模型。
在信息收集阶段，将u节点的所有邻接节点和相连的边上的信息通过一个通
用累加函数收集起来：

通过以上三个阶段的操作，可以定义以图节点为中心的高度抽象的GAS计算
模型。在GAS模型中，节点的入边和出边在信息收集和分发阶段如何使用取决于

2

具体的应用，比如，在PageRank计算中，信息收集阶段只考虑入边信息，分发
阶段只考虑出边信息，但是在类似于Facebook的社交关系图中，如果边表达的
语义是朋友关系，那么在信息收集和分发阶段则是所有边的信息都会纳入计算范
围。
3、同步执行模型

同步执行模型是相对于异步执行模型而言的。我们知道，图计算往往需要经
过多轮迭代过程，在以节点为中心的图编程模型下，在每轮迭代过程中对