Set disgiunto su scintilla apache

Question

Sto cercando di trovare un algoritmo di ricerca di set disgiunti (componenti collegati/union-find) su una grande quantità di dati con scintilla di apache. Il problema è la quantità di dati. Anche la rappresentazione Raw del vertice del grafico non si adatta alla ram su una singola macchina. Anche i bordi non si adattano alla ram.

I dati di origine sono file di testo dei bordi del grafico su hdf: "id1 \ t id2".

ID presente come valore stringa, non int.

soluzione ingenua che ho trovato è:

1. prendere RDD di spigoli ->[id1:id2] [id3:id4] [id1:id3]
2. gruppo bordi a chiave. ->[id1:[id2;id3]][id3:[id4]]
3. per ciascun record stabilito minimo id per ciascun gruppo ->(flatMap) [id1:id1][id2:id1][id3:id1][id3:id3][id4:id3]
4. inversa RDD dallo stadio 3 [id2:id1] -> [id1:id2]
5. leftOuterJoin di RDDs dallo stadio 3 e 4
6. ripetere dallo stadio 2 mentre la dimensione del RDD sulla fase 3 non cambierebbe

Ma ciò comporta il trasferimento di grandi quantità di dati tra nodi (shuffling)

Qualche consiglio?

Answer 1

Se si sta lavorando con i grafici vorrei suggerire che si prende un'occhiata a uno di queste librerie

• GraphX
• GraphFrames

Entrambi forniscono l'algoritmo di componenti collegati fuori la scatola.

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