Rozłączne zestawy na iskierniku Apache

Question

Próbuję znaleźć algorytm wyszukiwania rozłącznych zestawów (połączonych komponentów/związków-szukania) na dużej ilości danych za pomocą iskry Apache. Problem to ilość danych. Nawet Raw reprezentacja wierzchołka wykresu nie pasuje do ram na pojedynczej maszynie. Krawędzie również nie pasują do barana.

Dane źródłowe to plik tekstowy krawędzi wykresu na hdfs: "id1 \ t id2".

id występuje jako wartość ciągu, nie int.

rozwiązanie naiwna, że ​​znalazłem to:

1. odbioru RDD krawędzi ->[id1:id2] [id3:id4] [id1:id3]
2. grupa krawędzie przez klucz. ->[id1:[id2;id3]][id3:[id4]]
3. dla każdego rekordu ustalone minimalne identyfikator każdej grupie ->(flatMap) [id1:id1][id2:id1][id3:id1][id3:id3][id4:id3]
4. odwrotnej BRD z etapu 3 [id2:id1] -> [id1:id2]
5. leftOuterJoin z ZOPS z etapu 3 i 4
6. powtarzać z etapu 2, podczas gdy wielkość BRD na krok 3 nie zmieni

Ale to prowadzi do przeniesienia dużych ilości danych pomiędzy węzłami (tasowania)

Wszelkie porady?

Answer 1

Jeśli pracujesz z wykresami chciałbym sugerujemy przyjrzeć się jednej z tych bibliotek

• GraphX
• GraphFrames

Oboje zapewniają algorytm podłączonych komponentów z pudełko.

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