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,504 | BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification | 2023 | VLDB | 5.7617085e-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 |
|---|---|---|---|---|
| 239 | The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing | 2018 | VLDB | 0.000235107 |
| 490 | TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases | 2013 | SIGMOD | 0.00017438618 |
| 657 | Efficient Subgraph Matching by Postponing Cartesian Products | 2016 | SIGMOD | 0.0001505607 |
| 712 | Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins | 2019 | VLDB | 0.00014578373 |
| 960 | Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together | 2019 | SIGMOD | 0.00012836554 |
| 2,376 | Towards Graph Containment Search and Indexing | 2007 | VLDB | 8.5543073e-05 |
| 6,642 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB | 5.7238453e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,760 | Updating Graph Indices with a One-Pass Algorithm | 2015 | SIGMOD |
| 2 | 14,113 | Information Discovery in Loosely Integrated Data | 2007 | SIGMOD |
| 3 | 3,506 | Performance and Scalability of Indexed Subgraph Query Processing Methods | 2015 | VLDB |
| 4 | 3,509 | Keyword Search on External Memory Data Graphs | 2008 | VLDB |
| 5 | 10,256 | Integral Densest Subgraph Search on Directed Graphs | 2025 | SIGMOD |
| 6 | 443 | Efficient Subgraph Matching on Billion Node Graphs | 2012 | VLDB |
| 7 | 9,191 | Interactive Graph Search for Multiple Targets on DAGs | 2025 | VLDB |
| 8 | 2,376 | Towards Graph Containment Search and Indexing | 2007 | VLDB |
| 9 | 6,642 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB |
| 10 | 7,840 | DAG Reduction: Fast Answering Reachability Queries | 2017 | SIGMOD |