Mostrar o rexistro simple do ítem
Optimizing RPQs over a compact graph representation
dc.contributor.author | Arroyuelo, Diego | |
dc.contributor.author | Gómez-Brandón, Adrián | |
dc.contributor.author | Hogan, Aidan | |
dc.contributor.author | Navarro, Gonzalo | |
dc.contributor.author | Rojas-Ledesma, Javiel | |
dc.date.accessioned | 2024-07-10T10:05:12Z | |
dc.date.issued | 2023-09-07 | |
dc.identifier.citation | 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 | es_ES |
dc.identifier.issn | 1066-8888 | |
dc.identifier.issn | 0949-877X | |
dc.identifier.uri | http://hdl.handle.net/2183/37866 | |
dc.description | ©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 | es_ES |
dc.description.abstract | [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. | es_ES |
dc.description.sponsorship | This work was supported by ANID—Millennium Science Initiative Program—Code ICN17_002; Fondecyt Grant 1-230755; Fondecyt Grants 1221926 and 1-200038; Xunta de Galicia, FEDER Galicia 2014-2020 80%, SXU 20% Grant ED431G 2019/01; GAIN/Xunta de Galicia Grant ED431C 2021/53 (GRC); Xunta de Galicia/FEDER-UE Grant IN852D 2021/3; Ministerio de Ciencia e Innovación Grants PID2020-114635RB-I00 and PDC2021-120917-C21. | es_ES |
dc.description.sponsorship | Chile. Agencia Nacional de Investigación y Desarrollo; ICN17_002 | es_ES |
dc.description.sponsorship | Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1-230755 | es_ES |
dc.description.sponsorship | Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1221926 | es_ES |
dc.description.sponsorship | Chile. Fondo Nacional de Desarrollo Científico y Tecnológico (Fondecyt); 1-221926 | es_ES |
dc.description.sponsorship | Xunta de Galicia; ED431G 2019/01 | es_ES |
dc.description.sponsorship | Xunta de Galicia; ED431C 2021/53 | es_ES |
dc.description.sponsorship | Xunta de Galicia; ED431C 2021/53 | es_ES |
dc.description.sponsorship | Xunta de Galicia; IN852D 2021/3 | es_ES |
dc.language.iso | eng | es_ES |
dc.publisher | Springer | es_ES |
dc.relation | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2020-114635RB-I00/ES/EXPLOTACIÓN ENRIQUECIDA DE TRAYECTORIAS CON ESTRUCTURAS DE DATOS COMPACTAS Y GIS | es_ES |
dc.relation | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023/PDC2021-120917-C21/ES/SIGTRANS | es_ES |
dc.relation.uri | https://doi.org/10.1007/s00778-023-00811-2 | es_ES |
dc.subject | Regular path queries | es_ES |
dc.subject | Ring index | es_ES |
dc.subject | Succinct data structures | es_ES |
dc.subject | Graph databases | es_ES |
dc.title | Optimizing RPQs over a compact graph representation | es_ES |
dc.type | info:eu-repo/semantics/article | es_ES |
dc.rights.access | info:eu-repo/semantics/openAccess | es_ES |
dc.date.embargoEndDate | 2024-09-07 | es_ES |
dc.date.embargoLift | 2024-09-07 | |
UDC.journalTitle | The VLDB Journal | es_ES |
UDC.volume | 33 | es_ES |
UDC.startPage | 349 | es_ES |
UDC.endPage | 374 | es_ES |
Ficheiros no ítem
Este ítem aparece na(s) seguinte(s) colección(s)
-
GI-LBD - Artigos [54]