{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:13Z","timestamp":1775638453715,"version":"3.50.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>\n            Graphs are widely used to model complicated data semantics in many applications. In this paper, we aim to develop efficient techniques to retrieve graphs, containing a given query graph, from a large set of graphs. Considering the problem of testing subgraph isomorphism is generally NP-hard, most of the existing techniques are based on the framework of\n            <jats:italic>filtering<\/jats:italic>\n            -and-\n            <jats:italic>verification<\/jats:italic>\n            to reduce the precise computation costs; consequently various novel feature-based indexes have been developed. While the existing techniques work well for small query graphs, the verification phase becomes a bottleneck when the query graph size increases. Motivated by this, in the paper we firstly propose a novel and efficient algorithm for testing subgraph isomorphism, QuickSI. Secondly, we develop a new feature-based index technique to accommodate QuickSI in the filtering phase. Our extensive experiments on real and synthetic data demonstrate the efficiency and scalability of the proposed techniques, which significantly improve the existing techniques.\n          <\/jats:p>","DOI":"10.14778\/1453856.1453899","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"364-375","source":"Crossref","is-referenced-by-count":313,"title":["Taming verification hardness"],"prefix":"10.14778","volume":"1","author":[{"given":"Haichuan","family":"Shang","sequence":"first","affiliation":[{"name":"University of New South Wales &amp; NICTA, Sydney, Australia"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales &amp; NICTA, Sydney, Australia"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"University of New South Wales &amp; NICTA, Sydney, Australia"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"Chinese university of Hong Kong, Hong Kong, China"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Data Structures and Algorithms","author":"Aho A. V.","year":"1983","unstructured":"A. V. Aho , J. E. Hopcroft , and J. Ullman . Data Structures and Algorithms . 1983 . A. V. Aho, J. E. Hopcroft, and J. Ullman. Data Structures and Algorithms. 1983."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/646514.695831"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.954600"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247574"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2993947.2993981"},{"key":"e_1_2_1_6_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms . 2001 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. 2001."},{"key":"e_1_2_1_7_1","volume-title":"USA","author":"Garey M. R.","year":"1990","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability; A Guide to the Theory of NP-Completeness. New York, NY , USA , 1990 . M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. New York, NY, USA, 1990."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2002.1048250"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.37"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367902"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/1910129"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(98)90142-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368956"},{"key":"e_1_2_1_15_1","first-page":"721","volume-title":"Proceedings of the IEEE International Conference on Data Mining","author":"Yan X.","year":"2002","unstructured":"X. Yan and J. Han . gspan: Graph-based substructure pattern mining . In Proceedings of the IEEE International Conference on Data Mining , page 721 , 2002 . X. Yan and J. Han. gspan: Graph-based substructure pattern mining. In Proceedings of the IEEE International Conference on Data Mining, page 721, 2002."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066244"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368955"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-007-0031-z"},{"key":"e_1_2_1_20_1","first-page":"938","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Zhao P.","year":"2007","unstructured":"P. Zhao , J. X. Yu , and P. S. Yu . Graph indexing: tree + delta &lt;= graph . In Proceedings of the International Conference on Very Large Data Bases , pages 938 -- 949 , 2007 . P. Zhao, J. X. Yu, and P. S. Yu. Graph indexing: tree + delta &lt;= graph. In Proceedings of the International Conference on Very Large Data Bases, pages 938--949, 2007."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353369"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453899","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:09:11Z","timestamp":1672225751000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453899"}},"subtitle":["an efficient algorithm for testing subgraph isomorphism"],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453899"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453899","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}