Efficient Subgraph Matching by Postponing Cartesian Products

Summary: Postpones Cartesian products in Ullmann-style subgraph matching to curb unpromising results from dissimilar vertices. Adds a path-based DS of size O(|E(G)|·|V(q)|) to reduce the |V(G)|^(|V(q)|−1) blowup and yield up to 3 orders of magnitude speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5263
Venue: SIGMOD
Year: 2016
Pagerank: 0.00013456907
Overall Rank: 1,180 | 91.80%
DOI: 10.1145/2882903.2915236

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 70 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,333	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012523806
1,561	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00011358946
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
2,912	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	7.9130459e-05
2,997	Subgraph Matching: on Compression and Computation	2018	VLDB	7.7559339e-05
3,001	Neural Subgraph Counting with Wasserstein Estimator	2022	SIGMOD	7.7404487e-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
3,641	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	6.8884895e-05
3,778	A Learned Sketch for Subgraph Counting	2021	SIGMOD	6.7747398e-05
4,470	GuP: Fast Subgraph Matching by Guard-based Pruning	2023	SIGMOD	6.1557462e-05
4,494	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1414196e-05
4,556	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.0883757e-05
4,836	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.8896897e-05
4,968	Efficient GPU-Accelerated Subgraph Matching	2023	SIGMOD	5.7956205e-05
5,009	HUGE: An Efficient and Scalable Subgraph Enumeration System	2021	SIGMOD	5.761237e-05
5,410	PICASSO: Exploratory Search of Connected Subgraph Substructures in Graph Databases	2017	VLDB	5.5235453e-05
5,499	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	5.4750222e-05
5,521	Efficient Streaming Subgraph Isomorphism with Graph Neural Networks	2021	VLDB	5.4614637e-05
5,728	Circinus: Fast Redundancy-Reduced Subgraph Matching	2023	SIGMOD	5.3507988e-05
5,773	I/O-Efficient Butterfly Counting at Scale	2023	SIGMOD	5.3319911e-05
5,926	RapidFlow: An Efficient Approach to Continuous Subgraph Matching	2022	VLDB	5.271318e-05
6,081	Subgraph Matching over Graph Federation	2022	VLDB	5.2208051e-05
6,281	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	5.128862e-05
6,289	Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach	2024	VLDB	5.1275309e-05
6,395	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.0829204e-05
6,441	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0603113e-05
6,575	Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction	2023	SIGMOD	5.0052259e-05
6,971	BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks	2018	SIGMOD	4.8792893e-05
7,100	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	4.8326259e-05
7,307	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB	4.7674113e-05
7,641	Extending Graph Patterns with Conditions	2020	SIGMOD	4.6902655e-05
7,673	Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling	2017	SIGMOD	4.6826056e-05
7,934	Fast Local Subgraph Counting	2024	VLDB	4.613363e-05
8,031	BSX : Subgraph Matching with Batch Backtracking Search	2025	SIGMOD	4.6018906e-05
8,809	Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks	2024	VLDB	4.4443756e-05
9,366	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	4.3493859e-05
9,727	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	4.2942813e-05
9,730	TC-Match: Fast Time-constrained Continuous Subgraph Matching	2024	VLDB	4.2942813e-05
9,788	A Modular Graph-Native Query Optimization Framework	2025	SIGMOD	4.2818172e-05
9,934	MAVIS: Materialized View for Subgraph Matching	2026	SIGMOD	4.2496728e-05
9,935	Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach	2025	SIGMOD	4.2482599e-05
9,942	VINCENT: Towards Efficient Exploratory Subgraph Search in Graph Databases	2022	VLDB	4.2456408e-05
10,014	BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching	2026	SIGMOD	4.1945683e-05
10,062	Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings	2026	SIGMOD	4.1945683e-05
10,084	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD	4.1945683e-05
10,085	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	4.1945683e-05
10,096	NeuSO: Neural Optimizer for Subgraph Queries	2026	SIGMOD	4.1945683e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
203	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034889335
350	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026365067
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
506	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021475362
612	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.0001920234
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
764	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017018712
900	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015495155
1,454	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011913289
1,500	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00011674394
1,635	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.0001105793
2,007	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	9.8081235e-05
2,162	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	9.3964337e-05
2,409	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.8776858e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,007	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	9.8081235e-05
5,854	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.3006473e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
10,733	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	4.1945683e-05
6,441	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0603113e-05
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
4,494	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1414196e-05
1,561	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00011358946
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