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 satisfythe 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.
|Data di pubblicazione:||2005|
|Titolo:||Polynomial-time metrics for attributed trees|
|Rivista:||IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1109/TPAMI.2005.146|
|Appare nelle tipologie:||2.1 Articolo su rivista |