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 20 of 70 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,139	An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
10,163	Enumerating Graph Pattern Matches with ML Oracles	2026	SIGMOD	4.1945683e-05
10,236	A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs	2026	VLDB	4.1945683e-05
10,264	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	4.1945683e-05
10,270	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.1945683e-05
10,292	Aquila: A High-Concurrency System for Incremental Graph Query	2026	VLDB	4.1945683e-05
10,308	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.1945683e-05
10,514	cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns	2025	SIGMOD	4.1945683e-05
10,632	Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach	2025	VLDB	4.1945683e-05
10,696	S3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB	4.1945683e-05
10,708	Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences	2025	VLDB	4.1945683e-05
10,733	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	4.1945683e-05
10,848	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	4.1945683e-05
10,851	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.1945683e-05
10,948	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	4.1945683e-05
10,979	Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching	2024	SIGMOD	4.1945683e-05
10,994	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1945683e-05
11,006	FusionQuery: On-demand Fusion Queries over Multi-source Heterogeneous Data	2024	VLDB	4.1945683e-05
11,565	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	4.1945683e-05
11,598	IDAR: Fast Supergraph Search Using DAG Integration	2020	VLDB	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