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