IDAR: Fast Supergraph Search Using DAG Integration
Summary: Introduces DAG integration and four techniques—dynamic programming with the integrated DAG, active-first search, and relevance-size ordering—to accelerate supergraph search (data graphs embedded in a query graph). Experiments report orders-of-magnitude speedups in indexing and query processing versus state-of-the-art. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Hyunjoon Kim (Seoul National University)
- 2. Seunghwan Min (Seoul National University)
- 3. Kunsoo Park (Seoul National University)
- 4. Xuemin Lin (University of New South Wales)
- 5. Seok-Hee Hong (University of Sydney)
- 6. Wook-Shin Han (Pohang University of Science and Technology)
BibTeX Citation
@article{kim_vldb20,
title = {{IDAR: Fast Supergraph Search Using DAG Integration}},
author = {Kim, Hyunjoon and Min, Seunghwan and Park, Kunsoo and Lin, Xuemin and Hong, Seok-Hee and Han, Wook-Shin},
journal = {PVLDB},
series = {{VLDB} '20},
volume = {13},
number = {9},
pages = {1456--1468},
doi = {10.14778/3397230.3397241},
url = {https://doi.org/10.14778/3397230.3397241},
year = {2020}
}Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,393 | BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification | 2023 | VLDB | 5.8879832e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 264 | The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing | 2018 | VLDB | 0.00022980015 |
| 485 | TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases | 2013 | SIGMOD | 0.00017717377 |
| 659 | Efficient Subgraph Matching by Postponing Cartesian Products | 2016 | SIGMOD | 0.00015214062 |
| 809 | Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins | 2019 | VLDB | 0.00013874588 |
| 1,006 | Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together | 2019 | SIGMOD | 0.00012699518 |
| 2,328 | Towards Graph Containment Search and Indexing | 2007 | VLDB | 8.745748e-05 |
| 6,520 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB | 5.8535203e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,631 | Updating Graph Indices with a One-Pass Algorithm | 2015 | SIGMOD |
| 2 | 13,802 | Information Discovery in Loosely Integrated Data | 2007 | SIGMOD |
| 3 | 3,477 | Performance and Scalability of Indexed Subgraph Query Processing Methods | 2015 | VLDB |
| 4 | 3,450 | Keyword Search on External Memory Data Graphs | 2008 | VLDB |
| 5 | 10,767 | Integral Densest Subgraph Search on Directed Graphs | 2025 | SIGMOD |
| 6 | 442 | Efficient Subgraph Matching on Billion Node Graphs | 2012 | VLDB |
| 7 | 2,328 | Towards Graph Containment Search and Indexing | 2007 | VLDB |
| 8 | 9,812 | Interactive Graph Search for Multiple Targets on DAGs | 2025 | VLDB |
| 9 | 6,520 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB |
| 10 | 7,707 | DAG Reduction: Fast Answering Reachability Queries | 2017 | SIGMOD |