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: 5264
Venue: SIGMOD
Year: 2016
Pagerank: 0.00015144404
Overall Rank: 682 | 95.27%
DOI: 10.1145/2882903.2915236

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 71 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,139	An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis]	2026	SIGMOD	5.1725247e-05
10,163	Enumerating Graph Pattern Matches with ML Oracles	2026	SIGMOD	5.1725247e-05
10,236	A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs	2026	VLDB	5.1725247e-05
10,264	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	5.1725247e-05
10,270	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	5.1725247e-05
10,276	gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs	2026	VLDB	5.1725247e-05
10,304	Aquila: A High-Concurrency System for Incremental Graph Query	2026	VLDB	5.1725247e-05
10,320	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	5.1725247e-05
10,523	cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns	2025	SIGMOD	5.1725247e-05
10,640	Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach	2025	VLDB	5.1725247e-05
10,704	S3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB	5.1725247e-05
10,715	Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences	2025	VLDB	5.1725247e-05
10,740	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	5.1725247e-05
10,852	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	5.1725247e-05
10,855	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	5.1725247e-05
10,951	gSWORD: GPU-accelerated Sampling for Subgraph Counting	2024	SIGMOD	5.1725247e-05
10,982	Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching	2024	SIGMOD	5.1725247e-05
10,997	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	5.1725247e-05
11,009	FusionQuery: On-demand Fusion Queries over Multi-source Heterogeneous Data	2024	VLDB	5.1725247e-05
11,569	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	5.1725247e-05
11,602	IDAR: Fast Supergraph Search Using DAG Integration	2020	VLDB	5.1725247e-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
175	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027377116
292	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.0002223786
321	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00021373781
352	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020516762
428	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018725237
434	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018612924
487	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017695307
725	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014708873
1,048	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012532323
1,201	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011794097
1,221	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011697627
1,469	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010747632
1,566	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	0.00010397786
2,789	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.1864277e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,469	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010747632
5,297	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.347246e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	5.1725247e-05
10,740	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	5.1725247e-05
6,059	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	6.0534485e-05
434	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018612924
3,762	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	7.1990313e-05
1,031	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012615956
5,248	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	6.3687097e-05
2,312	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	8.8466711e-05