一种基于MapReduce的分布式极图构造算法

夏 菲

（东北石油大学,大庆,163000）

一种基于MapReduce的分布式极图构造算法

夏 菲

（东北石油大学,大庆,163000）

目前，传统的单处理程序在较短的时间内并不能及时解决问题，在这种背景下，大规模的图数据处理技术成为当前计算机领域的研究前沿。在研究的过程中极图构造法作为一个重要的研究内容，引起了越来越广泛的关注。本文主要研究MapReduce基础理论知识，以及基于MapReduce的分布式极图构造算法。

MapReduce；分布式；极图构造法；设计

1 MapReduce相关理论

1.1 MapReduce

MapReduce编程模型是由谷歌工程师率先提出的，其主要运用的领域是大规模数据的并行预算。从用户的角度出发，MapReduce共分为两个最为基本的阶段分别是Map和Reduce阶段。在其中的任何一个阶段输入的都是一系列的键值对，其每一个阶段的输出的同样也是一系列的键值对，其可以用以下的公式进行表示。

1.2 MapReduce执行程序

1.MapReduce库在工作的过程中需要先将user program输入的文件进行划分，每一分都有16MB到64MB，在此基础之上使用fork将用户的进程复制到集群内的其他机器上。

2.user program的副本之中有一个master，其余都是worker，master主要负责调度，为闲置的worker分配作业。

3.被分配了Map作业的worker，开始读取对应分片的输入数据，Map作业数量是由M决定的，和split一一对应;Map作业从输入数据中抽取出键值对，每一个键值对都作为参数传递给map函数，map函数产生的中间键值对被缓存在内存中。

4.缓存的中间键值对会被定期写入本地磁盘，而且被分为R个区，R的大小是由用户定义的，将来每个区会对应一个Reduce作业;这些中间键值对的位置会被通报给master，master负责将信息转发给Reduceworker。

5.master通知分配了Reduce作业的worker它负责的分区在什么位置(肯定不止一个地方，每个Map作业产生的中间键值对都可能映射到所有R个不同分区)，当Reduceworker把所有它负责的中间键值对都读过来后，先对它们进行排序，使得相同键的键值对聚集在一起。因为不同的键可能会映射到同一个分区也就是同一个Reduce作业，所以排序是必须的。

6.reduceworker遍历排序后的中间键值对，对于每个唯一的键，都将键与关联的值传递给reduce函数，reduce函数产生的输出会添加到这个分区的输出文件中。

7.当所有的Map和Reduce作业都完成了，master唤醒正版的user program MapReduce函数调用返回userprogram的代码。

2 可行性分析

设计分布式并行算法设计一个十分有效的反法是：通过对现在固有的并行算法进行检测和拓展，并在此基础之上降之并行化。目前，对原始计算问题进行分解的方法主要有以下两种方案：第一种方案是按照计算算法的功能进行划分，被称之为功能分解。第二种方法是按照算法的数据进行划分，也被称之为域分解。第一种计算方案主要将关注的重点放在被执行计算上，比较适合计算比较复杂，但是这些计算所涉及到的数据又相互重叠的数据。第二种计算方案主要是计算程序中的数据，这些数据既包括输入数据也包括输出数据，同时还有中间结果数据，在实际应用的过程当中绝大多数算法都采用了这种方法。无论是这两种算法中的哪一种方案在使用的过程中，一个最为基本的要求是：在进行划分之后尽可能保证各个数据之间的独立性。这样每一个进行数据处理的计算任务都不会再需要其他任务之中的数据，可以明显建设任务间进行通信需求的代价。因此在设计分布式极图构造算法时,首先需要分析FCG算法中固有的并行性后再将其并行化。

在算法1阶段所处理的图像都是相互的独立的，因此不需要其他基础图就可以独立完成该图的临界图构造，在对一个基础图进行计算时计算的复杂程度也比较低。待计算的基础图集合的规模将变得愈来愈庞大,并且随着输入数据规模的膨胀,FCG算法构造出来的中间结果图的规模也会达到相应4-6倍的增长。数据膨胀相对于在阶段2中判定的构造图G'与已经生成的临界图集合中的图的同构关系带来了很严重的影响。

3 基于MapReduce的分布式极图构造算法设计

3.1 相关引理

（6）end for

（13）end for

（14）else

（15）if G is a critical graph and

（17）end if

（21）end for

（22）end if

（23）end for

（25）end while

（26）n++

（27）end while

3.2 算法设计

通过对FCG算法的研究我们可以得出，串行算法FCG是以个嵌套循环算法，第2行到27行的循环代码块(可以将之标记为代码块1)实现了构造算法的整体过程,循环构造了顶点数从6到且边数不小于N的所有临界图集合。其中第4行至6行的for循环是对输入的每一个n-1个顶点的临界图添加新顶点后得到集合的过程。而第7行至25行的while循环代码块(标记为代码块2)是对集合:中的每一个图添加与顶点vo相关联的边和删除导致出现禁止子图的其他边的过程,其算法伪代码。

（6）end for

（8）Job Begin

（12）end for

（15）Job End;

（16）n++;

（17）end while

系统在进行算法并行计算时，代码2的功能是由map函数实现的,将会由多个map函数并发的对个字输入的数据子集合中的每一个图进行临界图构造。下面以k个map与1个reduce的设计为例来说明该过程。首先将临界图集合中的图分成yt个子集。每个子集将由一个map负责,那么第个 map通过执行代码块2中的操作来生成相应的临界图集合,记作。Reduce函数主要实现了对这A个临界图子集合的合并运算,即,合并所要实现的目的是为了过滤掉这些子集中相同构造的临界图。通过一轮MapReduce过程完成了顶点数为n的临界图集合构造过程,而通过引理4可知,本次Job作业的输出结果将要作为下一轮顶点数为的临界图集合构造过程的输入数据,最后经过多轮构造得到不同顶点下的临界图集合,其中最多边数的即为所求极图集合。如上式所示,算法FCG-MR完整的体现了这个分布式极图构造的过程。从算法FCG-MR中可以看出,对于顶点数不同的图,都需要一轮MapReduce过程来实现其临界图的构造过程,而每个过程都要分为两个阶段。第一阶段处理已经被划分好的输入数据子集,对集合中的每一个图进行临界图构造,同时判同构保证了每一个输出的临界图集合中无同构的图。第二阶段的主要工作是合并每个任务所构造的临界图集合,同样要确保没有同构的图,即合并的目的就是要过滤掉那些由不同map任务产生的结果集合之间的同构图。

4 结语

近年来，随着计算机科学的快速发展，在图论研究中遇到的许多难题，越来越依靠与计算机通过算法进行解决。进行基于MapReduce分布式极图算法的研究对于利用云计算技术对图论领域的问题进行研究具有重要的研究意义。

[1]于戈,谷略,鲍玉斌,王志刚.云计算环境下的大规模图数据处理技术.计算机学报,2011(10).

[2]黄斌.许舒人.蒲卫.基于MapReduce的数据挖掘平台设计与实现[J].华中科 技大学学报(自然科学版),2011(6).

夏菲，女 出生年1990-3-21，汉，本科，黑龙江省大庆市人。

A distributed pole figure construction algorithm based on MapReduce

Xia Fei
（Daqing Petroleum Institute Daqing 163000）

At present, the traditional single handler can not solve the problem in a timely manner,in this context,a massive figure data processing technology become the research frontier in the field of computer.The pole figure construction algorithm is the important content gains more and more attention.This paper mainly studies graphs basic theoretical knowledge, as well as distributed pole figure construction algorithm based on MapReduce.

MapReduce; Distributed;pole figure construction algorithm;design

TP301.6

A