Open Access System for Information Sharing

Login Library

 

Conference
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

IDAR: Fast Supergraph Search Using DAG Integration

Title
IDAR: Fast Supergraph Search Using DAG Integration
Authors
HAN, WOOK SHINKIM, HYUNJOONMIN, SEUNGHWANPARK, KUNSOOLIN, XUEMINHONG, SEOK-HEE
Date Issued
4-Sep-2020
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
http://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.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

한욱신HAN, WOOK SHIN
Grad. School of AI
Read more

Views & Downloads

Browse