MatCo: Computing Match Cover of Subgraph Query over Graph Data

Summary: MatCo introduces the match-cover problem for subgraph queries and a local candidate space to prune future partial matches, avoiding full exploration. It reduces Cartesian products to linear enumerations and achieves 1–3 orders of magnitude speedups over baselines on diverse graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7242
Venue: SIGMOD
Year: 2025
Pagerank: 4.2942813e-05
Overall Rank: 9,727 | 32.34%
DOI: 10.1145/3725323

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,163	Enumerating Graph Pattern Matches with ML Oracles	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023598882
1,180	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013456907
1,394	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.0001221552
1,561	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00011358946
1,720	Incremental Graph Pattern Matching	2011	SIGMOD	0.00010779343
1,756	Graphflow: An Active Graph Database	2017	SIGMOD	0.00010664542
1,775	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010602927
1,924	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00010077055
1,953	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9665955e-05
2,912	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	7.9130459e-05
3,036	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	7.6735171e-05
3,187	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	7.4136521e-05
4,470	GuP: Fast Subgraph Matching by Guard-based Pruning	2023	SIGMOD	6.1557462e-05
4,807	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9092289e-05
5,499	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	5.4750222e-05
5,854	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.3006473e-05
5,926	RapidFlow: An Efficient Approach to Continuous Subgraph Matching	2022	VLDB	5.271318e-05
6,575	Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction	2023	SIGMOD	5.0052259e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
4,470	GuP: Fast Subgraph Matching by Guard-based Pruning	2023	SIGMOD	6.1557462e-05
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
6,281	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	5.128862e-05
3,187	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	7.4136521e-05
11,565	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	4.1945683e-05
1,180	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013456907
2,997	Subgraph Matching: on Compression and Computation	2018	VLDB	7.7559339e-05
9,730	TC-Match: Fast Time-constrained Continuous Subgraph Matching	2024	VLDB	4.2942813e-05
10,851	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.1945683e-05