{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,17]],"date-time":"2024-08-17T15:13:07Z","timestamp":1723907587084},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.14778\/3397230.3397241","type":"journal-article","created":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T11:46:24Z","timestamp":1593431184000},"page":"1456-1468","source":"Crossref","is-referenced-by-count":8,"title":["IDAR"],"prefix":"10.14778","volume":"13","author":[{"given":"Hyunjoon","family":"Kim","sequence":"first","affiliation":[{"name":"Seoul National University"}]},{"given":"Seunghwan","family":"Min","sequence":"additional","affiliation":[{"name":"Seoul National University"}]},{"given":"Kunsoo","family":"Park","sequence":"additional","affiliation":[{"name":"Seoul National University"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"University of New South Wales"}]},{"given":"Seok-Hee","family":"Hong","sequence":"additional","affiliation":[{"name":"University of Sydney"}]},{"given":"Wook-Shin","family":"Han","sequence":"additional","affiliation":[{"name":"Pohang University of Science and Technology (POSTECH)"}]}],"member":"320","published-online":{"date-parts":[[2020,6,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_10"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16001-1_17"},{"key":"e_1_2_1_4_1","volume-title":"Data Management of Protein Interaction Networks","author":"Cannataro M.","year":"2012"},{"key":"e_1_2_1_5_1","first-page":"926","volume-title":"Proceedings of VLDB","author":"Chen C.","year":"2007"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0212-8"},{"key":"e_1_2_1_7_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0076911"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_1_10_1","first-page":"337","volume-title":"Proceedings of SIGMOD","author":"Han W.-S.","year":"2013"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767909"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498237"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2007.383171"},{"issue":"4","key":"e_1_2_1_15_1","first-page":"420","article-title":"The ubiquity of large graphs and surprising challenges of graph processing","volume":"11","author":"Sahu S.","year":"2017","journal-title":"PVLDB"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447846"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00028"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl571"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497505"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2661872"},{"key":"e_1_2_1_21_1","first-page":"721","volume-title":"Proceedings of IEEE ICDM","author":"Yan X.","year":"2002"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536211"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516385"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2499201"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13818-8_26"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci0496402"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3397230.3397241","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:21:35Z","timestamp":1672222895000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3397230.3397241"}},"subtitle":["fast supergraph search using DAG integration"],"short-title":[],"issued":{"date-parts":[[2020,5]]},"references-count":26,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["10.14778\/3397230.3397241"],"URL":"https:\/\/doi.org\/10.14778\/3397230.3397241","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,5]]}}}