Database Paper Browser

Back to papers

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 50 of 71 citing papers.

Rank Citing Paper Year Venue Pagerank
817 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.0001387659
1,031 Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019 SIGMOD 0.00012615956
1,097 CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019 SIGMOD 0.00012273511
1,278 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011462905
2,162 TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data 2018 SIGMOD 9.0994327e-05
2,201 Subgraph Matching: on Compression and Computation 2018 VLDB 9.0257706e-05
2,214 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.008953e-05
2,312 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 8.8466711e-05
2,689 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.317052e-05
2,827 GPU-Accelerated Subgraph Enumeration on Partitioned Graphs 2020 SIGMOD 8.1346366e-05
3,229 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.6920894e-05
3,396 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.5176876e-05
3,749 Distributed Subgraph Matching on Timely Dataflow 2019 VLDB 7.2091565e-05
3,762 Multi-Query Optimization for Subgraph Isomorphism Search 2017 VLDB 7.1990313e-05
3,948 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 7.0699328e-05
4,186 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 6.9091925e-05
4,693 Circinus: Fast Redundancy-Reduced Subgraph Matching 2023 SIGMOD 6.6231764e-05
4,702 Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming 2021 VLDB 6.6188333e-05
5,070 Efficient Streaming Subgraph Isomorphism with Graph Neural Networks 2021 VLDB 6.4436438e-05
5,223 RapidFlow: An Efficient Approach to Continuous Subgraph Matching 2022 VLDB 6.3799903e-05
5,248 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.3687097e-05
5,353 Making Graphs Compact by Lossless Contraction 2021 SIGMOD 6.3219746e-05
5,371 I/O-Efficient Butterfly Counting at Scale 2023 SIGMOD 6.3147556e-05
5,511 Subgraph Matching over Graph Federation 2022 VLDB 6.2563094e-05
5,615 Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction 2023 SIGMOD 6.2131411e-05
5,779 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 6.1549096e-05
5,845 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 6.1294746e-05
6,059 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 6.0534485e-05
6,546 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.9031535e-05
6,620 BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks 2018 SIGMOD 5.8801038e-05
6,819 SUFF: Accelerating Subgraph Matching with Historical Data 2023 VLDB 5.8222444e-05
7,038 BSX : Subgraph Matching with Batch Backtracking Search 2025 SIGMOD 5.7719407e-05
7,204 PICASSO: Exploratory Search of Connected Subgraph Substructures in Graph Databases 2017 VLDB 5.7313421e-05
7,235 Extending Graph Patterns with Conditions 2020 SIGMOD 5.7195408e-05
7,636 Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling 2017 SIGMOD 5.6358895e-05
8,117 Fast Local Subgraph Counting 2024 VLDB 5.5419908e-05
8,695 Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks 2024 VLDB 5.4478131e-05
9,305 In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework 2024 SIGMOD 5.3496275e-05
9,714 MatCo: Computing Match Cover of Subgraph Query over Graph Data 2025 SIGMOD 5.2849709e-05
9,717 TC-Match: Fast Time-constrained Continuous Subgraph Matching 2024 VLDB 5.2849709e-05
9,781 A Modular Graph-Native Query Optimization Framework 2025 SIGMOD 5.2719963e-05
9,933 MAVIS: Materialized View for Subgraph Matching 2026 SIGMOD 5.2371813e-05
9,936 Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach 2025 SIGMOD 5.2356043e-05
9,941 VINCENT: Towards Efficient Exploratory Subgraph Search in Graph Databases 2022 VLDB 5.2326703e-05
10,014 BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching 2026 SIGMOD 5.1725247e-05
10,062 Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026 SIGMOD 5.1725247e-05
10,084 GraphMatch: Subgraph Query Processing on Steroids 2026 SIGMOD 5.1725247e-05
10,085 GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries 2026 SIGMOD 5.1725247e-05
10,096 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 5.1725247e-05
10,131 A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] 2026 SIGMOD 5.1725247e-05
Previous Page 1 / 2 Next

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.

Previous Page 1 / 1 Next

Semantically Similar Papers