Analysis of Data Structures Involved in RPQ Evaluation.
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
A fundamental ingredient of declarative graph query languages are regular path queries (RPQs). They provide an expressive yet compact way to match long and complex paths in a data graph by utilizing regular expressions. In this paper, we systematically explore and analyze the design space for the data structures involved in automaton-based RPQ evaluation. We consider three fundamental data structures used during RPQ processing: Adjacency lists for quick neighborhood exploration, visited data structure for cycle detection, and the representation of intermediate results. We conduct an extensive experimental evaluation on realistic graph data sets and systematically investigate various alternative data structure representations and implementation variants. We show that carefully crafted data structures which exploit the access pattern of RPQs lead to reduced peak memory consumption and evaluation time.
Details
Originalsprache | Englisch |
---|---|
Titel | DATA 2018 - Proceedings of the 7th International Conference on Data Science, Technology and Applications |
Redakteure/-innen | Jorge Bernardino, Christoph Quix |
Herausgeber (Verlag) | SCITEPRESS - Science and Technology Publications |
Seiten | 334-343 |
Seitenumfang | 10 |
ISBN (elektronisch) | 9789897583186 |
Publikationsstatus | Veröffentlicht - 2018 |
Peer-Review-Status | Ja |
Konferenz
Titel | 7th International Conference on Data Science, Technology and Applications, DATA 2018 |
---|---|
Dauer | 26 - 28 Juli 2018 |
Stadt | Porto |
Land | Portugal |
Externe IDs
Scopus | 85071499724 |
---|---|
ORCID | /0000-0001-8107-2775/work/142253473 |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Experimental analysis, Graph data management, Regular path queries