{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T15:32:40Z","timestamp":1788622360869,"version":"build-2803163510"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,8,26]]},"abstract":"<jats:p>We study supergraph search (SPS), that is, given a query graph<jats:italic>q<\/jats:italic>and a graph database<jats:italic>G<\/jats:italic>that contains a collection of graphs , return graphs that have<jats:italic>q<\/jats:italic>as a supergraph from<jats:italic>G<\/jats:italic>. SPS has broad applications in bioinformatics, cheminformatics and other scientific and commercial fields. Determining whether a graph is a subgraph (or supergraph) of another is an NP-complete problem. Hence, it is intractable to compute SPS for large graph databases. Two separate indexing methods, a \"filter + verify\"-based method and a \"prefix-sharing\"-based method, have been studied to efficiently compute SPS. To implement the above two methods, subgraph patterns are mined from the graph database to build an index. Those subgraphs are mined to optimize either the filtering gain or the prefix-sharing gain. However, no single subgraph-mining algorithm considers both gains.<\/jats:p><jats:p>This work is the first one to mine subgraphs to optimize both the filtering gain and the prefix-sharing gain while processing SPS queries. First, we show that the subgraph-mining problem is NP-hard. Then, we propose two polynomial-time algorithms to solve the problem with an approximation ratio of 1-1\/<jats:italic>e<\/jats:italic>and 1\/4 respectively. In addition, we construct a lattice-like index, LW-index, to organize the selected subgraph patterns for fast index-lookup. Our experiments show that our approach improves the query processing time for SPS queries by a factor of 3 to 10.<\/jats:p>","DOI":"10.14778\/2536206.2536211","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"829-840","source":"Crossref","is-referenced-by-count":10,"title":["Mining and indexing graphs for supergraph search"],"prefix":"10.14778","volume":"6","author":[{"given":"Dayu","family":"Yuan","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prasenjit","family":"Mitra","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering and College of Information Sciences and Technology, The Pennsylvania State University, University Park, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C. Lee","family":"Giles","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering and College of Information Sciences and Technology, The Pennsylvania State University, University Park, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,8]]},"reference":[{"key":"e_1_2_1_1_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/978-3-642-22110-1_10","volume-title":"CAV","author":"Babic D.","year":"2011","unstructured":"D. Babic , D. Reynaud , and D. Song . Malware Analysis with Tree Automata Inference . In CAV , volume 6806 of Lecture Notes in Computer Science , pages 116 - 131 , 2011 . D. Babic, D. Reynaud, and D. Song. Malware Analysis with Tree Automata Inference. In CAV, volume 6806 of Lecture Notes in Computer Science, pages 116-131, 2011."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1145\/564691.564722","volume-title":"SIGMOD","author":"Bruno N.","year":"2002","unstructured":"N. Bruno and S. Chaudhuri . Exploiting statistics on query expressions for optimization . SIGMOD , pages 263 - 274 , New York, NY, USA , 2002 . N. Bruno and S. Chaudhuri. Exploiting statistics on query expressions for optimization. SIGMOD, pages 263-274, New York, NY, USA, 2002."},{"key":"e_1_2_1_3_1","first-page":"926","volume-title":"VLDB","author":"Chen C.","year":"2007","unstructured":"C. Chen , X. Yan , P. S. Yu , J. Han , D.-Q. Zhang , and X. Gu . Towards graph containment search and indexing . VLDB , pages 926 - 937 . VLDB Endowment , 2007 . C. Chen, X. Yan, P. S. Yu, J. Han, D.-Q. Zhang, and X. Gu. Towards graph containment search and indexing. VLDB, pages 926-937. VLDB Endowment, 2007."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1508857.1508859","article-title":"Efficient query processing on graph databases","volume":"34","author":"Cheng J.","year":"2009","unstructured":"J. Cheng , Y. Ke , and W. Ng . Efficient query processing on graph databases . TODS , 34 : 2 :1-2:48, 2009 . J. Cheng, Y. Ke, and W. Ng. Efficient query processing on graph databases. TODS, 34:2:1-2:48, 2009.","journal-title":"TODS"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1145\/1247480.1247574","volume-title":"SIGMOD","author":"Cheng J.","year":"2007","unstructured":"J. Cheng , Y. Ke , W. Ng , and A. Lu . Fg-index: Towards verification-free query processing on graph databases . In SIGMOD , pages 857 - 872 , 2007 . J. Cheng, Y. Ke, W. Ng, and A. Lu. Fg-index: Towards verification-free query processing on graph databases. In SIGMOD, pages 857-872, 2007."},{"key":"e_1_2_1_6_1","series-title":"Mathematical Programming Studies","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume-title":"Polyhedral Combinatorics","author":"Fisher M.","year":"1978","unstructured":"M. Fisher , G. Nemhauser , and L. Wolsey . An analysis of approximations for maximizing submodular set functions . In M. Balinski and A. Hoffman, editors, Polyhedral Combinatorics , volume 8 of Mathematical Programming Studies , pages 73 - 87 . 1978 . M. Fisher, G. Nemhauser, and L. Wolsey. An analysis of approximations for maximizing submodular set functions. In M. Balinski and A. Hoffman, editors, Polyhedral Combinatorics, volume 8 of Mathematical Programming Studies, pages 73-87. 1978."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"449","DOI":"10.14778\/1920841.1920901","article-title":"a framework for comparisons of disk-based graph indexing techniques","volume":"3","author":"Han W.-S.","year":"2010","unstructured":"W.-S. Han , J. Lee , M.-D. Pham , and J. X. Yu . igraph : a framework for comparisons of disk-based graph indexing techniques . Proc. VLDB Endow. , 3 : 449 - 459 , 2010 . W.-S. Han, J. Lee, M.-D. Pham, and J. X. Yu. igraph: a framework for comparisons of disk-based graph indexing techniques. Proc. VLDB Endow., 3:449-459, 2010.","journal-title":"Proc. VLDB Endow."},{"issue":"5","key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1016\/j.cag.2010.06.002","article-title":"Automatic discovery of common design structures in cad models","volume":"34","author":"Ma L.","year":"2010","unstructured":"L. Ma , Z. Huang , and Y. Wang . Automatic discovery of common design structures in cad models . Computers and Graphics , 34 ( 5 ): 545 - 555 , 2010 . L. Ma, Z. Huang, and Y. Wang. Automatic discovery of common design structures in cad models. Computers and Graphics, 34(5):545-555, 2010.","journal-title":"Computers and Graphics"},{"key":"e_1_2_1_9_1","first-page":"1","article-title":"The parmol package for frequent subgraph mining","author":"Meinl T.","year":"2006","unstructured":"T. Meinl , M. Wrlein , O. Urzova , I. Fischer , and M. Philippsen . The parmol package for frequent subgraph mining . ECEASST , 1 , 2006 . T. Meinl, M. Wrlein, O. Urzova, I. Fischer, and M. Philippsen. The parmol package for frequent subgraph mining. ECEASST, 1, 2006.","journal-title":"ECEASST"},{"key":"e_1_2_1_10_1","first-page":"1","volume-title":"CVPR","author":"Nowozin S.","year":"2007","unstructured":"S. Nowozin , K. Tsuda , T. Uno , T. Kudo , and G. Bakir . Weighted substructure mining for image analysis . In CVPR , pages 1 - 8 , 2007 . S. Nowozin, K. Tsuda, T. Uno, T. Kudo, and G. Bakir. Weighted substructure mining for image analysis. In CVPR, pages 1-8, 2007."},{"key":"e_1_2_1_11_1","first-page":"697","volume-title":"SDM","author":"Saha B.","year":"2009","unstructured":"B. Saha and L. Getoor . On maximum coverage in the streaming model & application to multi-topic blog-watch . In SDM , pages 697 - 708 , 2009 . B. Saha and L. Getoor. On maximum coverage in the streaming model & application to multi-topic blog-watch. In SDM, pages 697-708, 2009."},{"key":"e_1_2_1_12_1","first-page":"364","volume-title":"Proc. VLDB Endow.","author":"Shang H.","year":"2008","unstructured":"H. Shang , Y. Zhang , X. Lin , and J. X. Yu . Taming verification hardness: an efficient algorithm for testing subgraph isomorphism . Proc. VLDB Endow. , pages 364 - 375 , 2008 . H. Shang, Y. Zhang, X. Lin, and J. X. Yu. Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proc. VLDB Endow., pages 364-375, 2008."},{"key":"e_1_2_1_13_1","first-page":"637","volume-title":"ICDE","author":"Shang H.","year":"2010","unstructured":"H. Shang , K. Zhu , X. Lin , Y. Zhang , and R. Ichise . Similarity search on supergraph containment . In ICDE , pages 637 - 648 , 2010 . H. Shang, K. Zhu, X. Lin, Y. Zhang, and R. Ichise. Similarity search on supergraph containment. In ICDE, pages 637-648, 2010."},{"key":"e_1_2_1_14_1","first-page":"563","volume-title":"CIKM","author":"Sun B.","year":"2009","unstructured":"B. Sun , P. Mitra , and C. L. Giles . Independent informative subgraph mining for graph information retrieval . In CIKM , pages 563 - 572 , 2009 . B. Sun, P. Mitra, and C. L. Giles. Independent informative subgraph mining for graph information retrieval. In CIKM, pages 563-572, 2009."},{"issue":"2","key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1021\/ci00042a005","article-title":"Artificial intelligence in organic synthesis. sst: starting material selection strategies. an application of superstructure search","volume":"24","author":"Wipke W. T.","year":"1984","unstructured":"W. T. Wipke and D. Rogers . Artificial intelligence in organic synthesis. sst: starting material selection strategies. an application of superstructure search . J Chem Inform Comput Sci , 24 ( 2 ): 71 - 81 , 1984 . W. T. Wipke and D. Rogers. Artificial intelligence in organic synthesis. sst: starting material selection strategies. an application of superstructure search. J Chem Inform Comput Sci, 24(2):71-81, 1984.","journal-title":"J Chem Inform Comput Sci"},{"key":"e_1_2_1_16_1","first-page":"721","volume-title":"ICDM","author":"Yan X.","year":"2002","unstructured":"X. Yan and J. Han . gspan: Graph-based substructure pattern mining . In ICDM , pages 721 - 724 , 2002 . X. Yan and J. Han. gspan: Graph-based substructure pattern mining. In ICDM, pages 721-724, 2002."},{"key":"e_1_2_1_17_1","first-page":"335","volume-title":"SIGMOD","author":"Yan X.","year":"2004","unstructured":"X. Yan , P. S. Yu , and J. Han . Graph indexing: a frequent structure-based approach . In SIGMOD , pages 335 - 346 , 2004 . X. Yan, P. S. Yu, and J. Han. Graph indexing: a frequent structure-based approach. In SIGMOD, pages 335-346, 2004."},{"issue":"2","key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s00778-012-0284-8","article-title":"Lindex: a lattice-based index for graph databases","volume":"22","author":"Yuan D.","year":"2013","unstructured":"D. Yuan and P. Mitra . Lindex: a lattice-based index for graph databases . The VLDB Journal , 22 ( 2 ): 229 - 252 , 2013 . D. Yuan and P. Mitra. Lindex: a lattice-based index for graph databases. The VLDB Journal, 22(2):229-252, 2013.","journal-title":"The VLDB Journal"},{"key":"e_1_2_1_19_1","first-page":"198","volume-title":"ICDE","author":"Yuan D.","year":"2012","unstructured":"D. Yuan , P. Mitra , H. Yu , and C. L. Giles . Iterative graph feature mining for graph indexing . In ICDE , pages 198 - 209 , 2012 . D. Yuan, P. Mitra, H. Yu, and C. L. Giles. Iterative graph feature mining for graph indexing. In ICDE, pages 198-209, 2012."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1145\/1516360.1516385","volume-title":"EDBT","author":"Zhang S.","year":"2009","unstructured":"S. Zhang , J. Li , H. Gao , and Z. Zou . A novel approach for efficient supergraph query processing on graph databases . In EDBT , pages 204 - 215 , 2009 . S. Zhang, J. Li, H. Gao, and Z. Zou. A novel approach for efficient supergraph query processing on graph databases. In EDBT, pages 204-215, 2009."},{"key":"e_1_2_1_21_1","first-page":"360","volume-title":"SSDBM","author":"Zhu G.","year":"2010","unstructured":"G. Zhu , X. Lin , W. Zhang , W. Wang , and H. Shang . Prefindex: an efficient supergraph containment search technique . In SSDBM , pages 360 - 378 , 2010 . G. Zhu, X. Lin, W. Zhang, W. Wang, and H. Shang. Prefindex: an efficient supergraph containment search technique. In SSDBM, pages 360-378, 2010."},{"issue":"5","key":"e_1_2_1_22_1","first-page":"1214","article-title":"Superstructure searching algorithm for generic reaction retrieval","volume":"45","author":"Zhu Q.","year":"2005","unstructured":"Q. Zhu , Yao, Yuan, F. Li , Chen, W. Cai , and Q. Liao . Superstructure searching algorithm for generic reaction retrieval . JCIM , 45 ( 5 ): 1214 - 1222 , 2005 . Q. Zhu, Yao, Yuan, F. Li, Chen, W. Cai, and Q. Liao. Superstructure searching algorithm for generic reaction retrieval. JCIM, 45(5):1214-1222, 2005.","journal-title":"JCIM"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536206.2536211","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T14:43:55Z","timestamp":1689345835000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536206.2536211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":22,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2013,8,26]]}},"alternative-id":["10.14778\/2536206.2536211"],"URL":"https:\/\/doi.org\/10.14778\/2536206.2536211","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,8]]}}}