Optimizing RPQs over a compact graph representation
Non accesible ata 2024-09-07
Use este enlace para citar
http://hdl.handle.net/2183/37866Coleccións
- GI-LBD - Artigos [47]
Metadatos
Mostrar o rexistro completo do ítemTítulo
Optimizing RPQs over a compact graph representationAutor(es)
Data
2023-09-07Cita bibliográfica
Arroyuelo, D., Gómez-Brandón, A., Hogan, A. et al. Optimizing RPQs over a compact graph representation. The VLDB Journal 33, 349–374 (2024). https://doi.org/10.1007/s00778-023-00811-2
Resumo
[Absctract]: We propose techniques to evaluate regular path queries (RPQs) over labeled graphs (e.g., RDF). We apply a bit-parallel simulation of a Glushkov automaton representing the query over a ring: a compact wavelet-tree-based index of the graph. To the best of our knowledge, our approach is the first to evaluate RPQs over a compact representation of such graphs, where we show the key advantages of using Glushkov automata in this setting. Our scheme obtains optimal time, in terms of alternation complexity, for traversing the product graph. We further introduce various optimizations, such as the ability to process several automaton states and graph nodes/labels simultaneously, and to estimate relevant selectivities. Experiments show that our approach uses 3–5X
less space, and is over 5 X faster, on average, than the next best state-of-the-art system for evaluating RPQs.
Palabras chave
Regular path queries
Ring index
Succinct data structures
Graph databases
Ring index
Succinct data structures
Graph databases
Descrición
©2023 This version of the article has been accepted for publication, after
peer review and is subject to Springer Nature’s AM terms of use, but is not
the Version of Record and does not reflect post-acceptance improvements,
or any corrections. The Version of Record is available online at:
https://doi.org/10.1007/s00778-023-00811-2
Versión do editor
ISSN
1066-8888
0949-877X
0949-877X