提纲 ·11.1图计算简介 112 Pregel简介 113 Pregel图计算模型 114 Pregel的c++AP 115 Pregell的体系结构 116 Pregel的应用实例 117 Pregel和 MapReduce实现 PageRank算法的对 118Hama的安装和使用 本PPT是如下教材的配套讲义 《大数据技术原理与应用 —概念、存储、处理、分析与应用》 (2017年2月第2版) SBN:978-7-115443304 厦门大学林子雨编著,人民邮电出版社 欢迎访问《大数据技术原理与应用》教材官方网站: http://dblab.xmu.edu.cn/post/bigdata 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu
《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 提纲 • 11.1图计算简介 • 11.2Pregel简介 • 11.3Pregel图计算模型 • 11.4Pregel的C++ API • 11.5Pregel的体系结构 • 11.6Pregel的应用实例 • 11.7 Pregel和MapReduce实现PageRank算法的对比 • 11.8 Hama的安装和使用 欢迎访问《大数据技术原理与应用》教材官方网站： http://dblab.xmu.edu.cn/post/bigdata 本PPT是如下教材的配套讲义： 《大数据技术原理与应用 ——概念、存储、处理、分析与应用》 （2017年2月第2版） ISBN:978-7-115-44330-4 厦门大学 林子雨 编著，人民邮电出版社
●11图计算简介 ·11.1.1图结构数据 ·11.1.2传统图计算解决方案的不足之处 ·11.1.3图计算通用软件 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu
《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.1 图计算简介 • 11.1.1 图结构数据 • 11.1.2 传统图计算解决方案的不足之处 • 11.1.3 图计算通用软件
●111图结构数据 许多大数据都是以大规模图或网络的形式呈现,如社交网 络、传染病传播途径、交通事故对路网的影响 ˉ许多非图结构的大数据,也常常会被转换为图模型后进行 分析 图数据结构很好地表达了数据之间的关联性 关联性计算是大数据计算的核心——通过获得数据的关联 性,可以从噪音很多的海量数据中抽取有用的信息 比如,通过为购物者之间的关系建模,就能很快找到口 味相似的用户,并为之推荐商品 或者在社交网络中,通过传播关系发现意见领袖 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu
《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn •许多大数据都是以大规模图或网络的形式呈现，如社交网 络、传染病传播途径、交通事故对路网的影响 •许多非图结构的大数据，也常常会被转换为图模型后进行 分析 •图数据结构很好地表达了数据之间的关联性 •关联性计算是大数据计算的核心——通过获得数据的关联 性，可以从噪音很多的海量数据中抽取有用的信息 –比如，通过为购物者之间的关系建模，就能很快找到口 味相似的用户，并为之推荐商品 –或者在社交网络中，通过传播关系发现意见领袖 11.1.1 图结构数据
●1121传统图计算解决方案的不足之处 很多传统的图计算算法都存在以下几个典型问题: (1)常常表现出比较差的内存访问局部性 (2)针对单个顶点的处理工作过少 (3)计算过程中伴随着并行度的改变 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu
《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.1.2 传统图计算解决方案的不足之处 很多传统的图计算算法都存在以下几个典型问题： （1）常常表现出比较差的内存访问局部性 （2）针对单个顶点的处理工作过少 （3）计算过程中伴随着并行度的改变
1112传统图计算解决方案的不足之处 针对大型图(比如社交网络和网络图)的计算问题,可能的解决方案及 其不足之处具体如下: (1)为特定的图应用定制相应的分布式实现:通用性不好 (2)基于现有的分布式计算平台进行图计算:在性能和易用性方面往 往无法达到最优 现有的并行计算框架像 MapReduce还无法满足复杂的关联性计算 MapReduce作为单输入、两阶段、粗粒度数据并行的分布式计算 框架,在表达多迭代、稀疏结构和细粒度数据时,力不从心 比如,有公司利用 MapReduce进行社交用户推荐,对于5000万注 册用户,50亿关系对,利用10台机器的集群,需要超过10个小时的 计算 (3)使用单机的图算法库:比如BGL、LEAD、 NetworkX、JDSL、 Standford GraphBase和FGL等,但是,在可以解决的问题的规模方面 具有很大的局限性 (4)使用已有的并行图计算系统:比如, Parallel bcl和 CGM Graph, 实现了很多并行图算法,但是,对大规模分布式系统非常重要的一些方 面(比如容错),无法提供较好的支持 大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu
《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.1.2 传统图计算解决方案的不足之处 针对大型图（比如社交网络和网络图）的计算问题，可能的解决方案及 其不足之处具体如下： •（1）为特定的图应用定制相应的分布式实现：通用性不好 •（2）基于现有的分布式计算平台进行图计算：在性能和易用性方面往 往无法达到最优 •现有的并行计算框架像MapReduce还无法满足复杂的关联性计算 •MapReduce作为单输入、两阶段、粗粒度数据并行的分布式计算 框架，在表达多迭代、稀疏结构和细粒度数据时，力不从心 •比如，有公司利用MapReduce进行社交用户推荐，对于5000万注 册用户，50亿关系对，利用10台机器的集群，需要超过10个小时的 计算 •（3）使用单机的图算法库：比如BGL、LEAD、NetworkX、JDSL、 Standford GraphBase和FGL等，但是，在可以解决的问题的规模方面 具有很大的局限性 •（4）使用已有的并行图计算系统：比如，Parallel BGL和CGM Graph， 实现了很多并行图算法，但是，对大规模分布式系统非常重要的一些方 面（比如容错），无法提供较好的支持