A Polynomial-Time Metric for Attributed Trees
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.
Cite
Text
Torsello et al. "A Polynomial-Time Metric for Attributed Trees." European Conference on Computer Vision, 2004. doi:10.1007/978-3-540-24673-2_34Markdown
[Torsello et al. "A Polynomial-Time Metric for Attributed Trees." European Conference on Computer Vision, 2004.](https://mlanthology.org/eccv/2004/torsello2004eccv-polynomial/) doi:10.1007/978-3-540-24673-2_34BibTeX
@inproceedings{torsello2004eccv-polynomial,
title = {{A Polynomial-Time Metric for Attributed Trees}},
author = {Torsello, Andrea and Hidovic, Dzena and Pelillo, Marcello},
booktitle = {European Conference on Computer Vision},
year = {2004},
pages = {414-427},
doi = {10.1007/978-3-540-24673-2_34},
url = {https://mlanthology.org/eccv/2004/torsello2004eccv-polynomial/}
}