database - shortestpath - cypher shortest path

¿Es mejor una base de datos de gráficos para los algoritmos de rutas más cortas? (4)

Mi objetivo es escribir un algoritmo de ruta más corto para una red de carreteras.

Actualmente mi arquitectura es algo así: almaceno todos los datos en la base de datos PostgreS PostgreSQL habilitada. Hago un SELECT * FROM ways , que toma menos de 3 segundos en una tabla con 100,000 bordes (formas) y después de eso aplicaré un algoritmo de ruta más corta (Java, Ruby o cualquier cosa) al gráfico que ya reside en la memoria . La segunda operación puede tomar aproximadamente 1,5 segundos en un gráfico con 100.000 aristas.

Entonces, toma:

2-3 segundos para cargar todos los caminos de la base de datos en la memoria y crear un gráfico (los nodos se almacenan en una tabla con formas (bordes));
1-1.5 segundos para calcular una ruta más corta en un gráfico que ya está en la memoria.

Esto es muy similar a lo que pgRouting hace (que yo sepa que usa C Boost para almacenar el gráfico en la memoria), excepto que pgRouting toma alrededor de 2 segundos en total para calcular una ruta más corta en el mismo conjunto de datos (sí, es rápido, pero es una caja negra para mí, así que necesito la mía).

Pero recientemente encontré sobre las bases de datos Graph y sobre Neo4j. En su sitio afirman que "seguir haciendo estos cálculos en velocidades por debajo de segundo en gráficos de millones de carreteras y puntos de referencia hace que sea posible en muchos casos abandonar el enfoque normal de los índices de precomputación con tiendas K / V y poder poner el enrutamiento en la ruta crítica con la posibilidad de adaptarse a las condiciones de vida y construir servicios espaciales altamente personalizados y dinámicos ".

Entonces, la pregunta es: ¿será más rápida una base de datos de gráficos con mi problema particular?

El problema tiene las siguientes propiedades:

la base de datos consiste en una tabla (formas);
la única consulta a la base de datos es obtener todos los caminos en la memoria (para construir un gráfico);
No necesito escalabilidad, es decir, es probable que el gráfico no crezca.

No tengo experiencia con bases de datos "gráficas", pero a juzgar por su pregunta, tengo algunas cosas en mente.

En primer lugar, la respuesta directa será "Crear una base de datos de gráficos y hacer una comparación de rendimiento con su solución". Puede medir el uso de la memoria, el tiempo de ejecución (velocidad), la utilización de la CPU y posiblemente otras métricas. Eso le proporcionaría suficiente información para tomar su decisión.

Mi otro consejo es revisar tu método. Las tres propiedades de problema que describió (una tabla, cargando todas las rutas y sin necesidad de escalabilidad) se aplican en su dominio actual pero no en el de las bases de datos de gráficos. Es un paradigma de programación completamente diferente y es posible que tenga que ajustar y adaptar su método para adaptarse al dominio de ese tipo especial de bases de datos. No es razonable realizar un análisis de rendimiento u otro tipo de comparaciones si está aplicando su enfoque estándar en un entorno no estándar (como la base de datos de gráficos).

Recapitulación: Traduzca su problema a los términos de la base de datos de gráficos y ejemplifíquelo según corresponda. Después de hacer eso, haga una comparación de rendimiento entre las dos soluciones.

Mi apuesta es, suponiendo que hayas traducido y modelado tu problema adecuadamente para la base de datos de gráficos, te otorgará un mejor rendimiento. Su enfoque clásico de "store-read-sort" es simple pero no tan efectivo a menos que se optimice agresivamente.

Una base de datos de gráficos probablemente no cargará todos sus datos en la memoria inicialmente, pero con el tiempo, ya que los buenos están diseñados para tratar con conjuntos de datos extremadamente grandes. Sin embargo, una vez que los datos están allí, la base de datos de gráficos tiene que trabajar menos que la base de datos relacional para atravesar los enlaces. Esto se debe a que puede acceder directamente a objetos relacionados utilizando sus identidades, en lugar de tener que usar índices de árbol B y (posiblemente) una tabla de unión, por lo que debería ser más rápido una vez que los nodos y los bordes se almacenan en caché.

Ciertamente no tienes que reinventar la rueda si estás usando cualquier base de datos de gráficos, como Neo4j. Muchos algoritmos de ruta más cortos están incorporados en esto y está diseñado para manejar la complejidad en caso de que tenga que considerar la limitación de velocidad en cualquier carretera específica, camino de una vía, puntuación de una carretera, etc. ¿Cómo se mantiene al día con el rendimiento cuando sus datos crecen? veces, o, 100 veces. Teniendo en cuenta el tiempo total de cálculo de 3 segundos para 100.000 formas, puede ser en minutos para 1M formas y en Neo4j, la respuesta será en milisegundos.

El avance con las bases de datos de gráficos no es solo rendimiento, sino más bien concepto: sus algoritmos de enrutamiento tratan con gráficos relacionales únicos (es decir, gráficos donde los enlaces son del mismo tipo) mientras que con las bases de datos de gráficos tiene un gráfico de múltiples relaciones .

Esto le permite calcular la ruta más corta entre nodos que toman solo un tipo específico de borde o evitan otro tipo.

Para obtener más información, debe leer sobre el álgebra detrás del gráfico db y el concepto de tuberías.

Recomiendo encarecidamente el proyecto thinkerpop para comenzar con la base de datos de gráficos.