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)
Incoming Non-self Citations Over Time
Authors
- 1. Myoungji Han (Seoul National University)
- 2. Hyunjoon Kim (Seoul National University)
- 3. Geonmo Gu (Seoul National University)
- 4. Kunsoo Park (Seoul National University)
- 5. Wook-Shin Han (Pohang University of Science and Technology)
BibTeX Citation
@inproceedings{han_sigmod19,
title = {{Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together}},
author = {Han, Myoungji and Kim, Hyunjoon and Gu, Geonmo and Park, Kunsoo and Han, Wook-Shin},
series = {{SIGMOD} '19},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3299869.3319880},
url = {https://dl.acm.org/doi/10.1145/3299869.3319880},
year = {2019}
}
Incoming Citations (Sorted by Pagerank)
Showing 9 of 59 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,885 | Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach | 2025 | VLDB | 5.093636e-05 |
| 10,952 | Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences | 2025 | VLDB | 5.093636e-05 |
| 11,072 | Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds | 2025 | VLDB | 5.093636e-05 |
| 11,075 | Mix & Match: Subgraph Matching for Absolute Coverage | 2025 | VLDB | 5.093636e-05 |
| 11,165 | gSWORD: GPU-accelerated Sampling for Subgraph Counting | 2024 | SIGMOD | 5.093636e-05 |
| 11,217 | FusionQuery: On-demand Fusion Queries over Multi-source Heterogeneous Data | 2024 | VLDB | 5.093636e-05 |
| 11,227 | Extending Graph Rules with Oracles | 2024 | VLDB | 5.093636e-05 |
| 11,410 | Enriching Recommendation Models with Logic Conditions | 2023 | SIGMOD | 5.093636e-05 |
| 11,793 | IDAR: Fast Supergraph Search Using DAG Integration | 2020 | VLDB | 5.093636e-05 |
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.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 442 | Efficient Subgraph Matching on Billion Node Graphs | 2012 | VLDB |
| 2 | 1,487 | Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs | 2015 | VLDB |
| 3 | 1,128 | Graph Pattern Matching: From Intractable to Polynomial Time | 2010 | VLDB |
| 4 | 6,924 | SUFF: Accelerating Subgraph Matching with Historical Data | 2023 | VLDB |
| 5 | 3,194 | GuP: Fast Subgraph Matching by Guard-based Pruning | 2023 | SIGMOD |
| 6 | 10,419 | A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] | 2026 | SIGMOD |
| 7 | 9,693 | Subgraph Matching: A New Decomposition Based Approach | 2025 | VLDB |
| 8 | 4,983 | A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction | 2024 | SIGMOD |
| 9 | 2,190 | Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching | 2021 | SIGMOD |
| 10 | 659 | Efficient Subgraph Matching by Postponing Cartesian Products | 2016 | SIGMOD |