Representing Paths in Graph Database Pattern Matching

Simple item page
dc.article.number2980
dc.contributor.authorMartens, Wim
dc.contributor.authorNiewerth, Matthias
dc.contributor.authorPopp, Tina
dc.contributor.authorRojas, Carlos
dc.contributor.authorVansummeren, Stijn
dc.contributor.authorVrgoc, Domagoj
dc.date.accessioned2025-05-01T10:31:08Z
dc.date.available2025-05-01T10:31:08Z
dc.date.issued2023
dc.description.abstractModern graph database query languages such as GQL, SQL/PGQ, and their academic predecessor G-Core promote paths to first-class citizens in the sense that their pattern matching facility can return paths, as opposed to only nodes and edges. This is challenging for database engines, since graphs can have a large number of paths between a given node pair, which can cause huge intermediate results in query evaluation., We introduce the concept of path multiset representations (PMRs), which can represent multisets of paths exponentially succinctly and therefore bring significant advantages for representing intermediate results. We give a detailed theoretical analysis that shows that they are especially well-suited for representing results of regular path queries and extensions thereof involving counting, random sampling, and unions. Our experiments show that they drastically improve scalability for regular path query evaluation, with speedups of several orders of magnitude.
dc.description.funderWilsonOlegario foundation
dc.format.extent13 páginas
dc.fuente.origenWOS
dc.identifier.doi10.14778/3587136.3587151
dc.identifier.eisbn978-1-5106-5352-8
dc.identifier.eissn1759-5053
dc.identifier.isbn978-1-5106-5351-1
dc.identifier.issn2150-8097
dc.identifier.pubmedid40243597
dc.identifier.scieloidS0718-69242020000300109
dc.identifier.scopusidSCOPUS_ID:105001560634
dc.identifier.urihttps://doi.org/10.14778/3587136.3587151
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/103717
dc.identifier.wosidWOS:000992411400016
dc.information.autorucInstituto de Ingeniería Matemática y Computacional; Vrgoc Domagoj; 0000-0001-5854-2652; 243075
dc.issue.numero7
dc.language.isoen
dc.nota.accesoSin adjunto
dc.pagina.final1803
dc.pagina.inicio1790
dc.relation.ispartofInternational Conference on Intelligent User Interfaces (30a. : 2025)
dc.revistaPROCEEDINGS OF THE VLDB ENDOWMENT
dc.rightsregistro bibliográfico
dc.subjectGenerative AI
dc.subjectLarge Language Models
dc.subjectSpace Manipulation
dc.subject.ddc510
dc.subject.deweyMatemática física y químicaes_ES
dc.subject.ods03 Good health and well-being
dc.subject.odspa03 Salud y bienestar
dc.titleRepresenting Paths in Graph Database Pattern Matching
dc.typecomunicación de congreso
dc.volumen16
sipa.codpersvinculados243075
sipa.indexWOS
sipa.trazabilidadCarga WOS-SCOPUS;01-05-2025
Files
Collections
Artículos de conferencia