一个有向图,由(V,E)组成,其中V是顶点的集合,E为联结各顶点的边,每条边e可能有相应的权重w。
图的表示方式有两种:邻接矩阵和邻接表。其中对于节点数较少的图,用邻接矩阵表示较为方便,计算时也能充分应用矩阵计算的一些优势。但是当节点数特别大,需要借助map-reduce计算时,用邻接表是更为合适的选择。每一行数据,key为NodeId,值为与这个节点邻接的所有节点的AdjacentList(可能还包含了每一个节点的权重)。
有向图的最短路径,即从源点s出发,到达图上任意结点的最短路径。
图论中最经典的最短路径算法即Dijkstra算法,它采用了贪心的策略,利用宽度优先一层层搜索,直到遍历所有结点或已经找到最短路径。算法伪代码如下:
Dijkstra(G,w, s)
d[s] ← 0
for all vertex v ∈ V do
d[v] ← ∞
Q ← {V }
while Q != ∅ do
u ←ExtractMin(Q)
for all vertex v ∈ u.AdjacencyList do
if d[v] > d[u] + w(u, v) then
d[v] ← d[u] + w(u, v)
以下图的例子来说明这个算法:
n1为起始点。首先标记它到自已的距离为0,然后算法把所有节点(n2~n5)加入到优先队列Q中,并标记n1到这些点的距离为∞。
进入循环:
第一次迭代,从Q中取出最近的扩张点n1,找到n1的邻接点n2, n3,并更新到n2, n3的距离分别为10和5。
第二次迭代,从Q中取出最近的扩张点n3,找到n3的邻接点n2, n5, n4,这时发现n1经n3到n2的距离比直接到n2的距离要短,于是更新到n2的距离为8,到n5的距离为7,到n4的距离为14。
第三次迭代,从Q中取出最近的扩张点n5...
当所有点都搜索过后,算法终止,此时已经找到n1到各点的最短距离。
Dijkstra算法关键的一点是优先队列Q(实际实现可以用数组),它保存了全局的从源点出发最近的结点。而map-reduce则无法做到这一点(其实也不是做不到,就是比较麻烦,需要用distributed cache)。
基于map-reduce的并行算法跟Dijkstra算法有点类似,它也基于Dijkstra的迭代思想,伪代码如下:
class Mapper
method Map(nid n, node N)
d ← N.Distance
Emit(nid n,N) //Pass along graph structure [1]
for all nodeid m ∈ N.AdjacencyList do
Emit(nid m, d+w) //Emit distances to reachable nodes [2]
class Reducer
method Reduce(nid m, [d1, d2, . . .])
dmin←∞
M ← ∅
for all d ∈ counts [d1, d2, . . .] do
if IsNode(d) then
M ← d //Recover graph structure
else if d < dmin then //Look for shorter distance
dmin ← d
M.Distance← dmin //Update shortest distance
Emit(nid m, node M)
它每次迭代执行一个map-reduce job,并且只遍历一个节点。在Map中,它先输出这个节点的完整邻接节点数据,即[1]。然后遍历该节点的邻接节点,并输出该节点ID及权重。在Reduce中,对当前节点m,遍历map的输出权重,若比当前的路径值小,则更新。最后输出该节点的路径值及完整邻接节点数据,作为下一次迭代的输入。
实现上有个细节需要注意的是,map的输出有两种类型的数据:邻接节点数据和权重数据,这可以通过一个包装类,并设置一个dataType变量来实现。
当遍历完所有的节点之后,迭代就终止了。
这个实现还有一个小问题就是,不知道完整的最短路径,这可以在[2]中修改一下Map的输出来实现。
下面是一个例子,邻接节点的数据格式为: nodeId --> distance | adj1: w1, adj2: w2...
原始输入为:
n1 --> 0 | n2: 6, n3: 15, n4:20
n2 --> ∞ | n3: 5, n4:8
n3 --> ∞ | n4:2
n4 -> ∞ |
第一次迭代:
Map:
n1 --> 0 | n2: 6, n3: 15, n4:20
n2 --> ∞ | n3: 5, n4:8
n3 --> ∞ | n4:2
n4 -> ∞ |
n2 --> 6
n3 --> 15
n4 --> 20
Reduce:
n1 --> 0 | n2: 6, n3: 15, n4:20
n2 --> 6 | n3: 5, n4:8
n3 --> 15 | n4:2
n4 --> 20 |
第二次迭代:
Map:
n1 --> 0 | n2: 6, n3: 15, n4:20
n2 --> 6 | n3: 5, n4:8
n3 --> 15 | n4:2
n4 --> 20 |
n3 --> 11
n4 --> 14
Reduce:
n1 --> 0 | n2: 6, n3: 15, n4:20
n2 --> 6 | n3: 5, n4:8
n3 --> 11 | n4:2
n4 --> 14 |
第三次迭代:
Map:
n1 --> 0 | n2: 6, n3: 15, n4:20
n2 --> 6 | n3: 5, n4:8
n3 --> 11 | n4:2
n4 --> 14 |
n4 --> 13
Reduce:
n1 --> 0 | n2: 6, n3: 15, n4:20
n2 --> 6 | n3: 5, n4:8
n3 --> 11 | n4:2
n4 --> 13 |
第四次迭代:
Map:
n1 --> 0 | n2: 6, n3: 15, n4:20
n2 --> 6 | n3: 5, n4:8
n3 --> 11 | n4:2
n4 --> 13 |
Reduce:
n1 --> 0 | n2: 6, n3: 15, n4:20
n2 --> 6 | n3: 5, n4:8
n3 --> 11 | n4:2
n4 --> 13 |
迭代终止
分享到:
相关推荐
论文研究-DTCNN的人脸识别算法的Map-Reduce并行化实现研究.pdf, 传统人脸识别算法都采用基于特征提取的解决方案,所以有效的特征需要很强的先验知识和丰富的工程经验....
_Map-Reduce_并行聚类算法的研究
针对K-means算法处理海量数据存在严重的内存不足,提出利用MapReduce并行化K-means,但是普通的K均值存在收敛速度慢、易陷入局部最优和对初始聚类中心的选取等局限性,因此选择了经ACO改进过的ACO-K-means聚类算法。...
为提高智能算法在Map-Reduce作业调度问题中的求解效率, 提出一种基于改进蛙跳策略的调度算法。针对蛙跳策略在Map-Reduce作业调度中的应用, 算法具体设计了编码方案和进化算子; 同时, 为提高算法收敛性能, 对蛙跳策略...
《Ranking and Semi-supervised Classification on Large Scale Graphs Using Map-Reduce》原文及译文
Hadoop [3] is a popular open-source map-reduce im- plementation which is being used as an alternative to store and process extremely large data sets on commodity hard- ware. However, the map-reduce ...
大数据时代悄然而至,数据质量也引起人们的关注。...本文在MAP-REDUCE框架下对K-MEDOIDS聚类算法进行了改进,增强了算法的适用性和精确性,并通过仿真实验验证了在大数据环境下该算法的并行性和有效性。
基于云计算Map-Reduce模型的快速碰撞检测算法.pdf
Hadoop Map-Reduce数据分析
本文从3D模型的三个投影视图中提取了基于词袋(BOW)标准化的SIFT特征,然后使用基于Hadoop平台的分布式K-means聚类算法来计算特征向量和聚类3D模型。 为了获得精确的初始聚类中心,还提出了基于最大和最小原理的...
讲述map-reduce的实现细节文档,讲述map-reduce的学习过程中遇到的问题记忆解决办法,是很好的学习文档。
Hadoop学习总结之三:Map-Reduce入门
Map-Reduce体系架构 介绍材料,非常不错
Map-Reduce原理体系架构和工作机制,eclipse与Hadoop集群连接
采用Apache公司的Hadoop Map-Reduce框架来实现数据收集功能,并通过实验,将数据收集工作在传统的单线程模式(传统实现模式)、Hadoop伪分布模式和全分布模式下所需时间进行比较,并对执行结果进行了分析。...
Hadoop Map-Reduce教程,hadoop,mapreduce
3提取KPI数据(Map-Reduce).part2
Map-Reduce源码.png
google三大核心技术之一,map reduce的论文
Hadoop学习总结之四:Map-Reduce的过程解析