纵有疾风起
人生不言弃

Hama顶点编程

Hama是基于HDFS上的BSP模型实现。 Apache Hame是Google Pregel的开源实现

  Pregel是Google提出的一个面向大规模图计算的通用编程模型。许多实际应用中都涉及到大型的图算法,典型的如网页链接关系、社交关系、地理位置图、科研论文中的引用关系等,有的图规模可达数十亿的顶点和上万亿的边。Pregel编程模型就是为了对这种大规模图进行高效计算而设计。

  Pregel的设计思想来自BSP(Bluk Synchronous Parallel)模型。BSP模型包括三部分:BSP机器模型、BSP计算模型和BSP代价模型。其中BSP计算模型采用单程序多数据(SPMD)的执行方式。BSP计算由一组处理单元和一系列连续的超级步 (superstep)组成。在每个超级步内,每个处理单元并发地执行本地计算,并向其他的处理单元发送消息。在一个超级步结束时有一个全局的同步操作。因此,可以看作本地计算-全局通信-栅栏同步模式

  具体而言,Pregel计算由一系列的迭代(即超级步)组成。在每一个超级步中,计算框架会调用顶点上的用户自定义的Compute函数,这个过程是并行执行的。Compute函数定义了在一个顶点V以及一个超级步S中需要执行的操作。该函数可以读入前一超级步S-1中发送来的消息,然后将消息发送给在下一超级步S+1中处理的其他顶点,并且在此过程中修改V的状态以及其出边的状态,或者修改图的拓扑结构。消息通过顶点的出边发送,但一个消息可以送到任何已知ID的特定顶点上去。这种计算模式非常适合分布式实现:顶点的计算是并行的;它没有限制每个超级步的执行顺序,所有的通信都仅限于S到S+1之间

  Pregel是一个以顶点为中心的计算模型,边在这种计算模式中并不是第一类对象,在边上没有相应的计算。

少点:

单向松弛模拟:对于模式图中的一个出边而言,孩子节点或孙子节点必须出现在条件集合中

    少点:如果该点不存在,则他的儿子节点必须都存在,会出现无用结果,如存在A–>B,则输出B

双向松弛模拟:将模式图的边反向,再匹配,双向匹配。

    少点:如果该点不存在,则他的儿子和父亲节点必须都存在。

应用场景:社团发现,一个团体中某些人的工作可以被上一级代替。

数据来源:Twitter,Amazon,Google

与谁比较,优势?

文章转载于:https://www.cnblogs.com/kxdblog/p/4333305.html

原著是一个有趣的人,若有侵权,请通知删除

未经允许不得转载:起风网 » Hama顶点编程

分享到: 生成海报

评论 抢沙发

评论前必须登录!

立即登录   注册

切换注册

登录

忘记密码 ?

切换登录

注册

我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活