Эффективный способ построения крупномасштабного иерархического пути к дереву данных ⇐ Python

[Anonymous]

У меня есть большой набор данных (подумайте: большие данные) сетевых элементов, которые образуют древовидную сеть.
Игрушечный набор данных выглядит следующим образом:

Код: Выделить всё

|   id | type   | parent_id   |
|-----:|:-------|:------------|
|    1 | D      |         |
|    2 | C      | 1           |
|    3 | C      | 2           |
|    4 | C      | 3           |
|    5 | B      | 3           |
|    6 | B      | 4           |
|    7 | A      | 4           |
|    8 | A      | 5           |
|    9 | A      | 3           |

Важные правила:

• Корневые узлы (в игрушечном примере типа D ) и листовые узлы (в игрушечном примере типа А) не могут быть связаны друг с другом и между собой. Т. е. узел D не может быть соединен с другим узлом D (для узлов A наоборот), а узел A не может быть напрямую связан с узлом D.
• Для простоты любые другие Тип узла может быть случайным образом связан по типам.
• Глубина дерева может быть произвольной.
• Листовой узел всегда имеет тип A.
• Листовой узел не обязательно должен быть подключен через все промежуточные узлы. На самом деле существует лишь несколько промежуточных узлов, через которые необходимо пройти. В данном примере этим обстоятельством можно пренебречь.
• Если вы рекомендуете делать это в Spark, решение должно быть написано с учетом pyspark.
  < /ul>
  Я хотел бы создать эффективный способ (желательно в Spark) расчета пути к дереву для каждого узла, например:

  Код: Выделить всё

  |   id | type   | parent_id   | path                |
  |-----:|:-------|:------------|:--------------------|
  |    1 | D      |         | D:1                 |
  |    2 | C      | 1           | D:1>C:2             |
  |    3 | C      | 2           | D:1>C:2>C:3         |
  |    4 | C      | 3           | D:1>C:2>C:3>C:4     |
  |    5 | B      | 3           | D:1>C:2>C:3>B:5     |
  |    6 | B      | 4           | D:1>C:2>C:3>C:4>B:6 |
  |    7 | A      | 4           | D:1>C:2>C:3>C:4>A:7 |
  |    8 | A      | 5           | D:1>C:2>C:3>B:5>A:8 |
  |    9 | A      | 3           | D:1>C:2>C:3>A:9     |
  

  Примечание:
  Каждый элемент в дереве пути создается следующим образом: id:type.
  Если у вас есть другие эффективные способы хранения путей в дереве (например, таблицы замыканий) и их вычисления, я тоже буду рад их услышать. Однако время выполнения вычислений должно быть очень небольшим (менее часа, предпочтительно минут), а последующее извлечение должно занимать несколько секунд.
  Конечная цель — получить структура данных, которая позволяет мне эффективно агрегировать любой сетевой узел под определенным узлом (время выполнения не более нескольких секунд).
  Фактический набор данных, состоящий примерно из 3 миллионов узлов, может быть построен следующим образом. :
  Примечание:
• Комментарий node_counts, который создает показанные выше примеры игрушек.
• Распределение элементов узла близко к реальному.

Код: Выделить всё

import random
import pandas as pd
random.seed(1337)
node_counts = {'A': 1424383, 'B': 596994, 'C': 234745, 'D': 230937, 'E': 210663, 'F': 122859, 'G': 119453, 'H': 57462, 'I': 23260, 'J': 15008, 'K': 10666, 'L': 6943, 'M': 6724, 'N': 2371, 'O': 2005, 'P': 385}
#node_counts = {'A': 3, 'B': 2, 'C': 3, 'D': 1}
elements = list()
candidates = list()
root_type = list(node_counts.keys())[-1]
leaf_type = list(node_counts.keys())[0]
root_counts = node_counts[root_type]
leaves_count = node_counts[leaf_type]
ids = [i + 1 for i in range(sum(node_counts.values()))]
idcounter = 0
for i, (name, count) in enumerate(sorted(node_counts.items(), reverse=True)):
for _ in range(count):
_id = ids[idcounter]
idcounter += 1
_type = name
if i == 0:
_parent = None
else:
# select a random one that is not a root or a leaf
if len(candidates) == 0: # first bootstrap case
candidate = random.choice(elements)
else:
candidate = random.choice(candidates)
_parent = candidate['id']
_obj = {'id': _id, 'type': _type, 'parent_id': _parent}
#print(_obj)
elements.append(_obj)
if _type != root_type and _type != leaf_type:
candidates.append(_obj)
df = pd.DataFrame.from_dict(elements).astype({'parent_id': 'Int64'})

Чтобы создать путь к дереву на чистом Python с приведенными выше игрушечными данными, вы можете использовать следующую функцию:

Код: Выделить всё

def get_hierarchy_path(df, cache_dict, ID='id', LABEL = 'type', PARENT_ID = 'parent_id', node_sep='|', elem_sep=':'):
def get_path(record):
if pd.isna(record[PARENT_ID]):
return f'{record[LABEL]}{elem_sep}{record[ID]}'
else:
if record[PARENT_ID] in cache_dict:
parent_path = cache_dict[record[PARENT_ID]]
else:
try:
parent_path = get_path(df.query(f'{ID} == {record[PARENT_ID]}').iloc[0])
except IndexError as e:
print(f'Index Miss for {record[PARENT_ID]} on record {record.to_dict()}')
parent_path = f'{record[LABEL]}{elem_sep}{record[ID]}'
cache_dict[record[PARENT_ID]] = parent_path
return f"{parent_path}{node_sep}{record[LABEL]}{elem_sep}{record[ID]}"
return df.apply(get_path, axis=1)
df['path'] = get_hierarchy_path(df, dict(), node_sep='>')

Что я уже пробовал:

• Вычисления на чистом Python с помощью указанной выше функции для большого набора данных занимают меня много времени. 5,5 часов. Так что это не совсем решение. Приветствуется все, что быстрее.
• Технически используя пакет Spark Graphframes, я мог бы использовать BFS. Это дало бы мне хорошее решение для отдельных выходных узлов, но оно не масштабируется на всю сеть.
• Я думаю, что Pregel — это то, что вам нужно. Но я не знаю, как создать его в Pyspark.

Спасибо за помощь.

Подробнее здесь: https://stackoverflow.com/questions/741 ... -tree-path