TY - GEN
T1 - Pattern matching in unordered trees (Extended Abstract)
AU - Shasha, D.
AU - Wang, J. T.L.
AU - Zhang, K.
AU - Shih, F. Y.
PY - 1992
Y1 - 1992
N2 - We consider the problem of comparison between tmordered 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. We first observe that the problem is NP-complete. Then we present an 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.
AB - We consider the problem of comparison between tmordered 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. We first observe that the problem is NP-complete. Then we present an 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.
UR - http://www.scopus.com/inward/record.url?scp=84919298849&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84919298849&partnerID=8YFLogxK
U2 - 10.1109/TAI.1992.246429
DO - 10.1109/TAI.1992.246429
M3 - Conference contribution
AN - SCOPUS:84919298849
T3 - Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI
SP - 352
EP - 361
BT - 4th International Conference on Tools with Artificial Intelligence, ICTAI 1992
PB - IEEE Computer Society
T2 - 4th International Conference on Tools with Artificial Intelligence, ICTAI 1992
Y2 - 10 November 1992 through 13 November 1992
ER -