Projects per year
Defining and computing distances between tree structures is a classical area of study in theoretical computer science, with practical applications in the areas of computational biology, information retrieval, text analysis, and many others. In this paper, we focus on rooted, unordered, uniquely-labelled trees such as taxonomies and other hierarchies. For trees as these, we introduce the intuitive concept of a 'local move' operation as an atomic edit of a tree. We then introduce SuMoTED, a new edit distance measure between such trees, defined as the minimal number of local moves required to convert one tree into another. We show how SuMoTED can be computed using a scalable algorithm with quadratic time complexity. Finally, we demonstrate its use on a collection of music genre taxonomies.
|Number of pages||8|
|Journal||Pattern Recognition Letters|
|Early online date||4 May 2016|
|Publication status||Published - 1 Aug 2016|
- Tree edit distance
FingerprintDive into the research topics of 'SuMoTED: An intuitive edit distance between rooted unordered uniquely-labelled trees'. Together they form a unique fingerprint.
- 1 Finished
Data Science for the Detection of Emerging Music Styles
De Bie, T. E. P.
1/11/14 → 1/11/16