apache spark上的不相交集合

Question

我试图找到使用apache spark在大量数据上搜索不相交集合（连接组件/ union-find）的算法。 问题是数据量。甚至图形顶点的原始表示也不适合在单个机器上运行。边缘也不适合公羊。

源数据是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. 反向而在RDD的大小从阶段3 [id2:id1] -> [id1:id2]
5. RDDS的leftOuterJoin RDD从阶段3和4
6. 重复从阶段2步骤3将不会改变

但是这会导致对大量数据的节点之间的传输 （改组）

有何建议？

Answer 1

如果您正在使用的图形工作，我建议你看一看这些库

• GraphX
• GraphFrames

他们都提供连接组件的算法出来的任一个盒子。

GraphX：

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

GraphFrames：

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