Disjunkte Sätze auf Apache Funke

Question

Ich versuche, Algorithmus der Suche disjunkte Sätze (verbundene Komponenten/union-find) auf große Menge von Daten mit Apache Funke zu finden. Problem ist die Menge der Daten. Sogar die rohe Darstellung eines Graphenscheitelpunktes passt nicht zu einer einzelnen Maschine. Kanten passen auch nicht in den Widder.

Quelldaten sind Textdatei von Graph Kanten auf hdfs: "ID1 \ t ID2".

ID vorhanden als Zeichenfolgenwert, nicht int.

Naive Lösung, die ich gefunden ist:

1. nehmen rdd von Kanten ->[id1:id2] [id3:id4] [id1:id3]
2. Gruppe von Schlüsselkanten. ->[id1:[id2;id3]][id3:[id4]]
3. für jeden Datensatz zu jeder Gruppe mindestens id eingestellt ->(flatMap) [id1:id1][id2:id1][id3:id1][id3:id3][id4:id3]
4. Rückwärts RDD von Stufe 3 [id2:id1] -> [id1:id2]
5. leftOuterJoin von RDDs aus Stufe 3 und 4
6. Wiederholen von Stufe 2, während einer Größe von RDD auf Schritt 3 würde nicht

ändern Aber dies führt zu der Übertragung großer Datenmengen zwischen dem Knoten (shuffling)

Irgendwelche Ratschläge?

Answer 1

Wenn Sie mit Grafiken arbeiten würde ich vorschlagen, dass Sie

• GraphX
• GraphFrames

Beide bieten den angeschlossenen Komponenten Algorithmus an einer dieser Bibliotheken einen Blick aus die Kiste.

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