Графическая база данных лучше для алгоритмов кратчайших путей?

Question

Моя цель - написать алгоритм кратчайшего пути для дорожной сети.

В настоящее время моя архитектура выглядит примерно так: я храню все данные в базе данных PostgreSQL с поддержкой PostGIS. Я делаю один SELECT * FROM ways, что занимает менее 3 секунд на таблице с 100 000 ребер (путями), и после этого я применяю алгоритм кратчайшего пути (на основе Java, Ruby или чего-либо еще) к графу, который уже находится в памяти. Вторая операция может занять около 1,5 секунд на графике с 100 000 ребер.

Итак, требуется:

• 2-3 секунды для загрузки всех путей из базы данных в память и создания графа (узлы хранятся в одной таблице с путями (ребрами));
• 1-1,5 секунды для расчета кратчайшего пути на графике, который уже находится в памяти.

Это очень похоже на то, что делает pgRouting (насколько мне известно, он использует C Boost для хранения графа в памяти), за исключением того, что pgRouting занимает в общей сложности около 2 секунд для вычисления кратчайшего пути для того же набора данных (да, это быстро, но это черный ящик для меня, поэтому мне нужен свой).

Но недавно я узнал о базах данных Graph и о Neo4j. На своем сайте они утверждают, что «Все еще имея возможность выполнять эти вычисления с точностью до секунды на графиках миллионов дорог и путевых точек, во многих случаях можно отказаться от обычного подхода к предварительным вычислениям индексов с K / V-хранилищами и иметь возможность поставьте маршрутизацию на критический путь с возможностью адаптации к условиям жизни и создания высоко персонализированных и динамических пространственных услуг. ".

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

Проблема имеет следующие свойства:

• база данных состоит из одной таблицы (пути);
• единственный запрос к базе данных - получить все пути в память (построить график);
• Мне не нужна масштабируемость, т. Е. Вполне вероятно, что график не будет расти.

Answer 1

Вам, конечно, не нужно заново изобретать колесо, если вы используете какую-либо графическую базу данных, например Neo4j. Многие алгоритмы кратчайшего пути встроены в него, и он разработан для того, чтобы справляться со сложностью в случае, если вам нужно учитывать ограничение скорости на любой конкретной дороге, дороге с односторонним движением, оценке дороги и т. Д. Как вы не отставаете от производительности, когда ваши данные растут 10 раз или 100 раз. Принимая во внимание ваше общее время вычислений 3 с для 100 000 способов, оно может составлять минуты для 1 М, а в Neo4j ответ будет в миллисекундах.

Answer 2

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

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

Для получения дополнительной информации выследует прочитать о алгебре, лежащей в основе графа db и концепции конвейеров.

Я настоятельно рекомендую начать проект thinkerpop с базой данных графа.

Answer 3

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

Прежде всего, простой ответ будет: "Создайте такую ​​графическую базу данных и сделайтесравнение производительности с вашим решением ".Вы можете измерить использование памяти, время выполнения (скорость), загрузку процессора и / или, возможно, другие показатели.Это даст вам достаточно данных для принятия решения.

Мой другой совет - пересмотреть ваш метод.Три описанных вами свойства проблемы (одна таблица, загрузка всех путей и отсутствие необходимости масштабирования) применяются в вашем текущем домене, но не в одном из баз данных графа.Это совершенно другая парадигма программирования, и вам, возможно, придется настроить и адаптировать свой метод в соответствии с областью этих специальных видов баз данных.Неразумно проводить сравнение производительности или любые другие виды сравнений, если вы применяете свой стандартный подход в нестандартной среде (например, в базе данных графиков).

Резюме: Переведите свою проблему в термины графикабазы данных и моделировать его соответственно.После этого сделайте сравнение производительности между двумя решениями.

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

Answer 4

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