Analysis of Data Structures Involved in RPQ Evaluation.
Research output: Contribution to book/conference proceedings/anthology/report › Conference contribution › Contributed › peer-review
Contributors
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
Original language | English |
---|---|
Title of host publication | DATA 2018 - Proceedings of the 7th International Conference on Data Science, Technology and Applications |
Editors | Jorge Bernardino, Christoph Quix |
Publisher | SCITEPRESS - Science and Technology Publications |
Pages | 334-343 |
Number of pages | 10 |
ISBN (electronic) | 9789897583186 |
Publication status | Published - 2018 |
Peer-reviewed | Yes |
Conference
Title | 7th International Conference on Data Science, Technology and Applications, DATA 2018 |
---|---|
Duration | 26 - 28 July 2018 |
City | Porto |
Country | Portugal |
External IDs
Scopus | 85071499724 |
---|---|
ORCID | /0000-0001-8107-2775/work/142253473 |
Keywords
ASJC Scopus subject areas
Keywords
- Experimental analysis, Graph data management, Regular path queries