Polynomial-time metrics for attributed trees
We address the problem of comparing attributed trees and propose four novel distance measures centered around the notion of a maximal similarity common subtree. The proposed measures are general and defined on trees endowed with either symbolic or continuous- valued attributes and can be applied to rooted as well as unrooted trees. We prove that our measures satisfy the metric constraints and provide a polynomial- time algorithm to compute them. This is a remarkable and attractive property, since the computation of traditional edit- distance- based metrics is, in general, NP- complete, at least in the unordered case. We experimentally validate the usefulness of our metrics on shape matching tasks and compare them with ( an approximation of) edit- distance.
metrics time algorithms tree matching polynomial shape recognition