CWYAlpha

Just another WordPress.com site

Thought this was cool: 单源最短路径BFS的Mapreduce实现

leave a comment »


不贴代码,思想在Pregel:  A System for Large-Scale Graph Processing上,包含Pagerank算法等其他图方法。

这里记录下一些启发性的东西,帮你去对一些单机算法设计新的mapreduce的实现。

Map的输入:<node ID, <dist, adj list>>,节点,目前源到节点的距离dist(初始无穷大),节点的邻居;

<A, <0, <(B, 10), (D, 5)>>>

<B, <10, <(C, 1), (D, 2)>>>

<C, <inf, <(E, 4)>>>

<D, <5, <(B, 3), (C, 9), (E, 2)>>>

<E, <inf, <(A, 7), (C, 6)>>>

Map就是在每个节点上,计算起到邻居节点的最小距离,然后把邻居节点以及节点目前的距离输出;

Map的输出:

<B, 10>  <D, 5>  也就是A到节点B距离是10,到D距离是5

<C, 11> <D, 12>

<E, inf>   C是无穷大,C到E还是无穷大

<B, 8> <C, 14> <E, 7>

<A, inf> <C, inf>

这些作为reduce的输入,然后在reduce中,对接点的值进行修改:

<A, <0, <(B, 10), (D, 5)>>>

<A, inf>

<B, <10, <(C, 1), (D, 2)>>>

<B, 10> <B, 8>

<C, <inf, <(E, 4)>>>

<C, 11> <C, 14> <C, inf>

<D, <5, <(B, 3), (C, 9), (E, 2)>>>

<D, 5> <D, 12>

<E, <inf, <(A, 7), (C, 6)>>>

<E, inf> <E, 7>

修改后作为下一轮map的输入:

<A, <0, <(B, 10), (D, 5)>>>

<B, <8, <(C, 1), (D, 2)>>>

<C, <11, <(E, 4)>>>

<D, <5, <(B, 3), (C, 9), (E, 2)>>>

<E, <7, <(A, 7), (C, 6)>>>

继续下去。。。

具体可以看ppt的介绍,我这里只是大体把思想的东西记录下来,防止以后忘了。

图是BFS,别忘了是啥样子的。

您可能也喜欢:

MapReduce与自然语言处理

Hadoop Streaming的使用

转:面试中的海量数据处理问题

分布式环境下的大规模机器学习

无觅

相关文章

from 丕子: http://www.zhizhihu.com/html/y2012/3928.html

Written by cwyalpha

九月 13, 2012 在 4:54 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: