Advanced search
1 file | 851.66 KB

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

Author
Organization
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.
Keywords
ALGORITHMS, CONSENSUS, Tree edit distance, Taxonomies

Downloads

  • mcvicar2016.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 851.66 KB

Citation

Please use this url to cite or link to this publication:

Chicago
McVicar, Matt, Benjamin Sach, Cedric Mesnage, Jefrey Lijffijt, Eirini Spyropoulou, and Tijl De Bie. 2016. “SuMoTED : an Intuitive Edit Distance Between Rooted Unordered Uniquely-labelled Trees.” Pattern Recognition Letters 79: 52–59.
APA
McVicar, Matt, Sach, B., Mesnage, C., Lijffijt, J., Spyropoulou, E., & De Bie, T. (2016). SuMoTED : an intuitive edit distance between rooted unordered uniquely-labelled trees. PATTERN RECOGNITION LETTERS, 79, 52–59.
Vancouver
1.
McVicar M, Sach B, Mesnage C, Lijffijt J, Spyropoulou E, De Bie T. SuMoTED : an intuitive edit distance between rooted unordered uniquely-labelled trees. PATTERN RECOGNITION LETTERS. 2016;79:52–9.
MLA
McVicar, Matt, Benjamin Sach, Cedric Mesnage, et al. “SuMoTED : an Intuitive Edit Distance Between Rooted Unordered Uniquely-labelled Trees.” PATTERN RECOGNITION LETTERS 79 (2016): 52–59. Print.
@article{7203579,
  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.},
  author       = {McVicar, Matt and Sach, Benjamin and Mesnage, Cedric and Lijffijt, Jefrey and Spyropoulou, Eirini and De Bie, Tijl},
  issn         = {0167-8655},
  journal      = {PATTERN RECOGNITION LETTERS},
  keywords     = {ALGORITHMS,CONSENSUS,Tree edit distance,Taxonomies},
  language     = {eng},
  pages        = {52--59},
  title        = {SuMoTED : an intuitive edit distance between rooted unordered uniquely-labelled trees},
  url          = {http://dx.doi.org/10.1016/j.patrec.2016.04.012},
  volume       = {79},
  year         = {2016},
}

Altmetric
View in Altmetric
Web of Science
Times cited: