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

《【大数据分析分享系列】之数据库离线挖掘计算模型.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、【大数据分析分享系列】之数据库离线挖掘计算模型目录1、以节点为中心的编程模型.......................................................................12、GAS编程模型............................................................................................23、同步执行模型......................................

2、......................................................34、异步执行模型............................................................................................3对于离线挖掘类图计算而言，目前已经涌现出众多各方面表现优秀而各具特点的实际系统，典型的比如Pregel、Giraph、Hama、PowerGraph、GraphLab、GraphChi等。通过对这些系统的

3、分析，我们可以归纳出离线挖掘类图计算中一些常见的计算模型。本节将常见的计算模型分为两类，一类是图编程模型，另一类是图计算范型。编程模型更多地面向图计算系统的应用开发者，而计算范型则是图计算系统开发者需要关心的问题。在本节中，关于编程模型，主要介绍以节点为中心的编程模型及其改进版本的GAS编程模型；关于计算范型，则重点介绍同步执行模型和异步执行模型。这几类模型已经被广泛采用在目前的大规模图挖掘系统中。1、以节点为中心的编程模型以节点为中心的编程模型（Vertex-CenteredProgrammingModel）

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

5、定的停止标准为止。典型的图节点更新函数Function(vertex)基本遵循如下逻辑。即首先从vertex的入边和出边收集信息，对这些信息经过针对节点权值的函数f()变换后，将计算得到的值更新vertex的权值，之后以节点的新权值和1边原先的权值作为输入，通过针对边的函数g()进行变换，变换后的值用来依次更新边的权值。通过vertex的节点更新函数，来达到更新部分图状态的目的。以节点为中心的编程模型有很强的表达能力。研究表明，很多类型的问题都可以通过这个编程模型来进行表达，比如很多图挖掘、数据挖掘、机器学习甚

6、至是线性代数的问题都可以以这种编程模型来获得解决。这也是为何以图节点为中心的编程模型大行其道的根本原因。2、GAS编程模型GAS模型可以看作是对以节点为中心的图计算编程模型的一种细粒度改造，通过将计算过程进一步细分来增加计算并发性。GAS模型明确地将以节点为中心的图计算模型的节点更新函数Function(Vertex)划分为三个连续的处理阶段：信息收集阶段（Gather）、应用阶段（Apply）和分发阶段（Scatter）。通过这种明确的计算阶段划分，可以使原先的一个完整计算流程细分，这样在计算过程中可以将各个

7、子处理阶段并发执行来进一步增加系统的并发处理性能。这里假设当前要进行计算的节点是u，并以此为基础来说明GAS模型。在信息收集阶段，将u节点的所有邻接节点和相连的边上的信息通过一个通用累加函数收集起来：通过以上三个阶段的操作，可以定义以图节点为中心的高度抽象的GAS计算模型。在GAS模型中，节点的入边和出边在信息收集和分发阶段如何使用取决于2具体的应用，比如，在PageRank计算中，信息收集阶段只考虑入边信息，分发阶段只考虑出边信息，但是在类似于Facebook的社交关系图中，如果边表达的语义是朋友关系，那么在

8、信息收集和分发阶段则是所有边的信息都会纳入计算范围。3、同步执行模型同步执行模型是相对于异步执行模型而言的。我们知道，图计算往往需要经过多轮迭代过程，在以节点为中心的图编程模型下，在每轮迭代过程中对图节点会调用用户自定义函数Function(vertex)，这个函数会更改vertex节点及其对应边的状态，如果节点的这种状态变化在本轮迭代过程中就可以被其他节点看到并使用，也就是说变化立即