{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T18:04:40Z","timestamp":1648922680572},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,3,17]],"date-time":"2009-03-17T00:00:00Z","timestamp":1237248000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1007\/s10878-009-9221-1","type":"journal-article","created":{"date-parts":[[2009,3,16]],"date-time":"2009-03-16T22:05:23Z","timestamp":1237241123000},"page":"159-191","source":"Crossref","is-referenced-by-count":3,"title":["Efficient algorithms for supergraph query processing on graph databases"],"prefix":"10.1007","volume":"21","author":[{"given":"Shuo","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Xiaofeng","family":"Gao","sequence":"additional","affiliation":[]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Jianzhong","family":"Li","sequence":"additional","affiliation":[]},{"given":"Hong","family":"Gao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,3,17]]},"reference":[{"issue":"4","key":"9221_CR1","doi-asserted-by":"crossref","first-page":"1279","DOI":"10.1021\/ci700059g","volume":"47","author":"DK Agrafiotis","year":"2007","unstructured":"Agrafiotis DK, Bandyopadhyay D, Wegner JK, van Vlijmen H (2007) Recent advances in chemoinformatics. J Chem Inf Model 47(4):1279\u20131293","journal-title":"J Chem Inf Model"},{"key":"9221_CR2","unstructured":"Bohannon P, Fan W, Flaster M, Narayan PPS (2005) Information preserving XML schema embedding. In: Proceedings of the international conference on very large data bases, pp\u00a085\u201396"},{"key":"9221_CR3","doi-asserted-by":"crossref","unstructured":"Borgelt C, Berthold MR (2002) Mining molecular fragments: finding relevant substructures of molecules. In: Proceedings of the IEEE international conference on data mining, pp\u00a051\u201358","DOI":"10.1109\/ICDM.2002.1183885"},{"key":"9221_CR4","unstructured":"Bunke H (2000) Graph matching: Theoretical foundations, algorithms, and applications. In: Vision interface, pp\u00a082\u201388"},{"issue":"4","key":"9221_CR5","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s006070050029","volume":"62","author":"M Burge","year":"1999","unstructured":"Burge M, Kropatsch WG (1999) A minimal line property preserving representation of line images. Computing 62(4):355\u2013368","journal-title":"Computing"},{"key":"9221_CR6","doi-asserted-by":"crossref","unstructured":"Cai D, Shao Z, He X, Yan X, Han J (2005) Community mining from multi-relational networks. In: Proceedings of European conference on principles and practice of knowledge discovery in databases, pp\u00a0445\u2013452","DOI":"10.1007\/11564126_44"},{"key":"9221_CR7","unstructured":"Chen C, Yan X, Yu PS, Han J, Zhang D-Q, Gu X (2007) Towards graph containment search and indexing. In: Proceedings of the international conference on very large data bases, pp\u00a0926\u2013937"},{"key":"9221_CR8","doi-asserted-by":"crossref","unstructured":"Cheng J, Ke Y, Ng W, Lu A (2007) Fg-index: towards verification-free query processing on graph databases. In: Proceedings of the ACM SIGMOD international conference on management of data, pp\u00a0857\u2013872","DOI":"10.1145\/1247480.1247574"},{"issue":"3","key":"9221_CR9","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1142\/S0218001404003228","volume":"18","author":"D Conte","year":"2004","unstructured":"Conte D, Foggia P, Sansone C, Vento M (2004) Thirty years of graph matching in pattern recognition. Int J Pattern Recognit Artif Intell 18(3):265\u2013298","journal-title":"Int J Pattern Recognit Artif Intell"},{"key":"9221_CR10","doi-asserted-by":"crossref","unstructured":"Cordella LP, Foggia P, Sansone C, Vento M (2000) Fast graph matching for detecting cad image components. In: Proceedings of the international conference on pattern recognition, pp\u00a06034\u20136037","DOI":"10.1109\/ICPR.2000.906251"},{"issue":"10","key":"9221_CR11","doi-asserted-by":"crossref","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"26","author":"LP Cordella","year":"2004","unstructured":"Cordella LP, Foggia P, Sansone C, Vento M (2004) A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans Pattern Anal Mach Intell 26(10):1367\u20131372","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"9221_CR12","unstructured":"Fortin S (1996) The graph isomorphism problem. Technical report, University of Alberta"},{"key":"9221_CR13","isbn-type":"print","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York. ISBN 0-7167-1044-7","ISBN":"http:\/\/id.crossref.org\/isbn\/0716710447"},{"key":"9221_CR14","unstructured":"Gupta AK, Suciu D (2003) Stream processing of xpath queries with predicates. In: Proceedings of the ACM SIGMOD international conference on management of data, pp\u00a0419\u2013430"},{"key":"9221_CR15","unstructured":"He H, Singh AK (2006) Closure-tree: an index structure for graph queries. In: Proceedings of the international conference on data engineering, p\u00a038"},{"key":"9221_CR16","doi-asserted-by":"crossref","unstructured":"Jiang H, Wang H, Yu PS, Zhou S (2007) Gstring: a novel approach for efficient search in graph databases. In: Proceedings of the international conference on data engineering, pp\u00a0566\u2013575","DOI":"10.1109\/ICDE.2007.367902"},{"key":"9221_CR17","doi-asserted-by":"crossref","unstructured":"Kuramochi M, Karypis G (2001) Frequent subgraph discovery. In: Proceedings of the IEEE international conference on data mining, pp\u00a0313\u2013320","DOI":"10.1109\/ICDM.2001.989534"},{"key":"9221_CR18","unstructured":"Li X-Y, Wan P-J, Wang Y, Yi C-W (2003) Fault tolerant deployment and topology control in wireless networks. In: Proceedings of the ACM international symposium on mobile ad hoc networking and computing, pp\u00a0117\u2013128"},{"key":"9221_CR19","doi-asserted-by":"crossref","unstructured":"Liu Y, Li J, Gao H (2008) Summarizing graph patterns. In: Proceedings of the international conference on data engineering, pp\u00a0903\u2013912","DOI":"10.1109\/ICDE.2008.4497499"},{"issue":"12","key":"9221_CR20","doi-asserted-by":"crossref","first-page":"1979","DOI":"10.1016\/S0031-3203(98)90142-X","volume":"32","author":"BT Messmer","year":"1999","unstructured":"Messmer BT, Bunke H (1999) A decision tree approach to graph and subgraph isomorphism detection. Pattern Recognit 32(12):1979\u20131998","journal-title":"Pattern Recognit"},{"issue":"2","key":"9221_CR21","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1109\/69.842269","volume":"12","author":"BT Messmer","year":"2000","unstructured":"Messmer BT, Bunke H (2000) Efficient subgraph isomorphism detection: a decomposition approach. IEEE Trans Knowl Data Eng 12(2):307\u2013323","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"3","key":"9221_CR22","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1109\/69.599932","volume":"9","author":"EGM Petrakis","year":"1997","unstructured":"Petrakis EGM, Faloutsos C (1997) Similarity searching in medical image databases. IEEE Trans Knowl Data Eng 9(3):435\u2013447","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"1","key":"9221_CR23","doi-asserted-by":"crossref","first-page":"364","DOI":"10.14778\/1453856.1453899","volume":"1","author":"H Shang","year":"2008","unstructured":"Shang H, Zhang Y, Lin X, Yu JX (2008) Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proc VLDB Endow 1(1):364\u2013375","journal-title":"Proc VLDB Endow"},{"key":"9221_CR24","doi-asserted-by":"crossref","unstructured":"Shasha D, Wang JT-L, Giugno R (2002) Algorithmics and applications of tree and graph searching. In: Proceedings of the ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems, pp\u00a039\u201352","DOI":"10.1145\/543613.543620"},{"issue":"1","key":"9221_CR25","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"JR Ullmann","year":"1976","unstructured":"Ullmann JR (1976) An algorithm for subgraph isomorphism. J ACM 23(1):31\u201342","journal-title":"J ACM"},{"key":"9221_CR26","doi-asserted-by":"crossref","unstructured":"Wang C, Wang W, Pei J, Zhu Y, Shi B (2004) Scalable mining of large disk-based graph databases. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining, pp\u00a0316\u2013325","DOI":"10.1145\/1014052.1014088"},{"issue":"1","key":"9221_CR27","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1145\/959242.959249","volume":"5","author":"T Washio","year":"2003","unstructured":"Washio T, Motoda H (2003) State of the art of graph-based data mining. SIGKDD Explor 5(1):59\u201368","journal-title":"SIGKDD Explor"},{"issue":"6","key":"9221_CR28","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1021\/ci9800211","volume":"38","author":"P Willett","year":"1998","unstructured":"Willett P, Barnard JM, Downs GM (1998) Chemical similarity searching. J Chem Inf Comput Sci 38(6):983\u2013996","journal-title":"J Chem Inf Comput Sci"},{"key":"9221_CR29","doi-asserted-by":"crossref","unstructured":"Williams DW, Huan J, Wang W (2007) Graph database indexing using structured graph decomposition. In: Proceedings of the international conference on data engineering, pp\u00a0976\u2013985","DOI":"10.1109\/ICDE.2007.368956"},{"key":"9221_CR30","unstructured":"W\u00f6rlein M (2006) Extension and parallelization of a graph-mining-algorithm. Master\u2019s thesis, Friedrich-Alexander-Universit\u00e4t, Erlangen-N\u00fcrnberg"},{"key":"9221_CR31","unstructured":"Yan X, Han J (2002) gspan: Graph-based substructure pattern mining. In: Proceedings of the IEEE international conference on data mining, pp\u00a0721\u2013724"},{"key":"9221_CR32","doi-asserted-by":"crossref","unstructured":"Yan X, Han J (2003) Closegraph: mining closed frequent graph patterns. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining, pp\u00a0286\u2013295","DOI":"10.1145\/956750.956784"},{"issue":"4","key":"9221_CR33","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/1114244.1114248","volume":"30","author":"X Yan","year":"2005","unstructured":"Yan X, Yu PS, Han J (2005) Graph indexing based on discriminative frequent structure analysis. ACM Trans Database Syst 30(4):960\u2013993","journal-title":"ACM Trans Database Syst"},{"issue":"2","key":"9221_CR34","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/1242524.1242530","volume":"32","author":"Z Zeng","year":"2007","unstructured":"Zeng Z, Wang J, Zhou L, Karypis G (2007) Out-of-core coherent closed quasi-clique mining from large dense graph databases. ACM Trans Database Syst 32(2):13","journal-title":"ACM Trans Database Syst"},{"key":"9221_CR35","doi-asserted-by":"crossref","unstructured":"Zhang S, Hu M, Yang J (2007) Treepi: a novel graph indexing method. In: Proceedings of the international conference on data engineering, pp\u00a0966\u2013975","DOI":"10.1109\/ICDE.2007.368955"},{"key":"9221_CR36","unstructured":"Zhao P, Yu JX, Yu PS (2007) Graph indexing: Tree + delta \u2265 graph. In: Proceedings of the international conference on very large data bases, pp\u00a0938\u2013949"},{"key":"9221_CR37","doi-asserted-by":"crossref","unstructured":"Zou L, Chen L, Yu JX, Lu Y (2008) A novel spectral coding in a large graph database. In: Proceedings of the international conference on extending database technology, pp\u00a0181\u2013192","DOI":"10.1145\/1353343.1353369"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9221-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9221-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9221-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:14Z","timestamp":1559276294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9221-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,17]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["9221"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9221-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3,17]]}}}