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

Access note
Acceso abierto
Publication date
2024Metadata
Show full item record
Cómo citar
Hogan, Aidan
Cómo citar
Optimizing 2-way regular path queries in graph databases with leapfrog triejoin
Professor Advisor
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.
xmlui.dri2xhtml.METS-1.0.item-notadetesis.item
Tesis para optar al grado de Magíster en Ciencias, Mención Computación Memoria para optar al título de Ingeniero Civil en Computación
Patrocinador
Este trabajo ha sido parcialmente financiado por ANID Fondecyt Proyecto Regular 1221926
Identifier
URI: https://repositorio.uchile.cl/handle/2250/203859
Collections
The following license files are associated with this item: