Cimos: Cost-Effective Multi-Query Oriented Continuous Subgraph Matching

Abstract

Continuous subgraph matching over dynamic graphs is a fundamental problem in graph databases, with broad applications in real-time pattern monitoring and risk control. In practice, applications often require monitoring multiple graph patterns simultaneously, making multi-query oriented continuous subgraph matching (MCSM) an increasingly important research topic. Although existing methods have achieved performance gains, their indexes offer limited filtering power and they lack high-quality query plans tailored to the multi-query setting. To address these limitations, we propose Cimos, a novel index-based framework for cost-effective MCSM. First, we design a data-centric index called DCL that serves multiple query graphs and prunes more non-candidate vertices by jointly considering the matching constraints of ancestor and descendant vertices in query DAGs. Second, we adopt a hybrid-order planning strategy that separates the query plan into static and dynamic ordering components. For the static component, we introduce a prefix order tree to extract isomorphic subgraphs shared across query graphs, and optimize vertex orderings using statistical upper-bound obtained via DCL-based subgraph sampling. For the dynamic component, we employ DCL-based cardinality estimation to adaptively determine vertex orderings during the matching process. Extensive experiments demonstrate that Cimos achieves notable speedup of more than 4.2x against state-of-the-art CSM and MCSM methods.