apache-spark - Spark : build recursive tree path for every node of an hierarchy DataFrame

Question

考虑一棵树及其 DataFrame 表示(左表):

0             ┌───────┬───────┐           ┌───────┬───────┐
├──1          │   id  │ parent│           │   id  │ path  │
│  ├──2       ├───────┼───────┤           ├───────┼───────┤
│  └──3       │   5   │   0   │           │   5   │0/5    │
│     └──4    ├───────┼───────┤           ├───────┼───────┤
└──5          │   4   │   3   │           │   4   │0/1/3/4│
              ├───────┼───────┤     =>    ├───────┼───────┤
              │   3   │   1   │           │   3   │0/1/3  │
              ├───────┼───────┤           ├───────┼───────┤
              │   2   │   1   │           │   2   │0/1/2  │
              ├───────┼───────┤           ├───────┼───────┤
              │   1   │   0   │           │   1   │0/1    │
              ├───────┼───────┤           ├───────┼───────┤
              │   0   │ null  │           │   0   │0      │
              └───────┴───────┘           └───────┴───────┘

为树的每个节点(右表)获取树路径(从根开始)的最有效方法是什么？

允许使用所有可能的方法:SQL 查询、DataFrame 方法、GraphX 等。

注意:具有递归连接的经典 SQL 解决方案不适用于 Spark DataFrames。

Answer 1

这看起来像一个 Spark Graph API 任务。你可以看看图框 Spark 包。它是一个在 GraphX 核心上提供高级 API 的包(与 RDD 上的传统 Spark 数据帧中使用的相同)。有了这个，您可以使用数据框构建图形。

看这个链接:https://mapr.com/blog/analyzing-flight-delays-with-apache-spark-graphframes-and-mapr-db/

它显示了一个包含航类数据的用例。如果你看 Breadth First Search Graph Algorithm部分，您将看到一个完全符合您要求的算法:查找两个顶点之间的路径(给定 maxPathLength 参数)。

使用图形框架依赖项运行 pyspark(根据您的 Spark 版本):

pyspark --packages graphframes:graphframes:0.6.0-spark2.3-s_2.11

构建您的数据框:

df = sc.parallelize([{"id": 5, "parent": 0}, {"id": 4, "parent": 3}, {"id": 3, "parent": 1}, {"id": 2, "parent": 1}, {"id": 1, "parent": 0}, {"id": 0, "parent": None}]).toDF()

创建图表:

df_vertices = df.selectExpr("id")
df_edges = df.withColumnRenamed("id", "dst").withColumnRenamed("parent", "src")

from graphframes import GraphFrame
graph  = GraphFrame(df_vertices, df_edges)

可视化路径(例如从 0 到 4):

graph.bfs(fromExpr="id = 0",toExpr="id = 4", maxPathLength=10).show(2)

结果:

+----+------+---+------+---+------+---+
|from|    e0| v1|    e1| v2|    e2| to|
+----+------+---+------+---+------+---+
| [0]|[1, 0]|[1]|[3, 1]|[3]|[4, 3]|[4]|
+----+------+---+------+---+------+---+