Evaluating Hybrid Graph Pattern Queries Using Runtime Index Graphs

Xiaoying Wu, Dimitri Theodoratos, Nikos Mamoulis, Michael Lan

Research output: Contribution to journalConference articlepeer-review


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 languageEnglish (US)
Pages (from-to)710-722
Number of pages13
JournalAdvances in Database Technology - EDBT
Issue number3
StatePublished - Mar 20 2023
Event26th International Conference on Extending Database Technology, EDBT 2023 - Ioannina, Greece
Duration: Mar 28 2023Mar 31 2023

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Software
  • Computer Science Applications


Dive into the research topics of 'Evaluating Hybrid Graph Pattern Queries Using Runtime Index Graphs'. Together they form a unique fingerprint.

Cite this