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.00013829006
Overall Rank: 1,125 | 92.19%
DOI: 10.1145/2882903.2915236

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 71 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,334	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012543633
1,522	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.0001152219
1,715	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010776518
1,906	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00010135267
2,882	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	7.9666138e-05
2,963	Subgraph Matching: on Compression and Computation	2018	VLDB	7.8061004e-05
2,988	Neural Subgraph Counting with Wasserstein Estimator	2022	SIGMOD	7.7752463e-05
3,034	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	7.6737281e-05
3,119	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	7.5393376e-05
3,488	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	7.0460627e-05
3,781	A Learned Sketch for Subgraph Counting	2021	SIGMOD	6.7691344e-05
4,326	GuP: Fast Subgraph Matching by Guard-based Pruning	2023	SIGMOD	6.2772512e-05
4,486	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1413967e-05
4,554	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.0839934e-05
4,756	Efficient GPU-Accelerated Subgraph Matching	2023	SIGMOD	5.9364786e-05
5,002	HUGE: An Efficient and Scalable Subgraph Enumeration System	2021	SIGMOD	5.7610359e-05
5,030	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.7445683e-05
5,490	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	5.4788004e-05
5,502	Circinus: Fast Redundancy-Reduced Subgraph Matching	2023	SIGMOD	5.4730826e-05
5,530	Efficient Streaming Subgraph Isomorphism with Graph Neural Networks	2021	VLDB	5.4562393e-05
5,782	I/O-Efficient Butterfly Counting at Scale	2023	SIGMOD	5.3268721e-05
5,921	RapidFlow: An Efficient Approach to Continuous Subgraph Matching	2022	VLDB	5.2681722e-05
5,968	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	5.2469955e-05
6,086	Subgraph Matching over Graph Federation	2022	VLDB	5.2157921e-05
6,283	Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction	2023	SIGMOD	5.1234789e-05
6,288	Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach	2024	VLDB	5.1226099e-05
6,391	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.0780425e-05
6,436	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0554554e-05
6,965	BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks	2018	SIGMOD	4.8759021e-05
7,091	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	4.8304411e-05
7,094	PICASSO: Exploratory Search of Connected Subgraph Substructures in Graph Databases	2017	VLDB	4.8293255e-05
7,304	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB	4.7628386e-05
7,456	BSX : Subgraph Matching with Batch Backtracking Search	2025	SIGMOD	4.7205339e-05
7,566	Extending Graph Patterns with Conditions	2020	SIGMOD	4.7047078e-05
7,664	Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling	2017	SIGMOD	4.6805647e-05
7,936	Fast Local Subgraph Counting	2024	VLDB	4.6089395e-05
8,809	Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks	2024	VLDB	4.4401156e-05
9,375	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	4.3452177e-05
9,726	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	4.2901665e-05
9,729	TC-Match: Fast Time-constrained Continuous Subgraph Matching	2024	VLDB	4.2901665e-05
9,791	A Modular Graph-Native Query Optimization Framework	2025	SIGMOD	4.2777144e-05
9,935	MAVIS: Materialized View for Subgraph Matching	2026	SIGMOD	4.2456012e-05
9,936	Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach	2025	SIGMOD	4.2441896e-05
9,942	VINCENT: Towards Efficient Exploratory Subgraph Search in Graph Databases	2022	VLDB	4.241573e-05
10,014	BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching	2026	SIGMOD	4.1905499e-05
10,062	Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings	2026	SIGMOD	4.1905499e-05
10,084	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD	4.1905499e-05
10,085	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	4.1905499e-05
10,096	NeuSO: Neural Optimizer for Subgraph Queries	2026	SIGMOD	4.1905499e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1905499e-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
202	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034881375
351	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026351742
460	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022679846
502	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021528261
616	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00019068362
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
749	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017193776
895	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015498104
1,444	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011941836
1,487	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00011691164
1,630	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011073047
2,021	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	9.7730473e-05
2,172	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	9.37776e-05
2,402	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.87387e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,021	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	9.7730473e-05
5,903	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.2757528e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
10,740	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	4.1905499e-05
6,436	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0554554e-05
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
4,486	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1413967e-05
1,522	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.0001152219
5,968	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	5.2469955e-05
3,119	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	7.5393376e-05