.png){kind=icon}
Return
Efficient Multi-Query Optimization for Continuous Subgraph Matching Over Streaming Graphs
.png){kind=icon}
PRE
AI
DOI：10.1109/tkde.2026.3721816.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Continuous subgraph matching ($\mathsf{ CSM}$) is a critical task for analyzing dynamic graphs and has a wide range of applications, such as merchant fraud detection, cyber-attack hunting, and rumor detection. Although many efficient $\mathsf{ CSM}$ algorithms have been recently proposed, they are mainly designed to process a single query. However, in some application scenarios, multi-query oriented continuous subgraph matching ($\mathsf{ MQCSM}$) is more critical. To our knowledge, the two existing solutions to $\mathsf{ MQCSM}$ are outdated due to unsatisfactory performance. In this paper, we propose $\mathsf{ MQ-Match}$, an efficient approach for $\mathsf{ MQCSM}$. Specifically, we design a compact index structure, called candidate classification graph ($\mathsf{ CCG}$), to maintain local matching relations in the data graph and prune invalid candidate expansions. We further develop a computation sharing incremental matching method based on shared matching trees, where common structures among query graphs are merged and processed once for each graph update. To reduce redundant search caused by automorphisms, we introduce an optimization approach $\mathsf{ MQ-Match^{\ast}}$. Specifically, we introduce an exclusion set based optimization that prunes symmetric search branches and directly generates symmetric results. Extensive experiments on real datasets show that $\mathsf{ MQ-Match^{\ast}}$ achieves 2.0x-37280.7x speedup over existing methods with much less memory in most settings, while scaling to billion-edge graphs.
Keywords:
Continuous subgraph matching
index structure
incremental maintenance
streaming graph
Journal
IF:
10.4
Papers:
6.9K
Citations:
3.2W
Organization
View more organizations
Cited Papers
No cited papers available