EUVIMEDEUVIMED entdecken
Crossref

Representing Paths in Graph Database Pattern Matching

Wim Martens, Matthias Niewerth, Tina Popp, Carlos Rojas, Stijn Vansummeren, Domagoj Vrgoč

Proceedings of the VLDB Endowment · 2023-03 · 16 (7) · 1790-1803

DOI: 10.14778/3587136.3587151 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 08.05.2023. Verfasst von Wim Martens und 5 weiteren Autor:innen. Die Arbeit wurde bisher 22-mal zitiert (Crossref) und nennt 63 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Modern 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.

Zitieren

APA

Martens, W., Niewerth, M., Popp, T., Rojas, C., Vansummeren, S., & Vrgoč, D. (2023). Representing Paths in Graph Database Pattern Matching. Proceedings of the VLDB Endowment, 16(7), 1790-1803. https://doi.org/10.14778/3587136.3587151

Vancouver

Martens W, Niewerth M, Popp T, Rojas C, Vansummeren S, Vrgoč D. Representing Paths in Graph Database Pattern Matching. Proceedings of the VLDB Endowment. 2023;16(7):1790-1803. doi:10.14778/3587136.3587151

BibTeX
@article{Martens2023,
  author = {Martens, Wim and Niewerth, Matthias and Popp, Tina and Rojas, Carlos and Vansummeren, Stijn and Vrgoč, Domagoj},
  title = {Representing Paths in Graph Database Pattern Matching},
  journal = {Proceedings of the VLDB Endowment},
  year = {2023},
  volume = {16},
  number = {7},
  pages = {1790--1803},
  doi = {10.14778/3587136.3587151}
}
Kostenlos starten →