IDAR: Fast Supergraph Search Using DAG Integration
- Title
- IDAR: Fast Supergraph Search Using DAG Integration
- Authors
- HAN, WOOK SHIN; KIM, HYUNJOON; MIN, SEUNGHWAN; PARK, KUNSOO; LIN, XUEMIN; HONG, SEOK-HEE
- Date Issued
- 2020-09-04
- Publisher
- VLDB Endowment
- Abstract
- Supergraph search is one of fundamental graph query processing problems in many application domains. Given a query graph and a set of data graphs, supergraph search is to find all the data graphs contained in the query graph as subgraphs. In existing algorithms, index construction or filtering approaches are computationally expensive, and search methods can cause redundant computations. In this paper, we introduce four new concepts to address these limitations: (1) DAG integration, (2) dynamic programming between integrated DAG and graph, (3) active-first search, and (4) relevance-size order, which together lead to a much faster and scalable algorithm for supergraph search. Extensive experiments with real datasets show that our approach outperforms state-of-the-art algorithms by up to orders of magnitude in terms of indexing time and query processing time.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/104130
- ISSN
- 2150-8097
- Article Type
- Conference
- Citation
- 46th Int'l Conf. on Very Large Data Bases (VLDB) / Proc. the VLDB Endowment (PVLDB), page. 1456 - 1468, 2020-09-04
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.