Back to Search
Start Over
SuMoTED: An intuitive edit distance between rooted unordered uniquely-labelled trees
- Source :
- McVicar, M, 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, vol. 79, pp. 52-59 . https://doi.org/10.1016/j.patrec.2016.04.012, PATTERN RECOGNITION LETTERS
- Publication Year :
- 2016
- Publisher :
- Elsevier BV, 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.
- Subjects :
- Focus (computing)
Technology and Engineering
Theoretical computer science
Tree edit distance
ALGORITHMS
020207 software engineering
02 engineering and technology
Measure (mathematics)
Tree (data structure)
Tree structure
Artificial Intelligence
Signal Processing
0202 electrical engineering, electronic engineering, information engineering
Scalable algorithms
020201 artificial intelligence & image processing
Edit distance
Computer Vision and Pattern Recognition
CONSENSUS
Time complexity
Software
Taxonomies
Mathematics
Subjects
Details
- ISSN :
- 01678655
- Volume :
- 79
- Database :
- OpenAIRE
- Journal :
- Pattern Recognition Letters
- Accession number :
- edsair.doi.dedup.....bf6b7b21d629f9bd234495b0bcf20b88