{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:51:15Z","timestamp":1773481875738,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,10,24]],"date-time":"2017-10-24T00:00:00Z","timestamp":1508803200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,10,24]],"date-time":"2017-10-24T00:00:00Z","timestamp":1508803200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["16H01722"],"award-info":[{"award-number":["16H01722"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61402494"],"award-info":[{"award-number":["61402494"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["71690233"],"award-info":[{"award-number":["71690233"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004735","name":"Natural Science Foundation of Hunan Province","doi-asserted-by":"publisher","award":["2015JJ4009"],"award-info":[{"award-number":["2015JJ4009"]}],"id":[{"id":"10.13039\/501100004735","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP150103071"],"award-info":[{"award-number":["DP150103071"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP150102728"],"award-info":[{"award-number":["DP150102728"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00778-017-0487-0","type":"journal-article","created":{"date-parts":[[2017,10,24]],"date-time":"2017-10-24T02:53:30Z","timestamp":1508813610000},"page":"53-78","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":42,"title":["Efficient structure similarity searches: a partition-based approach"],"prefix":"10.1007","volume":"27","author":[{"given":"Xiang","family":"Zhao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7239-5134","authenticated-orcid":false,"given":"Chuan","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,24]]},"reference":[{"key":"487_CR1","doi-asserted-by":"crossref","unstructured":"Bi, F., Chang, L., Lin, X., Qin, L., Zhang, W.: Efficient subgraph matching by postponing Cartesian products. In: SIGMOD Conference, pp. 1199\u20131214 (2016)","DOI":"10.1145\/2882903.2915236"},{"issue":"4","key":"487_CR2","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0167-8655(83)90033-8","volume":"1","author":"H Bunke","year":"1983","unstructured":"Bunke, H., Allermann, G.: Inexact graph matching for structural pattern recognition. PRL 1(4), 245\u2013253 (1983)","journal-title":"PRL"},{"issue":"3","key":"487_CR3","first-page":"265","volume":"18","author":"D Conte","year":"2004","unstructured":"Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. IJPRAI 18(3), 265\u2013298 (2004)","journal-title":"IJPRAI"},{"key":"487_CR4","doi-asserted-by":"crossref","unstructured":"Fankhauser, S., Riesen, K., Bunke, H.: Speeding up graph edit distance computation through fast bipartite matching. In: GbRPR, pp. 102\u2013111 (2011)","DOI":"10.1007\/978-3-642-20844-7_11"},{"key":"487_CR5","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st edn. W. H. Freeman, San Francisco (1979)","edition":"1"},{"key":"487_CR6","doi-asserted-by":"crossref","unstructured":"Gouda, K., Arafa, M., Calders, T.: Bfst_ed: a novel upper bound computation framework for the graph edit distance. In: SISAP, pp. 3\u201319 (2016)","DOI":"10.1007\/978-3-319-46759-7_1"},{"key":"487_CR7","doi-asserted-by":"crossref","unstructured":"Gouda, K., Hassaan, M.: CSI_GED: an efficient approach for graph edit similarity computation. In: ICDE, pp. 265\u2013276 (2016)","DOI":"10.1109\/ICDE.2016.7498246"},{"key":"487_CR8","doi-asserted-by":"crossref","unstructured":"Gupta, M., Gao, J., Yan, X., Cam, H., Han, J.: Top-k interesting subgraph discovery in information networks. In: ICDE, pp. 820\u2013831 (2014)","DOI":"10.1109\/ICDE.2014.6816703"},{"key":"487_CR9","volume-title":"Data Mining: Concepts and Techniques","author":"J Han","year":"2011","unstructured":"Han, J., Kamber, M., Pei, J.: Data Mining: Concepts and Techniques, 3rd edn. Morgan Kaufmann, Los Altos (2011)","edition":"3"},{"key":"487_CR10","doi-asserted-by":"crossref","unstructured":"Han, W.-S., Lee, J., Lee, J.-H.: Turbo$$_{\\text{iso}}$$: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: SIGMOD Conference, pp. 337\u2013348 (2013)","DOI":"10.1145\/2463676.2465300"},{"key":"487_CR11","unstructured":"He, H., Singh, A.K.: Closure-Tree: an index structure for graph queries. In: ICDE, p. 38 (2006)"},{"key":"487_CR12","doi-asserted-by":"crossref","unstructured":"Jin, C., Bhowmick, S.S., Choi, B., Zhou, S.: PRAGUE: towards blending practical visual subgraph query formulation and query processing. In: ICDE, pp. 222\u2013233 (2012)","DOI":"10.1109\/ICDE.2012.49"},{"issue":"1","key":"487_CR13","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1021\/ci7001878","volume":"48","author":"RM Mar\u00edn","year":"2008","unstructured":"Mar\u00edn, R.M., Aguirre, N.F., Daza, E.E.: Graph theoretical similarity approach to compare molecular electrostatic potentials. J. Chem. Inf. Model. 48(1), 109\u2013118 (2008)","journal-title":"J. Chem. Inf. Model."},{"key":"487_CR14","doi-asserted-by":"crossref","unstructured":"Ranu, S., Hoang, M.X., Singh, A.K.: Answering top-$$k$$ representative queries on graph databases. In: SIGMOD Conference, pp. 1163\u20131174 (2014)","DOI":"10.1145\/2588555.2610524"},{"issue":"5","key":"487_CR15","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.patrec.2009.10.011","volume":"31","author":"R Raveaux","year":"2010","unstructured":"Raveaux, R., Burie, J.-C., Ogier, J.-M.: A graph matching method and a graph matching distance based on subgraph assignments. PRL 31(5), 394\u2013406 (2010)","journal-title":"PRL"},{"issue":"5","key":"487_CR16","first-page":"617","volume":"8","author":"X Ren","year":"2015","unstructured":"Ren, X., Wang, J.: Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs. PVLDB 8(5), 617\u2013628 (2015)","journal-title":"PVLDB"},{"key":"487_CR17","unstructured":"Riesen, K., Fankhauser, S., Bunke, H.: Speeding up graph edit distance computation with a bipartite heuristic. In: MLG (2007)"},{"issue":"3","key":"487_CR18","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1109\/TSMC.1983.6313167","volume":"13","author":"A Sanfeliu","year":"1983","unstructured":"Sanfeliu, A., Fu, K.-S.: A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cyber. 13(3), 353\u2013362 (1983)","journal-title":"IEEE Trans. Syst. Man Cyber."},{"key":"487_CR19","doi-asserted-by":"crossref","unstructured":"Shang, H., Lin, X., Zhang, Y., Yu, J.X., Wang, W.: Connected substructure similarity search. In: SIGMOD Conference, pp. 903\u2013914 (2010)","DOI":"10.1145\/1807167.1807264"},{"issue":"1","key":"487_CR20","first-page":"364","volume":"1","author":"H Shang","year":"2008","unstructured":"Shang, H., Zhang, Y., Lin, X., Yu, J.X.: Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. PVLDB 1(1), 364\u2013375 (2008)","journal-title":"PVLDB"},{"key":"487_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1671970.1921702","volume":"15","author":"JR Ullmann","year":"2010","unstructured":"Ullmann, J.R.: Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. ACM J. Exp. Algorithmics 15, 1\u20136 (2010)","journal-title":"ACM J. Exp. Algorithmics"},{"key":"487_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2699878","volume":"20","author":"JR Ullmann","year":"2015","unstructured":"Ullmann, J.R.: Degree reduction in labeled graph retrieval. ACM J. Exp. Algorithmics 20, 1\u20133 (2015)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"3","key":"487_CR23","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1109\/TKDE.2010.28","volume":"24","author":"G Wang","year":"2012","unstructured":"Wang, G., Wang, B., Yang, X., Yu, G.: Efficiently indexing large sparse graphs for similarity search. IEEE Trans. Knowl. Data Eng. 24(3), 440\u2013451 (2012)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"487_CR24","doi-asserted-by":"crossref","unstructured":"Wang, X., Ding, X., Tung, A.K.H., Ying, S., Jin, H.: An efficient graph indexing method. In: ICDE, pp. 210\u2013221 (2012)","DOI":"10.1109\/ICDE.2012.28"},{"key":"487_CR25","doi-asserted-by":"crossref","unstructured":"Yan, X., Yu, P.S., Han, J.: Graph indexing: a frequent structure-based approach. In: SIGMOD Conference, pp. 335\u2013346 (2004)","DOI":"10.1145\/1007568.1007607"},{"key":"487_CR26","doi-asserted-by":"crossref","unstructured":"Yan, X., Yu, P.S., Han, J.: Substructure similarity search in graph databases. In: SIGMOD Conference, pp. 766\u2013777 (2005)","DOI":"10.1145\/1066157.1066244"},{"key":"487_CR27","doi-asserted-by":"crossref","unstructured":"Yang, S., Han, F., Wu, Y., Yan, X.: Fast top-k search in knowledge graphs. In: ICDE (to appear) (2016)","DOI":"10.1109\/ICDE.2016.7498307"},{"key":"487_CR28","doi-asserted-by":"crossref","unstructured":"Yang, Z., Fu, A.W., Liu, R.: Diversified top-$$k$$ subgraph querying in a large graph. In: SIGMOD Conference, pp. 1167\u20131182 (2016)","DOI":"10.1145\/2882903.2915216"},{"issue":"1","key":"487_CR29","first-page":"25","volume":"2","author":"Z Zeng","year":"2009","unstructured":"Zeng, Z., Tung, A.K.H., Wang, J., Feng, J., Zhou, L.: Comparing stars: on approximating graph edit distance. PVLDB 2(1), 25\u201336 (2009)","journal-title":"PVLDB"},{"key":"487_CR30","doi-asserted-by":"crossref","unstructured":"Zhang, K., Wang, J.T.-L., Shasha, D.: On the editing distance between undirected acyclic graphs and related problems. In: CPM, pp. 395\u2013407 (1995)","DOI":"10.1007\/3-540-60044-2_58"},{"issue":"1","key":"487_CR31","first-page":"1185","volume":"3","author":"S Zhang","year":"2010","unstructured":"Zhang, S., Yang, J., Jin, W.: SAPPER: subgraph indexing and approximate matching in large graphs. PVLDB 3(1), 1185\u20131194 (2010)","journal-title":"PVLDB"},{"issue":"3","key":"487_CR32","first-page":"169","volume":"7","author":"X Zhao","year":"2013","unstructured":"Zhao, X., Xiao, C., Lin, X., Liu, Q., Zhang, W.: A partition-based approach to structure similarity search. PVLDB 7(3), 169\u2013180 (2013)","journal-title":"PVLDB"},{"issue":"6","key":"487_CR33","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/s00778-013-0306-1","volume":"22","author":"X Zhao","year":"2013","unstructured":"Zhao, X., Xiao, C., Lin, X., Wang, W., Ishikawa, Y.: Efficient processing of graph similarity queries with edit distance constraints. VLDB J. 22(6), 727\u2013752 (2013)","journal-title":"VLDB J."},{"issue":"4","key":"487_CR34","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1109\/TKDE.2014.2349924","volume":"27","author":"W Zheng","year":"2015","unstructured":"Zheng, W., Zou, L., Lian, X., Wang, D., Zhao, D.: Efficient graph similarity search over large graph databases. IEEE Trans. Knowl. Data Eng. 27(4), 964\u2013978 (2015)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"487_CR35","doi-asserted-by":"crossref","unstructured":"Zhu, Y., Qin, L., Yu, J.X., Cheng, H.: Finding top-$$k$$ similar graphs in graph databases. In: EDBT, pp. 456\u2013467 (2012)","DOI":"10.1145\/2247596.2247650"},{"issue":"1","key":"487_CR36","first-page":"85","volume":"8","author":"Y Zhu","year":"2014","unstructured":"Zhu, Y., Yu, J.X., Qin, L.: Leveraging graph dimensions in online graph search. PVLDB 8(1), 85\u201396 (2014)","journal-title":"PVLDB"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-017-0487-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-017-0487-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-017-0487-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T18:07:37Z","timestamp":1750961257000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-017-0487-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,24]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["487"],"URL":"https:\/\/doi.org\/10.1007\/s00778-017-0487-0","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,24]]},"assertion":[{"value":"19 February 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2017","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2017","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 October 2017","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}