{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,7]],"date-time":"2024-07-07T09:54:57Z","timestamp":1720346097672},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2015,7,19]],"date-time":"2015-07-19T00:00:00Z","timestamp":1437264000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s10472-015-9467-5","type":"journal-article","created":{"date-parts":[[2015,7,17]],"date-time":"2015-07-17T22:42:21Z","timestamp":1437172941000},"page":"419-460","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A theory of subtree matching and tree kernels based on the edit distance concept"],"prefix":"10.1007","volume":"75","author":[{"given":"Kilho","family":"Shin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,19]]},"reference":[{"issue":"4","key":"9467_CR1","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/s00778-011-0254-6","volume":"21","author":"N Augsten","year":"2012","unstructured":"Augsten, N., B\u00f6hlen, M.H., Dyreson, C.E., Gamper, J.: Windowed pq-grams for approximate joins of data-centric XML. VLDB J. 21(4), 463\u2013488 (2012)","journal-title":"VLDB J."},{"key":"9467_CR2","doi-asserted-by":"crossref","unstructured":"Augsten, N., Bhlen, M.H., Gamper, J.: The pq-gram distance between ordered labeled trees. ACM Trans. Database Syst. 35(1) (2010)","DOI":"10.1145\/1670243.1670247"},{"key":"9467_CR3","volume-title":"Tree-to-tree correction for document trees, technical report 95-375","author":"D Barnard","year":"1995","unstructured":"Barnard, D., Clarke, G., Duncan, N.: Tree-to-tree correction for document trees, technical report 95-375. Queen\u2019s University, Kingston (1995)"},{"key":"9467_CR4","doi-asserted-by":"crossref","unstructured":"Berg, C., Christensen, J.P.R., Ressel, R.: Harmonic analysis on semigroups, theory of positive definite and related functions. Springer (1984)","DOI":"10.1007\/978-1-4612-1128-0"},{"issue":"1-3","key":"9467_CR5","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","volume":"337","author":"P Bille","year":"2005","unstructured":"Bille, P.: A survey on tree edit distance and related problems. Theor. Comput. Sci. 337(1-3), 217\u2013239 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9467_CR6","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1016\/S0167-8655(97)00060-3","volume":"18","author":"H Bunke","year":"1997","unstructured":"Bunke, H.: On a relation between graph edit distance and maximum common subgraph. Pattern Recognit. Lett. 18, 689\u2013694 (1997)","journal-title":"Pattern Recognit. Lett."},{"key":"9467_CR7","unstructured":"Chang, C.-C., Lin, C.-J.: Libsvm: a library for support vector machines (2001). http:\/\/www.csie.ntu.edu.tw\/~cjlin\/libsvm\/"},{"key":"9467_CR8","doi-asserted-by":"crossref","unstructured":"Cohen, S., Or, N.: A general algorithm for subtree similarity-search. In: IEEE 30th international conference on data engineering, pp 928\u2013939 (2014)","DOI":"10.1109\/ICDE.2014.6816712"},{"key":"9467_CR9","doi-asserted-by":"crossref","unstructured":"Marteau, P.-F., Gibet, S.: On recursive edit distance kernels with application to time series classification, IEEE Transactions on Neural Networks and Learning Systems (2014)","DOI":"10.1109\/TNNLS.2014.2333876"},{"key":"9467_CR10","doi-asserted-by":"crossref","unstructured":"Collins, M., Duffy, N.: Convolution kernels for natural language. In: Advances in neural information processing systems 14 [neural information processing systems: natural and synthetic, NIPS 2001], pp 625\u2013632. MIT Press (2001)","DOI":"10.7551\/mitpress\/1120.003.0085"},{"key":"9467_CR11","first-page":"1","volume":"1","author":"C Cortes","year":"2004","unstructured":"Cortes, C., Haffner, P., Mohri, M.: Rational kernels: theory and algorithms. J. Mach. Learn. Res. 1, 1\u201350 (2004)","journal-title":"J. Mach. Learn. Res."},{"key":"9467_CR12","unstructured":"Demaine, E.D., Mozes, S., Rossman, B., Weimann, O.: An optimal decomposition algorithm for tree edit distance. ACM Trans. Algo. (2006)"},{"key":"9467_CR13","first-page":"1","volume":"7","author":"J Dem\u0161ar","year":"2006","unstructured":"Dem\u0161ar, J.: Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Theory 7, 1\u201330 (2006)","journal-title":"J. Mach. Learn. Theory"},{"key":"9467_CR14","doi-asserted-by":"crossref","unstructured":"Dulucq, S., Touzet, H.: Analysis of tree edit distance algorithms. In: the 14th annual symposium on combinatorial pattern matching (CPM), pp 83\u201395 (2003)","DOI":"10.1007\/3-540-44888-8_7"},{"key":"9467_CR15","first-page":"2677","volume":"9","author":"HFS Garcia","year":"2008","unstructured":"Garcia, H.F.S.: An extension on Statistical comparisons of classifiers over multiple data sets for all pairwise comparisons. J. Mach. Learn. Theory 9, 2677\u20132694 (2008)","journal-title":"J. Mach. Learn. Theory"},{"issue":"1","key":"9467_CR16","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1145\/959242.959248","volume":"5","author":"T G\u00e4rtner","year":"2003","unstructured":"G\u00e4rtner, T.: A survey of kernels for structured data. SIGKDD Explorations 5(1), 49\u201358 (2003)","journal-title":"SIGKDD Explorations"},{"key":"9467_CR17","doi-asserted-by":"crossref","first-page":"63R","DOI":"10.1093\/glycob\/cwj010","volume":"16","author":"K Hashimoto","year":"2006","unstructured":"Hashimoto, K., Goto, S., Kawano, S., Aoki-Kinoshita, K.F., Ueda, N.: Kegg as a glycome informatics resource. Glycobiology 16, 63R\u201370R (2006)","journal-title":"Glycobiology"},{"key":"9467_CR18","unstructured":"Haussler, D.: Convolution kernels on discrete structures. UCSC-CRL 99-10, Dept. of Computer Science, University of California at Santa Cruz (1999)"},{"key":"9467_CR19","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1093\/biomet\/75.2.383","volume":"75","author":"G Hommel","year":"1988","unstructured":"Hommel, G.: A stagewise rejective multiple test procedure based on a modified bonferroni tests. Biometrika 75, 383\u2013386 (1988)","journal-title":"Biometrika"},{"key":"9467_CR20","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0304-3975(95)80029-9","volume":"143","author":"T Jiang","year":"1995","unstructured":"Jiang, T., Wang, L., Zhang, K.: Alignment of trees \u2014 an alternative to tree edit. Theor. Comput. Sci. 143, 137\u2013148 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"9467_CR21","unstructured":"Kashima, H., Koyanagi, T.: Kernels for semi-structured data. In: the 9th international conference on machine learning (ICML 2002), pp 291\u2013298 (2002)"},{"key":"9467_CR22","first-page":"91","volume":"1461","author":"PN Klein","year":"1998","unstructured":"Klein, P.N.: Computing the edit-distance between unrooted ordered trees. LNCS 1461, 91\u2013102 (1998). ESA\u201998","journal-title":"LNCS"},{"key":"9467_CR23","unstructured":"Kuboyama, T., Shin, K., Kashima, H.: Flexible tree kernels based on counting the number of tree mappings. In: Proceeding of machine learning with graphs (2006)"},{"key":"9467_CR24","doi-asserted-by":"crossref","unstructured":"Kuboyama, T., Shin, K., Miyahara, T., Yasuda, H.: A theoretical analysis of alignment and edit problems for trees. In: Proceeding of theoretical computer science, the 9th Italian Conference, lecture notes in computer science, vol. 3701, pp 323\u2013337 (2005)","DOI":"10.1007\/11560586_26"},{"key":"9467_CR25","unstructured":"Kuboyama, T.: Matching and Learning in Trees. PhD thesis, Department of Advanced Interdisciplinary Studies, The University of Tokyo (2007)"},{"key":"9467_CR26","doi-asserted-by":"crossref","unstructured":"Lu, C. L., Su, Z.Y., Tang, G.Y.: A new measure of edit distance between labeled trees. In: LNCS, vol. 2108, pp 338\u2013348. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-44679-6_37"},{"key":"9467_CR27","first-page":"219","volume":"1","author":"SY Lu","year":"1979","unstructured":"Lu, S.Y.: A tree-to-tree distance and its application to cluster analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) 1, 219\u2013224 (1979)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)"},{"issue":"1","key":"9467_CR28","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1145\/1061318.1061326","volume":"30","author":"G Minos","year":"2005","unstructured":"Minos, G., Amit, K.: Xml stream processing using tree-edit distance embeddings. ACM Trans. Database Syst. 30(1), 279\u2013332 (2005)","journal-title":"ACM Trans. Database Syst."},{"key":"9467_CR29","unstructured":"Moschitti, A.: Example data for TREE KERNELS IN SVM-LIGHT. http:\/\/disi.unitn.it\/moschitti\/Tree-Kernel.htm"},{"issue":"10","key":"9467_CR30","doi-asserted-by":"crossref","first-page":"1852","DOI":"10.1016\/j.patcog.2006.04.012","volume":"39","author":"M Neuhaus","year":"2006","unstructured":"Neuhaus, M., Bunke, H.: Edit distance-based kernel functions for structural pattern classification. Pattern Recogn. 39(10), 1852\u20131863 (2006)","journal-title":"Pattern Recogn."},{"key":"9467_CR31","doi-asserted-by":"crossref","unstructured":"Neuhaus, M., Bunke, H.: Bridging the gap between graph edit distance and kernel machines. World Scientific (2007)","DOI":"10.1142\/9789812770202"},{"key":"9467_CR32","doi-asserted-by":"crossref","unstructured":"Pawlik, M., Augsten, N.: Rted: A robust algorithm for the tree edit distance. In: Proceedings of the VLDB Endowment, vol. 5, pp 334\u2013345 (2011)","DOI":"10.14778\/2095686.2095692"},{"key":"9467_CR33","unstructured":"Richter, T.: A new measure of the distance between ordered trees and its applications, Technical Report 85166-CS, Dept. of Computer Science, Univ. of Bonn (1997)"},{"issue":"6","key":"9467_CR34","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1109\/TSMCB.2009.2019264","volume":"39","author":"K Riesen","year":"2009","unstructured":"Riesen, K., Bunke, H.: Graph classification by means of lipschitz embedding. IEEE Trans. Syst. Man Cybern. Part B Cybern. 39(6), 1472\u20131483 (2009)","journal-title":"IEEE Trans. Syst. Man Cybern. Part B Cybern."},{"key":"9467_CR35","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1090\/S0002-9947-1938-1501980-0","volume":"44","author":"IJ Schoenberg","year":"1938","unstructured":"Schoenberg, I.J.: Metric spaces and positive definite functions. Trans. Amer. Math. Soc. 44, 522\u2013536 (1938)","journal-title":"Trans. Amer. Math. Soc."},{"key":"9467_CR36","unstructured":"Sch\u00f6lkopf, B.: The kernel trick for distances. In: Advances in neural information processing systems 13 (NIPS 2000), pp 301\u2013307 (2000)"},{"key":"9467_CR37","unstructured":"Shin, K., Cuturi, M., Kuboyama, T.: Mapping kernels for trees. In: ICML 2011 (2011)"},{"key":"9467_CR38","doi-asserted-by":"crossref","unstructured":"Shin, K., Kuboyama, T.: A generalization of Haussler\u2019s convolution kernel - mapping kernel. In: ICML 2008 (2008)","DOI":"10.1145\/1390156.1390275"},{"issue":"5","key":"9467_CR39","doi-asserted-by":"crossref","first-page":"1040","DOI":"10.1007\/s11390-010-9386-1","volume":"25","author":"K Shin","year":"2010","unstructured":"Shin, K., Kuboyama, T.: Generalization of haussler\u2019s convolution kernel - mapping kernel and its application to tree kernels. J. Comput. Sci. Technol. 25(5), 1040\u20131054 (2010)","journal-title":"J. Comput. Sci. Technol."},{"issue":"1","key":"9467_CR40","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.ipl.2014.09.002","volume":"115","author":"K Shin","year":"2015","unstructured":"Shin, K.: Tree edit distance and maximum agreement subtree. Inf. Process. Lett. 115(1), 69\u201373 (2015)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9467_CR41","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/322139.322143","volume":"26","author":"KC Ta\u00ef","year":"1979","unstructured":"Ta\u00ef, K.C.: The tree-to-tree correction problem. J. ACM 26(3), 422\u2013433 (1979)","journal-title":"J. ACM"},{"issue":"1","key":"9467_CR42","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM 21(1), 168\u2013173 (1974)","journal-title":"J. ACM"},{"key":"9467_CR43","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/S0031-3203(99)00199-5","volume":"34","author":"JTL Wang","year":"2001","unstructured":"Wang, J.T.L., Zhang, K.: Finding similar consensus between trees: an algorithm and a distance hierarchy. Pattern Recogn. 34, 127\u2013137 (2001)","journal-title":"Pattern Recogn."},{"key":"9467_CR44","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s10994-006-5832-2","volume":"62","author":"MJ Zaki","year":"2006","unstructured":"Zaki, M.J., Aggarwal, C.C.: XRules: an effective algorithm for structural classification of XML data. Mach. Learn. 62, 137\u2013170 (2006)","journal-title":"Mach. Learn."},{"issue":"3","key":"9467_CR45","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1016\/0031-3203(94)00109-Y","volume":"28","author":"K Zhang","year":"1995","unstructured":"Zhang, K.: Algorithms for the constrained editing distance between ordered labeled trees and related problems. Pattern Recogn. 28(3), 463\u2013474 (1995)","journal-title":"Pattern Recogn."},{"issue":"6","key":"9467_CR46","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"K Zhang","year":"1989","unstructured":"Zhang, K., Shasha, D.: Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput. 18(6), 1245\u20131262 (1989)","journal-title":"SIAM J. Comput."}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-015-9467-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-015-9467-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-015-9467-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T01:50:36Z","timestamp":1717984236000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-015-9467-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,19]]},"references-count":46,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["9467"],"URL":"https:\/\/doi.org\/10.1007\/s10472-015-9467-5","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,19]]}}}