基于MapReduce的图算法 PDF

作者系阿里巴巴集团1688技术部普通码农

一、 概念知识介绍

Hadoop
MapReduce是一个用于处理海量数据的分布式计算框架。这个框架解决了诸如数据分布式存储、作业调度、容错、机器间通信等复杂问题,可以使没有并行
处理或者分布式计算经验的工程师,也能很轻松地写出结构简单的、应用于成百上千台机器处理大规模数据的并行分布式程序。

Hadoop
MapReduce基于“分而治之”的思想,将计算任务抽象成map和reduce两个计算过程,可以简单理解为“分散运算—归并结果”的过程。一个
MapReduce程序首先会把输入数据分割成不相关的若干键/值对(key1/value1)集合,这些键/值对会由多个map任务来并行地处理。
MapReduce会对map的输出(一些中间键/值对key2/value2集合)按照key2进行排序,排序是用memcmp的方式对key在内存中
字节数组比较后进行升序排序,并将属于同一个key2的所有value2组合在一起作为reduce任务的输入,由reduce任务计算出最终结果并输出
key3/value3。作为一个优化,同一个计算节点上的key2/value2会通过combine在本地归并。基本流程如下:

图片 1

 

Hadoop和单机程序计算流程对比:

图片 2

 

常计算任务的输入和输出都是存放在文件里的,并且这些文件被存放在Hadoop分布式文件系统HDFS(Hadoop
Distributed File
System)中,系统会尽量调度计算任务到数据所在的节点上运行,而不是尽量将数据移动到计算节点上,减少大量数据在网络中传输,尽量节省带宽消耗。

应用程序开发人员一般情况下需要关心的是图中灰色的部分,单机程序需要处理数据读取和写入、数据处理;Hadoop程序需要实现map和
reduce,而数据读取和写入、map和reduce之间的数据传输、容错处理等由Hadoop
MapReduce和HDFS自动完成。

引言

二、 开发环境搭建

Map/Reduce程序依赖Hadoop集群,另外Eclipse需要安装依赖的hadoop包。

Hadoop集群搭建:参考Hadoop
2.2.0集群搭建
http://www.linuxidc.com/Linux/2014-06/102865.htm

周末看到一篇不错的文章“Graph Twiddling in a MapReduce world”
,介绍MapReduce下一些图算法的实现。文章语言质朴,介绍很多实用图优化技巧。文章2009年发表,至今已经被引用183次,足以证明这篇文章价值。目前这篇文章网上已经有人对这篇文章做了介绍,但仅介绍了其中最简单的两个算法,对其中的所做优化,并没有做分析。为了加深对文章算法的理解,我重新对这篇文章的算法做了翻译,同时加了自己的理解,以及算法在我们工作可能涉及的应用场景。鉴于“一图胜千言”的想法,我增加大量图片,以及实际例子演化算法流程,以增强对算法的理解。

--------------------------------------分割线

Ubuntu
13.04上搭建Hadoop环境
http://www.linuxidc.com/Linux/2013-06/86106.htm

Ubuntu 12.10 +Hadoop 1.2.1版本集群配置
http://www.linuxidc.com/Linux/2013-09/90600.htm

Ubuntu上搭建Hadoop环境(单机模式+伪分布模式)
http://www.linuxidc.com/Linux/2013-01/77681.htm

Ubuntu下Hadoop环境的配置
http://www.linuxidc.com/Linux/2012-11/74539.htm

单机版搭建Hadoop环境图文教程详解
http://www.linuxidc.com/Linux/2012-02/53927.htm

Hadoop LZO 安装教程
http://www.linuxidc.com/Linux/2013-01/78397.htm

Hadoop集群上使用Lzo压缩
http://www.linuxidc.com/Linux/2012-05/60554.htm

 

介绍

1. 安装、配置Eclipse

在官网下载合适的Eclipse,将hadoop开发所依赖的插件jar包拷贝到eclipse的安装文件夹plugins下。Hadoop2.2.0开发依赖的jar包下载地址参考:

------------------------------------------分割线------------------------------------------

FTP地址:ftp://ftp1.linuxidc.com

用户名:ftp1.linuxidc.com

密码:www.linuxidc.com

在 2014年LinuxIDC.com\6月\Hadoop学习:Map&Reduce初探与小Demo实现

下载方法见
http://www.linuxidc.com/Linux/2013-10/91140.htm

------------------------------------------分割线------------------------------------------

当然也可以自己编译。

启动eclipse,选择Window—>Prefrances,若出现如下Hadoop
Map/Reduce说明插件安装成功

图片 3

MapReduce框架非常适合处理大规模的流数据,而图算法的实现一直是MapReduce的难点。已发表这方面的文章也不是特别多。根据“Graph
Twiddling in a MapReduce world”,本文详细介绍了
四个图算法的实现,分别是图节点度计算,三元环检测,四元环检测,k-桁结构(k-trusses)检测。

2. 配置DFS,主要是数据文件的输入输出管理。

Window—>Open
Perspective—>other—>Map/Reduce,显示Map/Reduce视图。点击Map/Reduce
Locations 的小象图标,新建Hadoop Location,输入如下:

图片 4

项目视图会出现DFS Location,用来管理输入、输出数据文件。

图片 5

需要配置hadoop安装文件夹:新建Map/Reduce工程单击Configure Hadoop install
direction,输入hadoop的安装路径。

图片 6

右键单击DFS
Location下的空文件夹上传一个文本文件,然后刷新,若文件出现了则说明环境配置成功。

更多详情见请继续阅读下一页的精彩内容
http://www.linuxidc.com/Linux/2014-06/102866p2.htm

图片 7

图节点度计算

度是图节点最基本的特征,在Hadoop中求节点度的方法比较简单。以图1为例,需要求其中各个节点的度。

图片 8

Hadoop算法实现非常简单,如下图2所演示

MapReduce-1:
分别以边的两个节点作为key,边作为键值输出,reducer阶段统计节点关联的边个数,同时输出边中相应节点的度;MapReduce-2:以MapReduce-1的输出作为输入,reducer阶段合并边上两个节点的度。

三元环检测

三元环检测主要思想是先查找所有开三元环(相当于三个节点形成一条链),然后一条边是否可以将这个开三元环闭合(即是否有一条边可以将链的两个端点闭合)。

这里有两个优化点,可以大大提供算法性能。
首先,为了降低计算复杂度,一个三元环,我们只输出一次。如果对三元环中节点排序(最简单的办法就是节点按字母排序),通过逆序或者旋转三元环的节点输出顺序只有一种(例如ABC,BAC,
CBA, ACB… 都可以由ABC逆序或者旋转得到)。由于这个性质,每轮mapper
reducer过程,输出时候保证节点是按顺序的。
其次,二次爆炸问题,当某一个节点度比较高的时候,那么通过这个节点边就会很多,进而形成的开三元环也会比较多(例如,节点A的度为N,那么通过节点A边有N条边,这N条边任意两条都可以形成一个开三元环,最终A节点将形成N(N-1)/2
个开三元环,当N很大时候性能会有很大影响)。一个解决办法是,使用度较小的节点为key做合并,这样数据被分散到度比较小的节点上。(结合上面的性质,三元环节点序是只有一种,所以不会出现有些三元环没找到的情况)。这两个优化点能大大提高算法性能。

我们以第一节中的图1为例,具体的hadoop算法流程如下

图见下载中的PDF

检测三元环算法包含两个MapReducer过程:

MapReducer-1

Mapper:

input: 带有度的边

output: 以边中度较小的节点为key,边为键值输出;【降低二次爆炸问题】

Reducer:

process:合并节点的开三元环;

output:输出开三元环,输出时候按三元环两端节点字母排序输出。【保证输出顺序】

相关文章

Comment ()
评论是一种美德,说点什么吧,否则我会恨你的。。。