{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T18:47:17Z","timestamp":1759776437349},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540292302"},{"type":"electronic","value":"9783540316985"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11563983_17","type":"book-chapter","created":{"date-parts":[[2005,10,22]],"date-time":"2005-10-22T04:50:07Z","timestamp":1129956607000},"page":"189-202","source":"Crossref","is-referenced-by-count":7,"title":["The q-Gram Distance for Ordered Unlabeled Trees"],"prefix":"10.1007","author":[{"given":"Nobuhito","family":"Ohkura","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kouichi","family":"Hirata","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tetsuji","family":"Kuboyama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masateru","family":"Harao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Asai, T., Abe, K., Kawazoe, S., Arimura, H., Sakamoto, H., Arikawa, S.: Efficient substructure discovery from large semi-structured data. In: Proc. SDM 2002 (2002)","DOI":"10.1137\/1.9781611972726.10"},{"key":"17_CR2","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-540-39644-4_6","volume-title":"Discovery Science","author":"T. Asai","year":"2003","unstructured":"Asai, T., Arimura, H., Nakano, S., Uno, T.: Discovering frequent substructures in large unordered trees. In: Grieser, G., Tanaka, Y., Yamamoto, A. (eds.) DS 2003. LNCS (LNAI), vol.\u00a02843, pp. 47\u201361. Springer, Heidelberg (2003)"},{"key":"17_CR3","doi-asserted-by":"publisher","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.\u00a0337, 217\u2013239 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/3-540-48194-X_6","volume-title":"Combinatorial Pattern Matching","author":"S. Burkhardt","year":"2001","unstructured":"Burkhardt, S., Karkkainen, J.: Better filtering with gapped q-grams. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.\u00a02089, pp. 73\u201385. Springer, Heidelberg (2001)"},{"key":"17_CR5","series-title":"Lecture Notes in Artificial Intelligence","first-page":"351","volume-title":"Advances in Knowledge Discovery and Data Mining","author":"K. Furukawa","year":"2002","unstructured":"Furukawa, K., Uchida, T., Yamada, K., Miyahara, T., Shoudai, T., Nakamura, Y.: Extracting characteristic structures among words in semistructured documents. In: Chen, M.-S., Yu, P.S., Liu, B. (eds.) PAKDD 2002. LNCS (LNAI), vol.\u00a02336, pp. 351\u2013360. Springer, Heidelberg (2002)"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Garofalakis, M., Kumar, A.: Correlating XML data streams using tree-edit distance embeddings. In: Proc. PODS 2003, pp. 143\u2013154 (2003)","DOI":"10.1145\/773153.773168"},{"key":"17_CR7","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/3-540-45650-3_13","volume-title":"Discovery Science","author":"D. Ikeda","year":"2001","unstructured":"Ikeda, D., Yamada, Y., Hirokawa, S.: Eliminating useless parts in semi-structured documents using alternation counts. In: Jantke, K.P., Shinohara, A. (eds.) DS 2001. LNCS (LNAI), vol.\u00a02226, pp. 113\u2013127. Springer, Heidelberg (2001)"},{"key":"17_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/3-540-54345-7_67","volume-title":"Mathematical Foundations of Computer Science 1991","author":"P. Jokinen","year":"1991","unstructured":"Jokinen, P., Ukkonen, E.: Two algorithms for approximate string matching in static texts. In: Tarlecki, A. (ed.) MFCS 1991. LNCS, vol.\u00a0520, pp. 240\u2013248. Springer, Heidelberg (1991)"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/11560586_26","volume-title":"Theoretical Computer Science","author":"T. Kuboyama","year":"2005","unstructured":"Kuboyama, T., Shin, K., Miyahara, T., Yasuda, H.: A theoretical analysis of alignment and edit problems for trees. In: Coppo, M., Lodi, E., Pinna, G.M. (eds.) ICTCS 2005. LNCS, vol.\u00a03701, pp. 323\u2013337. Springer, Heidelberg (2005)"},{"key":"17_CR10","unstructured":"Nakano, S., Uno, T.: Efficient generation of rooted trees. National Institute of Informatics Technical Report NII-2003-005E (2003)"},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-540-30559-0_3","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S. Nakano","year":"2004","unstructured":"Nakano, S., Uno, T.: Constant time generation of trees with specified diameter. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 33\u201345. Springer, Heidelberg (2004)"},{"key":"17_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/3-540-45123-4_29","volume-title":"Combinatorial Pattern Matching","author":"G. Navarro","year":"2000","unstructured":"Navarro, G., Sutinen, E., Tanninen, J., Tarhio, J.: Indexing text with approximate q-grams. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol.\u00a01848, pp. 350\u2013363. Springer, Heidelberg (2000)"},{"key":"17_CR13","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/0020-0190(77)90064-3","volume":"6","author":"S.M. Selkow","year":"1997","unstructured":"Selkow, S.M.: The tree-to-tree editing problem. Inform. Proc. Let.\u00a06, 184\u2013186 (1997)","journal-title":"Inform. Proc. Let."},{"key":"17_CR14","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1016\/0196-6774(90)90011-3","volume":"11","author":"D. Shasha","year":"1990","unstructured":"Shasha, D., Zhang, K.: Fast algorithms for the unit cost edit distance between trees. J. Algo.\u00a011, 581\u2013621 (1990)","journal-title":"J. Algo."},{"key":"17_CR15","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-540-24775-3_43","volume-title":"Advances in Knowledge Discovery and Data Mining","author":"T. Uchida","year":"2004","unstructured":"Uchida, T., Mogawa, T., Nakamura, Y.: Finding frequent structural features among words in tree-structured documents. In: Dai, H., Srikant, R., Zhang, C. (eds.) PAKDD 2004. LNCS (LNAI), vol.\u00a03056, pp. 351\u2013360. Springer, Heidelberg (2004)"},{"key":"17_CR16","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0304-3975(92)90143-4","volume":"92","author":"E. Ukkonen","year":"1993","unstructured":"Ukkonen, E.: Approximate string-matching with q-grams and maximal matches. Theor. Comput. Sci.\u00a092, 191\u2013211 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR17","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1002\/spe.4380210706","volume":"21","author":"W. Yang","year":"1991","unstructured":"Yang, W.: Identifying syntactic differences between two programs. Software\u2013Practice and Experience\u00a021, 739\u2013755 (1991)","journal-title":"Software\u2013Practice and Experience"},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"Zaki, M.J.: Efficiently mining frequent trees in a forest. In: Proc. SIGKDD 2002, pp. 71\u201380 (2002)","DOI":"10.1145\/775047.775058"},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"Zhang, K., Shasha, D.: Tree pattern matching. In: Apostolico, A., Galil, Z. (eds.) Pattern matching algorithms, pp. 341\u2013371 (1997)","DOI":"10.1093\/oso\/9780195113679.003.0014"}],"container-title":["Lecture Notes in Computer Science","Discovery Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11563983_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T16:26:15Z","timestamp":1626625575000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11563983_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540292302","9783540316985"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11563983_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}