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()