pregel

zz from：http://blog.csdn.net/AE86_FC/archive/2010/08/08/5796640.aspx

（说明：Pregel的名字来历很有意思。是为了纪念欧拉的七桥问题[7]，七座桥就位于Pregel这条河上。）

Abstract
许多实际应用问题中都涉及到大型的图算法。比如网页链接关系和社会关系图等。这些图都有相同的特点：规模超大，常常达到数十亿的顶点和上万亿的边。这么大的规模，给需要在其上进行高效计算的应用提出了巨大的难题。在这篇论文中，我们将提出一种适合处理这类问题的计算模式。将程序用一系列的迭代来描述(Programs are expressed as a sequence of iterations)，在每一次迭代中，每一个顶点都能接收来自上一次迭代的信息，并将这些信息传送给下一个顶点，并在此过程中修改其自身的状态信息，以该顶点为起点的出边的状态信息，或改变整个图的拓扑结构。这种面向顶点的方法足够的灵活，可以用来描述一系列的算法。这种计算模式被设计的足够高效，可扩展，和足够的容错，并在有上千台的计算节点的集群中得以实现。这种模式中隐式的同步性(implied synchronicity)使得它对程序的确认变得简单。分布式相关的细节已经被一组抽象的API给隐藏。而展现给人们的仅仅是一个表现力很强，很容易编程的大型图算法处理的计算框架。
Keywords
分布式计算，图算法
1．Introducetion
Internet使得Web graph成为一个人们争相分析和研究的热门对象。Web 2.0更是将对社会关系网的关注推向高潮。同时还有其他的大型图对象（如交通路线图，报纸文献，疾病爆发路径，以及科学研究的发表文章中的引用关系等），也已经被研究了很多年了。同时也有了许多相应的应用算法，如最短路径算法，page rank理论演变而来的图相关算法等等。同时还有许多其他的图计算问题也有着相当的实际价值，如最小切割，以及连通分支等相关问题。
事实证明，高效的处理大型图对象的计算是一件极具挑战性的事情。图算法常常暴露出类似不高效的本地内存访问，针对每个顶点的处理过少，以及在计算过程中改变并行度等问题。分布式的介入更是加剧了locality的问题，并且加剧了在计算过程中机器发生故障而影响计算的可能性。尽管大型图形无处不在，其商业应用也非常普及，但是一种通用的，适合各种图算法的大型分布式环境的实现到目前还不存在。
要实现一种大型图计算的算法通常意味着要在以下几点中作出选择: read more

zz from:

http://blog.csdn.net/AE86_FC/archive/2010/08/08/5796640.aspx

Abstract
许多实际应用问题中都涉及到大型的图算法。比如网页链接关系和社会关系图等。这些图都有相同的特点：规模超大，常常达到数十亿的顶点和上万亿的边。这么大的规模，给需要在其上进行高效计算的应用提出了巨大的难题。在这篇论文中，我们将提出一种适合处理这类问题的计算模式。将程序用一系列的迭代来描述(Programs are expressed as a sequence of iterations)，在每一次迭代中，每一个顶点都能接收来自上一次迭代的信息，并将这些信息传送给下一个顶点，并在此过程中修改其自身的状态信息，以该顶点为起点的出边的状态信息，或改变整个图的拓扑结构。这种面向顶点的方法足够的灵活，可以用来描述一系列的算法。这种计算模式被设计的足够高效，可扩展，和足够的容错，并在有上千台的计算节点的集群中得以实现。这种模式中隐式的同步性(implied synchronicity)使得它对程序的确认变得简单。分布式相关的细节已经被一组抽象的API给隐藏。而展现给人们的仅仅是一个表现力很强，很容易编程的大型图算法处理的计算框架。
Keywords
分布式计算，图算法
1．Introducetion
Internet使得Web graph成为一个人们争相分析和研究的热门对象。Web 2.0更是将对社会关系网的关注推向高潮。同时还有其他的大型图对象（如交通路线图，报纸文献，疾病爆发路径，以及科学研究的发表文章中的引用关系等），也已经被研究了很多年了。同时也有了许多相应的应用算法，如最短路径算法，page rank理论演变而来的图相关算法等等。同时还有许多其他的图计算问题也有着相当的实际价值，如最小切割，以及连通分支等相关问题。
事实证明，高效的处理大型图对象的计算是一件极具挑战性的事情。图算法常常暴露出类似不高效的本地内存访问，针对每个顶点的处理过少，以及在计算过程中改变并行度等问题。分布式的介入更是加剧了locality的问题，并且加剧了在计算过程中机器发生故障而影响计算的可能性。尽管大型图形无处不在，其商业应用也非常普及，但是一种通用的，适合各种图算法的大型分布式环境的实现到目前还不存在。
要实现一种大型图计算的算法通常意味着要在以下几点中作出选择: read more