algorithm - apache spark 上的不相交集

Question

我试图找到使用 apache spark 在大量数据上搜索不相交集(连接的组件/union-find)的算法。问题是数据量。即使是图形顶点的原始表示也不适合单机上的 ram。边缘也不适合 ram。

源数据是hdfs上图边的文本文件:“id1\t id2”。

id 以字符串值的形式出现，而不是 int。

我发现的简单解决方案是:

1. 取边的rdd -> [id1:id2] [id3:id4] [id1:id3]
2. 按键分组边缘。 -> [id1:[id2;id3]][id3:[id4]]
3. 为每个记录设置每个组的最小 id -> (flatMap) [id1:id1][id2:id1][id3:id1][id3:id3][id4:id3]
4. 从第 3 阶段反转 rdd [id2:id1] -> [id1:id2]
5. leftOuterJoin 第 3 和 4 阶段的 rdds
6. 从第 2 阶段开始重复，同时第 3 步的 rdd 大小不变

但是这样会导致节点间传输大量数据(洗牌)

有什么建议吗？

Answer 1

如果您正在使用图表，我建议您看一下这些库中的任何一个

• GraphX
• GraphFrames

它们都提供开箱即用的连通分量算法。

GraphX:

val graph: Graph = ...
val cc = graph.connectedComponents().vertices

图形框架:

val graph: GraphFrame = ...
val cc = graph.connectedComponents.run()
cc.select("id", "component").orderBy("component").show()