Exact and approximate algorithms for unordered tree matching
- 1 April 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics
- Vol. 24 (4) , 668-678
- https://doi.org/10.1109/21.286387
Abstract
We consider the problem of comparison between unordered trees, i.e., trees for which the order among siblings is unimportant. The criterion for comparison is the distance as measured by a weighted sum of the costs of deletion, insertion and relabel operations on tree nodes. Such comparisons may contribute to pattern recognition efforts in any field (e.g., genetics) where data can naturally be characterized by unordered trees. In companion work, we have shown this problem to be NP-complete. This paper presents an efficient enumerative algorithm and several heuristics leading to approximate solutions. The algorithms are based on probabilistic hill climbing and bipartite matching techniques. The paper evaluates the accuracy and time efficiency of the heuristics by applying them to a set of trees transformed from industrial parts based on a previously proposed morphological model.<>Keywords
This publication has 26 references indexed in Scilit:
- A tool for tree pattern matchingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Approximate Tree Matching in the Presence of Variable Length Don′t CaresJournal of Algorithms, 1994
- On the editing distance between unordered labeled treesInformation Processing Letters, 1992
- Fast serial and parallel algorithms for approximate tree matching with VLDC's (Extended Abstract)Published by Springer Nature ,1992
- Simple Fast Algorithms for the Editing Distance between Trees and Related ProblemsSIAM Journal on Computing, 1989
- Threshold decomposition of gray-scale morphology into binary morphologyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- The Tree-to-Tree Correction ProblemJournal of the ACM, 1979
- Representation of Random Waveforms by Relational TreesIEEE Transactions on Computers, 1976
- The String-to-String Correction ProblemJournal of the ACM, 1974
- Tree Systems for Syntactic Pattern RecognitionIEEE Transactions on Computers, 1973