Optimizing RPQs over a compact graph representation

Simple item page
dc.contributor.authorArroyuelo, Diego
dc.contributor.authorGomez-Brandon, Adrian
dc.contributor.authorHogan, Aidan
dc.contributor.authorNavarro, Gonzalo
dc.contributor.authorRojas-Ledesma, Javiel
dc.date.accessioned2025-01-20T17:11:48Z
dc.date.available2025-01-20T17:11:48Z
dc.date.issued2024
dc.description.abstractWe 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\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\times $$\end{document} less space, and is over 5x\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\times $$\end{document} faster, on average, than the next best state-of-the-art system for evaluating RPQs.
dc.fuente.origenWOS
dc.identifier.doi10.1007/s00778-023-00811-2
dc.identifier.eissn0949-877X
dc.identifier.issn1066-8888
dc.identifier.urihttps://doi.org/10.1007/s00778-023-00811-2
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/91209
dc.identifier.wosidWOS:001060741700001
dc.issue.numero2
dc.language.isoen
dc.pagina.final374
dc.pagina.inicio349
dc.revistaVldb journal
dc.rightsacceso restringido
dc.subjectRegular path queries
dc.subjectRing index
dc.subjectSuccinct data structures
dc.subjectGraph databases
dc.titleOptimizing RPQs over a compact graph representation
dc.typeartículo
dc.volumen33
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Optimizing RPQs.pdf
Size:
1.33 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas