Spark: построить рекурсивный путь дерева для каждого узла иерархии DataFrame - PullRequest
Новая
       19

Spark: построить рекурсивный путь дерева для каждого узла иерархии DataFrame

1 голос
/ 11 апреля 2019

Рассмотрим дерево и его представление в 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.

1 Ответ

2 голосов
/ 17 апреля 2019

Это похоже на задачу API Spark Graph. Вы можете посмотреть на Graphframes пакет свечей. Это пакет, который предоставляет высокоуровневые API через ядро ​​GraphX ​​(то же самое, что используется в традиционных Spark Dataframes через RDD). При этом вы можете создавать графики с вашими датафреймами.

Посмотрите на эту ссылку: https://mapr.com/blog/analyzing-flight-delays-with-apache-spark-graphframes-and-mapr-db/

Показывает вариант использования с данными о рейсах. Если вы посмотрите на раздел Breadth First Search Graph Algorithm, вы увидите алгоритм, который делает именно то, что вам нужно: поиск пути между двумя вершинами (с учетом параметра maxPathLength).

Запустите pyspark с зависимостями графических фреймов (в соответствии с вашей версией спарк): 

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]|
+----+------+---+------+---+------+---+
...