#StackBounty: #algorithm #apache-spark #mapreduce #graph-theory #disjoint-sets Disjoint sets on apache spark

Bounty: 50

I trying to find algorithm of searching disjoint sets (connected components/union-find) on large amount of data with apache spark.
Problem is amount of data. Even Raw representation of graph vertex doesn’t fit in to ram on single machine. Edges also doesn’t fit in to the ram.

Source data is text file of graph edges on hdfs: “id1 t id2”.

id present as string value, not int.

Naive solution that I found is:

  1. take rdd of edges -> [id1:id2] [id3:id4] [id1:id3]
  2. group edges by key. -> [id1:[id2;id3]][id3:[id4]]
  3. for each record set minimum id to each group -> (flatMap) [id1:id1][id2:id1][id3:id1][id3:id3][id4:id3]
  4. reverse rdd from stage 3 [id2:id1] -> [id1:id2]
  5. leftOuterJoin of rdds from stage 3 and 4
  6. repeat from stage 2 while size of rdd on step 3 wouldn’t change

But this results in the transfer of large amounts of data between nodes
(shuffling)

Any advices?


Get this bounty!!!