Segmental Mapping and Distance for Rooted Labeled Ordered Trees

• Autorzy: Kan T. , Higuchi S. , Hirata K.

Identyfikatory

DOI

10.3233/FI-2014-1054

• Języki publikacji: EN

Abstrakty

EN

In this paper, as variations of a Tai mapping between rooted labeled ordered trees (trees, for short), we introduce a segmentalmapping to preserve the parent-children relationship as possible, and also top-down segmengal and bottom-up segmental mappings as the segmental mappings that contain the pair of the roots and the pair of the leaves, respectively. Then, we show that these mappings provide a new hierarchy for the variations of the Tai mapping in addition to a well-known one, in particular, the top-down segmental mapping coincides with a top-down mapping. Also we show that both segmental and bottom-up segmental distances as the minimumcosts of segmental and bottom-up segmental mappings are metrics. Next, we design algorithms to compute the segmental and the bottom-up segmental distances in quadratic time and space. Finally, we give experimental results for the segmental distance.

Słowa kluczowe

EN

tree edit distance; segmental distance; Tai mapping; rooted labeled ordered trees

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 132, nr 4
• Strony: 461--483
• Opis fizyczny: Bibliogr. 23 poz., rys., tab., wykr.

Twórcy

autor

Kan T.

• Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan

autor

Higuchi S.

• Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan

autor

Hirata K.

• Department of Artificial Intelligence & Biomedical Informatics R&D Center, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan

Bibliografia

• [1] Akutsu, T., Fukagawa, D., Halldórsson,M. M., Takasu, A., Kaneta, K.: Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees, Theoretical Computer Science 470,10–22, 2013.
• [2] Chawathe, S. S.: Comparing hierarchical data in external memory, Proc. 25th International Conference on Very Large Data Bases (VLDB 1999), 90–101, 1999.
• [3] Demaine, E. D., Mozes, S., Rossman, B., Weimann, O.: An optimal decomposition algorithm for tree edit distance, ACM Transactions on Algorithms 6, 2009.
• [4] Hirata, K., Yamamoto, Y., Kuboyama, T.: Improved MAX SNP-hard results for finding an edit distance between unordered trees, Proc. 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), Lecture Notes in Computer Science 6661, 402–415, 2011.
• [5] KEGG: Kyoto Encyclopedia of Genes and Genoms, http://www.kegg.jp/.
• [6] Kuboyama, T.: Matching and learning in trees, Ph.D thesis, University of Tokyo, 2007. (Available at: http://tk.cc.gakushuin.ac.jp/doc/kuboyama2007phd.pdf)
• [7] Kuboyama, T., Shin, K., Kashima, H.: Flexible tree kernels based on counting the number of tree mappings, Proc. Mining and Learning with Graphs, 61–72, 2006.
• [8] Lu, S.-Y.: A tree-to-tree distance and its application to cluster analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence 1, 219–224, 1979.
• [9] Luke, S. and Panait, L: A survey and comparison of tree generation algorithms, Proc. Genetic and Evolutionary Computation Conference (GECCO 2001), 81–88, 2001.
• [10] Selkow, S. M.: The tree-to-tree editing problem, Information Processing Letters 6, 184–186, 1977.
• [11] Shin, K., Cuturi, M., Kuboyama, T.: Mapping kernels for trees, Proc. 28th International Conference on Machine Learning (ICML 2011), 961–968, 2011.
• [12] Tai, K.-C.: The tree-to-tree correction problem, J. ACM 26, 422–433, 1979.
• [13] Valiente, G.: An efficient bottom-up distance between trees, Proc. 8th International Symposium on String Processing and Infromation Retrieval (SPIRE 2001), 212–219, 2001.
• [14] Valiente, G.: Algorithms on trees and graphs, Springer, 2002.
• [15] Wang, J. T. L., Zhang, K.: Finding similar consensus between trees: An algorithm and a distance hierarchy, Pattern Recogition 34, 127–137, 2001.
• [16] Wang, L., Zhang, K.: Space efficient algorithms for ordered tree comparision, Algorithmica 51, 283–297, 2008.
• [17] Yamamoto, Y., Hirata, K., Kuboyama, T.: A bottom-up edit distance between rooted labeled trees, Proc. 7th Workshop on Learning with Logics and Logics for Learning (LLLL 2011), 26–33, 2011.
• [18] Yamamoto, Y., Hirata, K., Kuboyama, T.: Tractable and intractable variations of unordered tree edit distance, International Journal of Foundations of Computer Science (to appear).
• [19] Zhang, K.: Algorithms for the constrained editing distance between ordered labeled trees and related problems, Pattern Recogition 28, 463–474, 1995.
• [20] Zhang, K.: A constrained edit distance between unordered labeled trees, Algorithmica 15, 205-222, 1996.
• [21] Zhang, K., Jiang, T.: Some MAX SNP-hard results concerning unordered labeled trees, Information Processing Lettters 49, 249–254, 1994.
• [22] Zhang, K., Shasha, D.: Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing 18, 1245–1262, 1989.
• [23] Zhang, K., Wang, J. T. L., Shasha, D.: On the editing distance between undirected acyclic graph, International Journal of Foundations of Computer Science 7, 43–58, 1995.