TY - JOUR
T1 - Evaluating Hybrid Graph Pattern Queries Using Runtime Index Graphs
AU - Wu, Xiaoying
AU - Theodoratos, Dimitri
AU - Mamoulis, Nikos
AU - Lan, Michael
N1 - Funding Information:
*X. Wu was supported by the National Natural Science Foundation of China under Grant No. 61872276. †N. Mamoulis was co-financed by the European Regional Development Fund of EU and Greek national funds, under call Research-Create-Innovate (project code: T2EDK-02848).
Publisher Copyright:
© 2023 Copyright held by the owner/author(s)
PY - 2023/3/20
Y1 - 2023/3/20
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85165077301&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85165077301&partnerID=8YFLogxK
U2 - 10.48786/edbt.2023.59
DO - 10.48786/edbt.2023.59
M3 - Conference article
AN - SCOPUS:85165077301
SN - 2367-2005
VL - 26
SP - 710
EP - 722
JO - Advances in Database Technology - EDBT
JF - Advances in Database Technology - EDBT
IS - 3
T2 - 26th International Conference on Extending Database Technology, EDBT 2023
Y2 - 28 March 2023 through 31 March 2023
ER -