Database Paper Browser

Back to papers

Subgraph Matching: A New Decomposition Based Approach

Summary: Revisits tree-decomposition for subgraph matching by finding an optimal fractional-hypertree-width decomposition and materializing bag-level submatches to exploit shared computation across overlapping bags. Introduces ASDMatch: DP-derived per-bag attribute orders with a cost model for computation sharing plus adaptive materialization, yielding large practical speedups and enabling queries that previous methods time out on. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
14045
Venue
VLDB
Year
2025
Pagerank
4.1945683e-05
Overall Rank
10,733 | 25.34%
DOI
10.14778/3749646.3749693

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank Citing Paper Year Venue Pagerank
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 39 of 39 cited papers.

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

Rank Cited Paper Year Venue Pagerank
342 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00026795977
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
1,180 Efficient Subgraph Matching by Postponing Cartesian Products 2016 SIGMOD 0.00013456907
1,328 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00012565612
1,333 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00012523806
1,394 Real-time Constrained Cycle Detection in Large Dynamic Graphs 2018 VLDB 0.0001221552
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,275 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.1262202e-05
2,801 Scalable Distributed Subgraph Enumeration 2017 VLDB 8.0992955e-05
2,997 Subgraph Matching: on Compression and Computation 2018 VLDB 7.7559339e-05
3,009 Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU 2020 VLDB 7.7214924e-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
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,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,077 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 5.7153846e-05
5,718 Conjunctive Queries with Comparisons 2022 SIGMOD 5.3552123e-05
5,728 Circinus: Fast Redundancy-Reduced Subgraph Matching 2023 SIGMOD 5.3507988e-05
5,811 Fast and Robust Distributed Subgraph Enumeration 2019 VLDB 5.317401e-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,305 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 5.1209718e-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,934 Fast Local Subgraph Counting 2024 VLDB 4.613363e-05
8,031 BSX : Subgraph Matching with Batch Backtracking Search 2025 SIGMOD 4.6018906e-05
9,267 PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware 2024 SIGMOD 4.3663649e-05
9,916 TenGraph: A Tensor-Based Graph Query Engine 2024 VLDB 4.2561557e-05
11,132 A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition 2024 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Semantically Similar Papers