9

我试图找到使用 apache spark 在大量数据上搜索不相交集(连接组件/联合查找)的算法。问题是数据量。甚至图形顶点的原始表示也不适合单机上的 ram。Edges 也不适合 ram。

源数据是 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. 从第 3 阶段反转 rdd[id2:id1] -> [id1:id2]
  5. leftOuterJoin来自第 3 阶段和第 4 阶段的 rdds
  6. 从第 2 阶段重复,而第 3 步中 rdd 的大小不会改变

但这会导致节点之间传输大量数据(洗牌)

有什么建议吗?

4

1 回答 1

1

如果您正在使用图表,我建议您查看这些库中的任何一个

它们都提供了开箱即用的连接组件算法。

图X

val graph: Graph = ...
val cc = graph.connectedComponents().vertices

图框

val graph: GraphFrame = ...
val cc = graph.connectedComponents.run()
cc.select("id", "component").orderBy("component").show()
于 2017-06-14T14:28:10.887 回答