поиск в ширину на огромном графике с небольшим поршнем
У меня в настоящее время есть график, который имеет приблизительно 10 миллионов узлов и 35 миллионов краев. На данный момент полный график загружается в память в программе, запускаются. Это занимает несколько минут (это - Java, в конце концов), и нуждается приблизительно в половине гигабайта RAM. На данный момент это работает на машине с двухъядерным процессором и 4 гигабайта RAM.
Когда график ищется с помощью поиска в ширину, использование памяти повышается до пика одного гигабайта, и требуется десять секунд в среднем.
Я хотел бы развернуть программу на нескольких компьютерах. Функциональность кроме поиска графика действительно берет очень небольшие ресурсы. Моя целевая система является очень миниатюрной и имеет только 512 мегабайтов RAM.
Какие-либо предложения о том, как реализовать метод (вероятно, использующий базу данных) для поиска того графика, не используя слишком много памяти? Программа неактивна большую часть времени, когда она получает доступ к устройству, таким образом, новаторское могло занять приблизительно 5 минут макс. для упомянутого графика...
Спасибо за любые мысли, добавленные мое направление.
ОБНОВЛЕНИЕ:
Просто найденный neo4j. Кто-либо знает, подошло ли это для этого вида огромного графика?
2 ответа
Ваш вопрос немного расплывчатый, но в целом хорошая стратегия, которая в основном следует семантике в ширину при использовании того же объема памяти, что и поиск в глубину, - это Итеративное углубление . Идея состоит в том, что сначала вы выполняете поиск в глубину, ограниченный 1 уровнем; если не удается найти решение, начните с нуля и ограничьте его двумя уровнями; если это не удается, попробуйте 3 уровня и так далее.
Сначала это может показаться немного избыточным, но поскольку вы выполняете поиск в глубину, вы сохраняете в памяти гораздо меньше узлов и всегда выполняете поиск на один уровень меньше, чем прямой поиск в ширину. Поскольку количество узлов на уровне растет экспоненциально на больших графах, весьма вероятно, что сохранение этого одного последнего дополнительного уровня окупится за повторную попытку всех предыдущих уровней.
Я бы сказал, что Neo4j - это определенно хороший путь, когда у вас есть граф приличного размера, такой как этот. Он не только имеет встроенные алгоритмы BFS, но и сохраняет данные на диске, что сокращает время запуска.
Посмотрите это на highscalability.com: NEO4J - ГРАФИЧЕСКАЯ БАЗА ДАННЫХ, КОТОРАЯ УДИВЛЯЕТ БУТТОКСОМ
Я использовал Neo4j, и их документация очень хороша, и они предоставляют несколько хороших примеров для начала работы, которая действительно занимает всего несколько минут.
Посмотрите их руководство - Начало работы за 10 минут