Блог

Главная - Вопросы по программированию - Spark: построение рекурсивного древовидного пути для каждого узла иерархического фрейма данных

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

#apache-spark #dataframe #graph #tree #hierarchy

#apache-spark #фрейм данных #График #дерево #иерархия

Вопрос:

Рассмотрим дерево и его представление фрейма данных (левая таблица):

 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-запросы, методы фрейма данных, GraphX и т. Д.

Примечание: классическое решение SQL с рекурсивными объединениями не будет работать для фреймов данных Spark.

Комментарии:

1. Я подозреваю, что GraphX был бы правильным решением, но я сомневаюсь, что это было бы очень эффективно.

2. Да, кажется, эта задача может быть решена без инициализации графика.

3. @OlegMikhailov, как насчет RDD mapPartitions ?

4. @Sai, все методы хороши, пока они эффективны

Ответ №1:

Это похоже на задачу API Spark Graph. Вы можете посмотреть на пакет spark Graphframes. Это пакет, который предоставляет высокоуровневые API-интерфейсы поверх ядра GraphX (то же самое используется в традиционных фреймах данных Spark поверх RDDS). С помощью этого вы можете строить графики с вашими фреймами данных.

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

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

Запустите pyspark с зависимостями graphframes (в соответствии с вашей версией 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]|
 ---- ------ --- ------ --- ------ ---