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.
Torsello
Andrea
A
Dipartimento di Informatica, Università Ca' Foscari di Venezia, Via Torino 155, 30172 Venezia Mestre, Italy. torsello@dsi.unive.it
Hidović-Rowe
Dzena
D
Pelillo
Marcello
M
D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D003198:Computer Simulation; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D015233:Models, Statistical; D009716:Numerical Analysis, Computer-Assisted; D010363:Pattern Recognition, Automated / Q000379:methods*; D012815:Signal Processing, Computer-Assisted; D013997:Time Factors