A Polynomial-Time Metric for Attributed Trees
Lists
Only you see this
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...