{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:36:42Z","timestamp":1725475002644},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540496946"},{"type":"electronic","value":"9783540496960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11940128_11","type":"book-chapter","created":{"date-parts":[[2006,11,29]],"date-time":"2006-11-29T05:57:35Z","timestamp":1164779855000},"page":"90-99","source":"Crossref","is-referenced-by-count":5,"title":["Approximating Tree Edit Distance Through String Edit Distance"],"prefix":"10.1007","author":[{"given":"Tatsuya","family":"Akutsu","sequence":"first","affiliation":[]},{"given":"Daiji","family":"Fukagawa","sequence":"additional","affiliation":[]},{"given":"Atsuhiro","family":"Takasu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.ipl.2006.06.002","volume":"100","author":"T. Akutsu","year":"2006","unstructured":"Akutsu, T.: A relation between edit distance for ordered trees and edit distance for Euler strings. Information Processing Letters\u00a0100, 105\u2013109 (2006)","journal-title":"Information Processing Letters"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Batu, T., Ergun, F., Sahinalp, C.: Oblivious string embeddings and edit distance approximations. In: Proc. 17th ACM-SIAM Symp. Discrete Algorithms, pp. 792\u2013801 (2006)","DOI":"10.1145\/1109557.1109644"},{"key":"11_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 problem. Theoretical Computer Science\u00a0337, 217\u2013239 (2005)","journal-title":"Theoretical Computer Science"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1006\/jagm.2001.1170","volume":"40","author":"W. Chen","year":"2001","unstructured":"Chen, W.: New algorithm for ordered tree-to-tree correction problem. Journal of Algorithms\u00a040, 135\u2013158 (2001)","journal-title":"Journal of Algorithms"},{"key":"11_CR5","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. In: Proc. 13th ACM-SIAM Symp. Discrete Algorithms, pp. 667\u2013676 (2002)"},{"key":"11_CR6","unstructured":"Demaine, E., Mozes, S., Rossman, B., Weimann, O.: An O(n3)-time algorithm for tree edit distance. Preprint cs.DS\/0604037 (2006)"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1007\/978-3-540-30551-4_40","volume-title":"Algorithms and Computation","author":"D. Fukagawa","year":"2004","unstructured":"Fukagawa, D., Akutsu, T.: Fast algorithms for comparison of similar unordered trees. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 452\u2013463. Springer, Heidelberg (2004)"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1145\/1061318.1061326","volume":"30","author":"M. Garofalakis","year":"2005","unstructured":"Garofalakis, M., Kumar, A.: XML stream processing using tree-edit distance embedding. ACM Trans. Database Systems\u00a030, 279\u2013332 (2005)","journal-title":"ACM Trans. Database Systems"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Guha, S., Jagadish, H.V., Koudas, N., Srivastava, D., Yu, T.: Approximate XML joins. In: Proc. ACM SIGMOD, pp. 287\u2013298 (2002)","DOI":"10.1145\/564691.564725"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Khot, S., Naor, A.: Nonembeddability theorems via Fourier analysis. In: Proc. 46th IEEE Symp. Foundations on Computer Science, pp. 101\u2013110 (2005)","DOI":"10.1109\/SFCS.2005.54"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Klein, P.N.: Computing the edit-distance between unrooted ordered trees. In: Proc. 6th European Symp. Algorithms, pp. 91\u2013102 (1998)","DOI":"10.1007\/3-540-68530-8_8"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Rabani, R.: Improved lower bounds for embeddings into L 1. In: Proc. 17th ACM-SIAM Symp. Discrete Algorithms, pp. 1010\u20131017 (2006)","DOI":"10.1145\/1109557.1109669"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y.: Low distortion embeddings for edit distance. In: Proc. 37th ACM Symp. Theory of Computing, pp. 218\u2013224 (2005)","DOI":"10.1145\/1060590.1060623"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/322139.322143","volume":"26","author":"K.-C. Tai","year":"1979","unstructured":"Tai, K.-C.: The tree-to-tree correction problem. J. ACM\u00a026, 422\u2013433 (1979)","journal-title":"J. ACM"},{"key":"11_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04921-1","volume-title":"Algorithms on Trees and Graphs","author":"G. Valiente","year":"2002","unstructured":"Valiente, G.: Algorithms on Trees and Graphs. Springer, Heidelberg (2002)"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Yang, R., Kalnis, P., Tang, A.K.H.: Similarity evaluation on tree-structured data. In: Proc. ACM SIGMOD, pp. 754\u2013765 (2005)","DOI":"10.1145\/1066157.1066243"},{"key":"11_CR17","doi-asserted-by":"publisher","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. Computing\u00a018, 1245\u20131262 (1989)","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11940128_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:49:41Z","timestamp":1619509781000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11940128_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540496946","9783540496960"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11940128_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}