поиск в ширину на огромном графике с небольшим бараном

Question

В настоящее время у меня есть график, который имеет около 10 миллионов узлов и 35 миллионов ребер . На данный момент полный график загружается в память при запуске программы. Это занимает пару минут (в конце концов, это Java) и требует около половины гигабайта оперативной памяти. На данный момент он работает на машине с двухъядерным процессором и 4 гигабайтами оперативной памяти.

При поиске на графике с использованием поиска в ширину использование памяти возрастает до пика в один гигабайт, и в среднем это занимает десять секунд.

Я хотел бы развернуть программу на нескольких компьютерах. Функциональность, кроме поиска по графику, занимает очень мало ресурсов. Моя целевая система очень миниатюрна и имеет всего 512 мегабайт оперативной памяти.

Любые предложения о том, как реализовать метод (возможно, с использованием базы данных) для поиска в этом графе, не занимая слишком много памяти? Программа простаивает большую часть времени, так как обращается к аппаратному устройству, поэтому поиск пути может занять максимум 5 минут для упомянутого графика ...

Спасибо за любые мысли, брошенные в моем направлении.

UPDATE:

Только что найдено neo4j . Кто-нибудь знает, подойдет ли он для такого рода огромных графов?

Answer 1

Ваш вопрос немного расплывчатый, но в целом хорошая стратегия, которая в основном следует семантике первой ширины при использовании того же объема памяти, что и поиск в глубину, равна Итеративное углубление . Идея состоит в том, что вы делаете поиск в глубину, сначала ограниченный 1 уровнем; если не удается найти решение, начните с нуля и ограничьте его 2 уровнями; если не получится, попробуйте 3 уровня и так далее.

Поначалу это может показаться несколько избыточным, но, поскольку вы выполняете поиск в глубину, вы сохраняете в памяти гораздо меньше узлов и всегда выполняете поиск на один уровень меньше, чем простой поиск в ширину. Так как количество узлов в уровне растет экспоненциально, на больших графиках очень вероятно, что сохранение этого последнего дополнительного уровня окупается за избыточное использование всех предыдущих уровней.

Answer 2

Я бы сказал, что Neo4j, безусловно, хороший путь, когда у вас есть такой приличный размерный график. Он не только имеет встроенные алгоритмы BFS, но также сохраняет ваши данные на диске, тем самым сокращая время запуска.

Проверьте это на сайте highscalability.com: NEO4J - ГРАФИЧЕСКАЯ БАЗА ДАННЫХ, КОТОРЫЕ ПИЩУТ БУТТОКС

Я использовал Neo4j, и их документация очень хорошая, и они предоставляют несколько хороших примеров для начала работы, которые действительно занимают всего несколько минут.

Ознакомьтесь с их - Начало работы за 10 минут

Answer 3

Neo4j сохраняет данные в базе данных в виде графика, он становится постоянным, и вы можете получить доступ к нему, используя Graph Traversal Api (BFS, DBS, A * Dijkstra ...) или используя язык запросов Cypher.