Abstract
Graph pattern matching is a fundamental operation for the analysis and exploration of data graphs. In this paper, we present a novel approach for efficiently finding homomorphic matches for hybrid graph patterns, where each pattern edge may be mapped either to an edge or to a path in the input data, thus allowing for higher expressiveness and flexibility in query formulation. A key component of our approach is a lightweight index structure that leverages graph simulation to compactly encode the query answer search space. The index can be built on-the-fly during query execution and does not have to persist on the disk. Using the index, we design a multi-way join algorithm to enumerate query solutions without generating an exploding number of intermediate results. We demonstrate through extensive experiments that our approach can efficiently evaluate a broad spectrum of graph pattern queries and greatly outperforms state-of-the-art approaches. Our source code, datasets and queries are publicly available at https://github.com/wuxyng/RIGMatch.
Original language | English (US) |
---|---|
Pages (from-to) | 710-722 |
Number of pages | 13 |
Journal | Advances in Database Technology - EDBT |
Volume | 26 |
Issue number | 3 |
DOIs | |
State | Published - Mar 20 2023 |
Event | 26th International Conference on Extending Database Technology, EDBT 2023 - Ioannina, Greece Duration: Mar 28 2023 → Mar 31 2023 |
All Science Journal Classification (ASJC) codes
- Information Systems
- Software
- Computer Science Applications