Skip to content

SuMoTED: An intuitive edit distance between rooted unordered uniquely-labelled trees

Research output: Contribution to journalArticle

  • Matt McVicar
  • Benjamin Sach
  • Cédric Mesnage
  • Jefrey Lijffijt
  • Eirini Spyropoulou
  • Tijl De Bie
Original languageEnglish
Pages (from-to)52-59
Number of pages8
JournalPattern Recognition Letters
Volume79
Early online date4 May 2016
DOIs
DateAccepted/In press - 12 Apr 2016
DateE-pub ahead of print - 4 May 2016
DatePublished (current) - 1 Aug 2016

Abstract

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.

    Research areas

  • Taxonomies, Tree edit distance

Download statistics

No data available

Documents

Documents

  • Full-text PDF (final published version)

    Rights statement: This is the final published version of the article (version of record). It first appeared online via Elsevier at http://doi.org/10.1016/j.patrec.2016.04.012 . Please refer to any applicable terms of use of the publisher.

    Final published version, 818 KB, PDF document

    Licence: CC BY

DOI

View research connections

Related faculties, schools or groups