Abstract

We address the problem of comparing attributed trees and propose a novel distance measure centered around the notion of a max- imal similarity common subtree. The proposed measure is general and defined on trees endowed with either symbolic or continuous-valued at- tributes, and can be equally applied to ordered and unordered, rooted and unrooted trees. We prove that our measure satisfies the metric con- straints and provide a polynomial-time algorithm to compute it. This is a remarkable and attractive property since the computation of tra- ditional 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.