A Polynomial-Time Metric for Attributed Trees

Andrea Torsello, Dzena Hidovic, Marcello Pelillo

Abstract

We address the problem of comparing attributed trees and propose a novel distance measure centered around the notion of a maximal similarity common subtree. The proposed measure is general and defined on trees endowed with either symbolic or continuous-valued attributes, and can be equally applied to ordered and unordered, rooted and unrooted trees. We prove that our measure satisfies the metric constraints and provide a polynomial-time algorithm to compute it. This is a remarkable and attractive property since the computation of traditional edit-distance-based metrics is NP-complete, except for ordered structures. We experimentally validate the usefulness of our metric on shape matching tasks, and compare it with edit-distance measures.
BibTeX
@inproceedings{torsello2004polynomial,
  author = {Andrea Torsello and Dzena Hidovic and Marcello Pelillo},
  title = {{A Polynomial-Time Metric for Attributed Trees}},
  booktitle = {European Conference on Computer Vision},
  year = {2004},
  doi = {10.1007/978-3-540-24673-2\_34},
}

Loading related content...

Figure