Apache Spark上的不相交集

gz5pxeao 于 2023-02-05 发布在 Apache

关注(0)|答案(2)|浏览(121)

我尝试用Apache Spark在大量数据上寻找不相交集（连通元/联合查找）的算法。问题是数据量。即使是图形顶点的原始表示也不适合单机上的RAM。边也不适合RAM。
源数据是hdfs上图形边缘的文本文件：“标识1\t标识2”。
ID作为字符串值出现，而不是整数。
我发现的简单解决方案是：
1.取边的rdd-〉[id1:id2] [id3:id4] [id1:id3]
1.按关键字对边分组。-〉[id1:[id2;id3]][id3:[id4]]
1.对于每个记录集，每个组的最小ID-〉(flatMap) [id1:id1][id2:id1][id3:id1][id3:id3][id4:id3]
1.从阶段3反向RDD [id2:id1] -> [id1:id2]
1.第3阶段和第4阶段RDD的leftOuterJoin
1.从阶段2重复，而步骤3上的rdd大小不会改变
但这会导致节点之间传输大量数据（ Shuffle ）
有什么建议吗？

apache-spark

来源：https://stackoverflow.com/questions/37297149/disjoint-sets-on-apache-spark

2条答案

按热度按时间

mzsu5hc01#

如果您正在处理图表，我建议您查看一下这些库中的任意一个

图形X
图形框架

它们都提供开箱即用的连通分量算法。

图形X：

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

图形框架：

val graph: GraphFrame = ...
val cc = graph.connectedComponents.run()
cc.select("id", "component").orderBy("component").show()

赞(0）回复(0）举报 2023-02-05

kognpnkq2#

除了@Marsellus Wallace的答案，下面的完整代码使用GraphX从边的RDD中获取不相交集。

val edges:RDD[(Long,Long)] = ???

val g = Graph.fromEdgeTuples(edges,-1L)

val disjointSets:RDD[Iterable[Long]] = g.connectedComponents()
  //Get tuples with (vertexId,parent vertexId)
  .vertices
  //Group by parent vertex Id so it aggregates the disjoint set
  .groupBy(_._2)
  .values
  .map(_.map(_._1))

赞(0）回复(0）举报 2023-02-05

我来回答

Apache Spark上的不相交集

2条答案

相关问题

热门标签

最新问答