SuMoTED

Matt McVicar, Benjamin Sach, Cedric Mesnage, Jefrey Lijffijt, Eirini Spyropoulou, Tijl De Bie. SuMoTED: An intuitive edit distance between rooted unordered fully-labelled trees. Under review. 2015.

This page demonstrates the use of the Subtree Moving Tree Edit Distance (SuMoTED) introduced in this paper. Our goal was to design a tree edit distance which was intuitive, formally defined, and efficiently computable.

Say we wish to compute the distance between this source tree and target tree:

sourceScreen Shot 2015-11-05 at 11.52.37target

We allow for two types of small, intuitive edits on trees. Local upward moves¬†correspond to cutting the edge between a node and its parent, and re-attaching to its grandparent. Local downward moves correspond to cutting an edge between a node and its parent, and re-attaching to one of the node’s siblings. The cost of each operation is equal to the number of descendants of the node being moved. As an example, all possible local moves on the node F in a demo tree can be seen below:

allowable_moves

In (a), a local upward move shifts F and all its descendants to be a child of F’s grandparent, A. In (b) and (c), F is moved locally downwards to be a child of one of it’s siblings.

Given these allowable moves, can you work out the minimum number of moves required to convert the source tree about into the target tree? The total cost associated with the optimal move sequence we call the Subtree Moving Tree Edit Distance (SuMoTED). More details, theoretical results and experiments can be found in this paper [available on acceptance].

An animation of the optimal move sequence for the example above can be seen here.