Optimizing 2-way regular path queries in graph databases with leapfrog triejoin

Abstract

Esta tesis aborda la optimización de Consultas de Camino Regular Bidireccional (2RPQ) en grandes bases de datos de grafos, un componente crítico para extraer eficientemente infor- mación de estructuras de grafos complejas. El enfoque principal es mejorar el rendimiento de estas consultas mediante la implementación y el análisis del algoritmo Leapfrog Triejoin [19] en MillenniumDB [27]. Las 2RPQ, en particular aquellas que utilizan las que requieren cal- cular clausuras transitivas, son fundamentales en aplicaciones de grafos que van desde el análisis de redes sociales hasta la búsqueda de datos y más allá. Se proponen tres metodologías distintas: un método basado en operadores relacionales ex- tendidos (RELOP) con un operador alfa para consultas de alcanzabilidad; un método basado en Leapfrog Triejoin (LTJ) para consultas de caminos secuenciales; y un LTJ con caché LRU (LTJ CACHE) que minimiza las búsquedas redundantes en cálculos de alcanzabilidad. Estos enfoques se comparan con la implementación actual de autómatas finitos de MillenniumDB (MDB). Los resultados clave revelan que consultas de caminos específicos muestran un rendimiento superior con la implementación de LTJ CACHE, aunque la versión base MDB proporciona un mejor rendimiento promedio. Las tres metodologías propuestas en este estudio—RELOP, LTJ y LTJ CACHE—demostraron una reducción en el uso de memoria en comparación con MDB. Específicamente, RELOP y LTJ lograron disminuir el uso de memoria en 4GB cada uno, mientras que LTJ CACHE mostró un ahorro de aproximadamente 1GB a 2GB, comparado con el consumo de memoria de MDB. En las implicaciones se muestra el potencial para equilibrar la velocidad y la eficiencia de memoria en el procesamiento de consultas de grafos. Este trabajo propone una aplicación novedosa del algoritmo Leapfrog Triejoin en el ámbito de las 2RPQ dentro de una base de datos de grafos de ´ultima generación, mostrando una alternativa del enfoque estándar basado en máquinas de estado finito. El uso de un gran conjunto de datos obtenido de Wikidata con 1.200 millones de aristas muestra la aplicabilidad práctica y escalabilidad de los métodos propuestos. Futuros trabajos podrían explorar la integración de un optimizador de consultas que considere Leapfrog Triejoin como una alternativa viable para la evaluación de 2RPQ.

This thesis addresses the optimization of 2-Way Regular Path Queries (2RPQ) in large graph databases, a critical component for efficiently extracting insights from complex graph structures. The primary focus is on enhancing the performance of these queries through the implementation and analysis of the Leapfrog Triejoin algorithm [19] in MillenniumDB [27]. 2RPQs, particularly those utilizing the Kleene star operation for computing transitive closures, are pivotal in graph applications ranging from social network analysis to data search and beyond. Three distinct methodologies are explored: an extended relational operator method (RELOP) with an alpha operator for reachability queries; a Leapfrog Triejoin-based method (LTJ) for sequential path queries; and an augmented LTJ with LRU cache (LTJ CACHE) to minimize redundant searches in reachability computations. These approaches are benchmarked against MillenniumDB’s current finite automaton implementation. Key findings reveal that specific path queries show superior performance with the LTJ CACHE implementation, although the baseline MillenniumDB (MDB) provides better average performance. Significantly, all three methodologies proposed in this study—RELOP, LTJ, and LTJ CACHE—demonstrated a reduction in memory usage in comparison to MDB. Specifically, RELOP and LTJ achieved a savings of approximately 4GB each, while LTJ CACHE showed a savings of approximately 1GB to 2GB, all relative to MDB’s memory consumption. The implications of this research are significant, showcasing the potential for a trade-off between speed and memory efficiency in graph query processing. This work proposes a novel application of the Leapfrog Triejoin algorithm in the realm of 2RPQs within a state-of-theart graph database, marking a departure from the standard finite state machine approach. The use of a large dataset obtained from Wikidata with 1.2 billion edges shows the practical applicability and scalability of the proposed methods. Future work could explore the integration of a query optimizer that considers Leapfrog Triejoin as a viable alternative for 2RPQ evaluation. This thesis lays the groundwork for innovative approaches in graph database query optimization, opening avenues for enhanced efficiency and effectiveness in handling complex graph data.