Database Paper Browser

Back to papers

Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together

Summary: Proposes DAF, combining DAG-based dynamic programming, adaptive matching order, and failing-set pruning for subgraph matching. Outperforms CFL-Match/Turboiso by orders of magnitude in recursive calls and runtime, showing the value of learned search. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5693
Venue
SIGMOD
Year
2019
Pagerank
0.0001152219
Overall Rank
1,522 | 89.43%
DOI
10.1145/3299869.3319880

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 57 citing papers.

Rank Citing Paper Year Venue Pagerank
1,906 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00010135267
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,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,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,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,705 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 4.9507418e-05
7,091 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 4.8304411e-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,936 Fast Local Subgraph Counting 2024 VLDB 4.6089395e-05
8,135 Towards Event Prediction in Temporal Graphs 2022 VLDB 4.5740737e-05
8,145 Capturing Associations in Graphs 2020 VLDB 4.5724134e-05
9,375 In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework 2024 SIGMOD 4.3452177e-05
9,561 T-FSM: A Task-Based System for Massively Parallel Frequent Subgraph Pattern Mining from a Big Graph 2023 SIGMOD 4.3212967e-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,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
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,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
10,139 An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] 2026 SIGMOD 4.1905499e-05
10,163 Enumerating Graph Pattern Matches with ML Oracles 2026 SIGMOD 4.1905499e-05
10,236 A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs 2026 VLDB 4.1905499e-05
10,264 CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination 2026 VLDB 4.1905499e-05
10,270 Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026 VLDB 4.1905499e-05
10,276 gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs 2026 VLDB 4.1905499e-05
10,312 Scalable Approximate Biclique Counting over Large Bipartite Graphs 2026 VLDB 4.1905499e-05
10,320 Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching 2026 VLDB 4.1905499e-05
10,523 cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns 2025 SIGMOD 4.1905499e-05
10,640 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 4.1905499e-05
10,704 S3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics 2025 VLDB 4.1905499e-05
10,715 Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences 2025 VLDB 4.1905499e-05
10,740 Subgraph Matching: A New Decomposition Based Approach 2025 VLDB 4.1905499e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 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
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
1,125 Efficient Subgraph Matching by Postponing Cartesian Products 2016 SIGMOD 0.00013829006
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
1,806 Incremental Graph Pattern Matching 2011 SIGMOD 0.00010478244
1,948 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 9.9938634e-05
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,199 gStore: Answering SPARQL Queries via Subgraph Matching 2011 VLDB 9.3082437e-05
2,201 LDBC Graphalytics: A Benchmark for Large-Scale Graph Analysis on Parallel and Distributed Platforms 2016 VLDB 9.3042485e-05
2,882 TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data 2018 SIGMOD 7.9666138e-05
4,486 Multi-Query Optimization for Subgraph Isomorphism Search 2017 VLDB 6.1413967e-05
4,748 Diversified Top-k Graph Pattern Matching 2013 VLDB 5.9432853e-05
5,871 Taming Subgraph Isomorphism for RDF Query Processing 2015 VLDB 5.2912806e-05
7,771 Mining Tree-Structured Data on Multicore Systems 2009 VLDB 4.6512834e-05
8,374 LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying 2007 VLDB 4.5282277e-05
Previous Page 1 / 1 Next

Semantically Similar Papers