Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes

• Autorzy: Aratsu T. , Hirata K. , Kuboyama T.
• Języki publikacji: EN

Abstrakty

EN

This article proposes an approximation of the tree edit distance through the string edit distance for binary tree codes, instead of for Euler strings introduced by Akutsu (2006). Here, a binary tree code is a string obtained by traversing a binary tree representation with two kinds of dummy nodes of a tree in preorder. Then, we show that σ/2≤τ≤(h+1)σ+h, where τ is the tree edit distance between trees, and is the string edit distance between their binary tree codes and h is the minimum height of the trees.

Słowa kluczowe

EN

tree edit distance; string edit distance; binary tree code; binary tree representation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 101, nr 3
• Strony: 157--171
• Opis fizyczny: Bibliogr. 13 poz., wykr.

Twórcy

autor

Aratsu T.

autor

Hirata K.

autor

Kuboyama T.

• Dep. of Art. Intel., Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan,

Bibliografia

• [1] Akutsu, T.: A relationship between edit distance for ordered trees and edit distance for Euler strings, Information Processing Letters 100, 2006, 105-109.
• [2] Akutsu, T., Fukagawa, D., Takasu, A.: Approximating tree edit distance through string edit distance, Algorithmica 57, 2010, 325-348.
• [3] Aratsu, T., Hirata, K., Kuboyama, T.: Sibling distance for rooted ordered trees, Proc. JSAI PAKDD 2008 Post-Workshop Proceedings, LNAI 5433, 2009, 99-110.
• [4] Bille, P.: A survey on tree edit distance and related problems, Theoretical Computer Science 337, 2005, 217-239.
• [5] Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves, ACM Transactions on Algorithms 3, 2007, 1-19.
• [6] Demaine, E. D., Mozes, S., Rossman, B., Weimann, O.: An optimal decomposition algorithm for tree edit distance, Proc. ICALP'07, LNCS 4596, 2007, 146-157.
• [7] Garofalakis, M., Kumar, A.: XML stream processing using tree-edit distance embeddings, ACMTransactions on Database System 30, 2006, 279-332.
• [8] Kailing, K., Kriegel, H.-P., Schönauer, S., Seidl, T.: Efficient similarity search for hierarchical data in large databases, Proc. EBDT'04, LNCS 2992, 2004, 676-693.
• [9] Knuth, D. E.: The art of computer programing, Vol. 1, Fundamental algorithms (Third Edition), Addison-Wesley, 1997.
• [10] Magniez, F., de RougemontM.: Property testing of regular tree languages, Algorithmica 42, 2007, 127-146.
• [11] Valiente, G.: An efficient bottom-up distance between trees, Proc. SPIRE'01, 2001, 212-219.
• [12] Yang, R., Kalnis, P., Tung, A. K. H.: Similarity evaluation on tree-structured data, Proc. SIGMOD'05, 2005, 754-765.
• [13] Zhang, K., Shasha, D.: Simple fast algorithms for the editing distance between trees and related problems, SIAM J. Comput. 18, 1989, 1245-1262.