Polynomial-Time Metrics for Attributed Trees.

Andrea Torsello, Dzena Hidovic Rowe, Marcello Pelillo

Abstract

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.
BibTeX
@article{torsello2005polynomial,
  author = {Andrea Torsello and Dzena Hidovic Rowe and Marcello Pelillo},
  title = {{Polynomial-Time Metrics for Attributed Trees.}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2005},
  url = {https://openreview.net/forum?id=SQKc7YSx_pB},
}

Loading related content...

Figure