Maiter框架介绍Maiter框架的改进Simrank算法的实现-东北大学.PPT

谢谢！ 2013.06.16 东北大学毕业设计 LOGO LOGO LOGO LOGO LOGO LOGO LOGO LOGO LOGO LOGO LOGO LOGO LOGO Maiter框架介绍及SimRank算法在Maiter上的实现 王春磊 2013.07.05 Page ? * 主要内容 Maiter框架介绍 1 Maiter框架的改进 2 Simrank算法的实现 3 性能检测及实验结果 4 Page ? * 相关技术简介-Hadoop Hadoop是应用较广，且比较通用的分布式框架，但是不能高效的解决迭代算法 Page ? * Maiter框架简介 Hadoop Maiter Maiter框架可高效的支持异步迭代 Page ? * Maiter的异步条件 Page ? * Maiter的异步迭代 Page ? * 相关技术简介-Maiter Maiter框架可高效的解决迭代算法，但是刚刚被提出，系统功能不是很完备，支持算法有限 Page ? * Maiter框架的改进 改进前Maiter的执行过程： Page ? * Maiter框架的改进 改进后Maiter的执行过程： Page ? * Maiter框架的改进 改进前Maiter提供的API： void read_data(string line, K* k, D* data) ; void init_c(const K k, V* delta) const V default_v() const void accumulate(V* a, const V b) void priority(V* pri, const V value, const V delta) ; void g_func(const V delta, const D data, vectorpairK, V*output) 改进后Maiter提供的API： void read_data(string line, K k, D data) void init_c(const K k, V delta, D data) const V default_v() const void init_v(const K k,V v,D data) void accumulate(V a, const V b) void process_delta_v(const K k, V dalta,V value, D data) void priority(V pri, const V value, const V delta) void g_func(const K k,const V delta,const V value, const D data, vectorpairK, V * output) Page ? * 异步迭代算法的实现 Page ? * Page ? * Page ? * Page ? * 性能检测及实验结果 集群硬件软件配置： CPU：INTEL CORE i3-2100 LGA-1155 接口 3MB 高速缓存 2核 虚拟4核 内存：apacer 4G-DDR3 *2 硬盘：hitachi 500G/7200RPM 主板：ASUS P8H61-I JDK：JDK1.6.0_30 系统：redhat 6.1 64bit 实验集群： Hadoop集群，0.20.2版本，1个master节点，八个worker节点 Maiter集群，2.0版本，1个master节点，八个worker节点 Page ? * 性能检测及实验结果 实验结果-运行时间： 其中pagerank算法在Maiter框架下的运行速度是在Hadoop框架下的60多倍，与作者的实验数据吻合，说明对MaiterAPI的修改没有影响Maiter的效率 Simrank 算法在100个顶点的时候，在Maiter框架下执行的速度是Hadoop框架下的35倍。500个顶点的时候是11倍。1000个顶点时是3.6倍。 Page ? * 性能检测及实验结果 实验结果-运行时间： 图中显示的是simrank算法分别在Maiter框架和Hadoop框架下随着数据集的增长运行时间的增长情况，可以看出Maiter框架下simrank算法随数据集规模增大，运行时间增的速度比Hadoop框架下慢 Page ? * 性能检测及实验结果 实验结果-通行量： 由左图可以看到，Maiter框架下simrank的通信量显著的减少了，一方面是由于MP