алгоритм/подход найти узел назначения от исходного узла ровно к ребер неориентированного графа миллиардов узлов без цикла

Question

Рассмотрим У меня есть список смежности миллиардов узлов структурирован с использованием хэш-таблицы, расположенных следующим образом:

ключа = узел источника
значение = hash_table {узел1, узел2, node3}

входные значения из текстового файла в виде
от, к
1,2
1,5
1,11
... так далее

например. ключ = '1'
значение = { '2', '5', '11'}
означает 1 соединен с узлами 2,5,11

Я хочу знать алгоритм или подход к найти узел назначения из исходного узла точно к краям в неориентированном графе миллиардов узлов без цикла

например. из узла 1 я хочу найти узел 50 только до глубины 3 или до 3 ребер.

Мое предположение, что алгоритм находит 1 - 2 - 60 - 50, который является самым коротким путем, но как бы перемещение было эффективным с использованием указанной структуры списка смежности? Я не хочу использовать Hadoop/Map Reduce.

Я придумал наивное решение, как показано ниже в Python, но неэффективно. Единственное, что хэш-таблица ищет ключ в O (1), поэтому я мог просто искать соседей и их миллиардеров соседей непосредственно для ключа. Следующий алгоритм занимает много времени.

1. начать с исходного узла
2. использовать поиск хэш-таблицы для нахождения ключ
3. идти 1 уровень глубже с хэш-таблицы соседних узлов и найти их значения для узлов назначения, пока узел не найден
4. Остановить, если узел не найдены на глубине К

& nbsp1
& NBSP & NBSP |
{2 & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp 11}
& nbsp & nbsp | & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp | & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp |
{3,6,7} {nodes} {nodes} .... подключенные узлы
& nbsp | & nbsp | & NBSP | & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp | & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp |
{nodes} {nodes} {nodes} .... миллионов подключенных узлов.

Просьба предложить. Вышеупомянутый алгоритм, подобный BFS, занимает более 3 часов для поиска всех возможных отношений ключевого значения. Может быть, это будет уменьшено с помощью другого метода поиска?

Answer 1

Как вы намекали, это будет зависеть от характеристик доступа к данным вашей системы. Если бы вы были ограничены одноэлементными обращениями, то вы действительно застряли, так как trincot наблюдает. Однако, если вы можете управлять доступом к блокам, у вас есть вероятность параллельных операций.

Однако, думаю, что, который был бы вне вашего контроля: хеш-функция владеет характеристиками смежности - и, по сути, скорее всего будет «пессимизировать» (напротив «оптимизировать») эту характеристику.

Я вижу одну возможную надежду: используйте повторение вместо рекурсии, сохраняя список узлов для посещения. Когда вы размещаете новый узел в списке, получите его хэш-значение. Если вы можете организовать узлы, кластерные по местоположению, вы, возможно, выполните передачу блоков, получив несколько значений в одной операции чтения.