PaperlayerView exact revision on arXiv

Source-linked AI summary

RTED: A Robust Algorithm for the Tree Edit Distance

Mateusz Pawlik, Nikolaus Augsten

arXiv:1201.0230v1cs.DB

TL;DR

Existing tree edit distance algorithms can have highly variable runtimes across tree shapes, making their selection difficult. The paper introduces RTED and an optimal LRH strategy for GTED, then evaluates RTED against state-of-the-art methods. RTED is designed to be efficient across inputs while retaining optimal worst-case runtime complexity.

  • Problem

    Existing algorithms are either efficient only for some tree shapes or frequently encounter their worst cases, producing unpredictable and sometimes infeasible runtimes.

  • Method

    The paper introduces LRH algorithms, GTED, and RTED, which dynamically computes and applies an optimal LRH decomposition strategy in O(n^2) time and space.

  • Results

    RTED uses O(n^2) space, has optimal O(n^3) worst-case runtime, and computes no more subproblems than any known LRH algorithm for a tree pair.

  • Takeaways & Limitations

    RTED is efficient for any tree shape and empirically outperforms the other approaches, especially when tree shapes vary within a dataset.

  • Takeaways & Limitations

    The heavy-path function ΔI is not optimal because it computes unnecessary subproblems, although it is the only known heavy-path algorithm using O(n^2) space.

Abstract

from arXiv · show

We consider the classical tree edit distance between ordered labeled trees, which is defined as the minimum-cost sequence of node edit operations that transform one tree into another. The state-of-the-art solutions for the tree edit distance are not satisfactory. The main competitors in the field either have optimal worst-case complexity, but the worst case happens frequently, or they are very efficient for some tree shapes, but degenerate for others. This leads to unpredictable and often infeasible runtimes. There is no obvious way to choose between the algorithms. In this paper we present RTED, a robust tree edit distance algorithm. The asymptotic complexity of RTED is smaller or equal to the complexity of the best competitors for any input instance, i.e., RTED is both efficient and worst-case optimal. We introduce the class of LRH (Left-Right-Heavy) algorithms, which includes RTED and the fastest tree edit distance algorithms presented in literature. We prove that RTED outperforms all previously proposed LRH algorithms in terms of runtime complexity. In our experiments on synthetic and real world data we empirically evaluate our solution and compare it to the state-of-the-art.

1. INTRODUCTION

Tree edit distance is useful across applications, but existing algorithms have unpredictable runtimes because performance depends heavily on tree shape. The paper introduces RTED, which dynamically selects an optimal decomposition strategy and is designed to remain efficient across inputs.

  • Motivation: Tree edit distance computes the minimum-cost node-edit sequence transforming one ordered labeled tree into another.Applications include synchronizing file directories, archiving websites, record linkage, data mining, and several scientific domains.
  • Problem: Existing space-efficient algorithms can differ by more than a polynomial degree in runtime, making algorithm choice difficult and sometimes prohibitive.Zhang’s algorithm can be nearly quadratic for some shapes but quartic for others, while Demaine’s cubic worst case occurs frequently.
  • Contribution: An optimal LRH strategy for GTED can be computed in O(n^2) time and space without increasing the overall tree-edit-distance complexity.The strategy computation takes only a small percentage of total runtime.
  • Contribution: RTED computes no more subproblems than any known LRH algorithm for a given tree pair.The paper introduces LRH algorithms and GTED, which implements LRH strategies in O(n^2) space.
  • Evaluation: The paper empirically evaluates RTED against state-of-the-art algorithms and presents this as the first such experimental evaluation of tree edit distance.The evaluation covers synthetic and real-world data in the paper’s stated context.

2. NOTATION AND BACKGROUND

This section defines trees, forests, subforests, paths, and tree edit distance, then describes the recursive dynamic-programming formulation. Space-efficient implementations constrain decomposition choices to reuse storage, producing different algorithmic strategies.

  • 2.1 Notation: A tree is a directed, acyclic, connected graph whose nodes have at most one incoming edge; forests consist of connected tree components.Nodes carry labels and are totally ordered, with postorder traversal visiting nodes in ascending order.
  • 2.1 Notation: A subforest selects nodes and inherited edges from a tree, while a rooted subtree contains a node and all its descendants.A path is a connected subforest in which each node has at most one child.
  • 2.1 Notation: Forest notation includes node removal, subtree removal, and path removal, with F − γ denoting the subtrees attached to a removed path.The empty forest is denoted by ∅, and |F| denotes the number of nodes.
  • 2.2 Tree Edit Distance: Tree edit distance is the minimum cost of deleting, inserting, or renaming nodes to transform one forest into another.Deletion reconnects children to the parent, insertion places a node between a parent and consecutive children, and costs are operation-specific.
  • 2.3 Dynamic Programming Algorithms: The recursive formulation derives each forest distance from three or four smaller subproblems involving leftmost or rightmost roots.The listed subproblems include deleting roots, comparing rooted subtrees, and removing corresponding subtrees.
  • 2.3 Dynamic Programming Algorithms: Dynamic-programming implementations reduce storage from O(|F|^2|G|^2) to O(|F||G|) by bottom-up computation and space reuse.Zhang and Shasha consistently choose one direction, whereas Demaine et al. switch directions using a predefined path.

3. PROBLEM DEFINITION

Path strategies determine how recursive tree edit distance decomposes subtree pairs and therefore how many subproblems are computed. The paper targets an LRH algorithm that combines quadratic space, cubic optimal runtime, and robustness across tree shapes.

  • A strategy chooses the decomposition direction and input-forest order at each recursive step, determining the total number of subproblems.
  • Path strategies use non-overlapping root-to-leaf paths, while LRH strategies restrict choices to left, right, and heavy paths.
  • Previously proposed path algorithms can degenerate to their worst case even when a better path strategy exists, producing runtime differences of a polynomial degree.
  • The paper seeks an LRH algorithm combining worst-case time and space guarantees with robustness against such degeneration.
  • RTED satisfies the stated requirements and computes no more subproblems than any previously proposed LRH algorithm on any instance.

4. A GENERAL ALGORITHM FOR PATH STRATEGIES

The general tree edit distance algorithm GTED applies a supplied path strategy recursively while maintaining a quadratic-space distance matrix. Path-based decompositions select relevant subtrees and subforests, and the strategy controls the resulting runtime.

  • GTED generalizes existing tree edit distance algorithms by taking trees, a path strategy, and a distance matrix as input.
  • 4.1 Relevant Subforests and Subtrees: The full decomposition contains all subforests obtainable by repeatedly removing leftmost or rightmost root nodes.
  • 4.1 Relevant Subforests and Subtrees: Root-leaf paths connect a tree root to a leaf; left, right, and heavy paths follow the leftmost child, rightmost child, or largest-subtree child.
  • 4.1 Relevant Subforests and Subtrees: Recursive path decomposition first produces path-relative subforests, then recursively decomposes the resulting relevant subtrees.
  • GTED recursively processes relevant subtrees and invokes the single-path function matching the selected path type, swapping tree order when the path lies in the second tree.
  • GTED uses quadratic space, while its runtime varies with the strategy from O(|F||G|) to O(|F|^2|G|^2).

5. COST OF PATH STRATEGIES

The paper counts strategy-dependent relevant subproblems and uses those counts to evaluate path decompositions. A recursive cost formula selects an optimal LRH strategy for each pair of trees.

  • Relevant subproblems are pairs of relevant subforests, and their number determines the runtime of recursive tree edit distance algorithms.
  • The analysis derives counts for full, single-path, and recursively partitioned decompositions, including |F(F,γ)| = |F| for any root-leaf path.
  • The cardinalities of full-decomposition subforests and path-relative subforests are independent of the path and computable in linear time by one traversal.
  • Recursive path decomposition counts relevant subforests by summing the sizes of all relevant subtrees in the recursive decomposition.
  • 5.3 Cost of the Optimal Strategy: The optimal LRH strategy is found by exhaustively considering six recursive choices and taking the minimum resulting cost.
  • 5.3 Cost of the Optimal Strategy: Theorem 1 states that the Figure 5 cost formula computes the cost of the optimal LRH strategy for GTED.
  • 5.3 Cost of the Optimal Strategy: The heavy-path function ΔI is not optimal because it computes unnecessary subproblems, but it is the only known heavy-path algorithm using O(n^2) space.

6. RTED: ROBUST TREE EDIT DISTANCE ALGORITHM

RTED computes an optimal LRH decomposition strategy efficiently, then runs GTED with that strategy to obtain robust tree edit distance performance.

  • RTED computes the optimal LRH strategy for two trees and runs GTED with that strategy.
  • 6.2 Efficient Algorithm for Optimal Strategy: The cost formula is evaluated through dynamic programming over subtree pairs, avoiding repeated computation of identical branches.
  • 6.1 Baseline Algorithm for Optimal Strategy: The baseline strategy algorithm has tight O(n3) runtime, making strategy computation too expensive when GTED itself is faster.The optimal GTED strategy can be O(n2 log2 n) for trees of depth log(n).
  • 6.2 Efficient Algorithm for Optimal Strategy: OptStrategy reduces optimal-strategy computation to O(n2) time and space by incrementally maintaining cost sums instead of repeatedly summing relevant subtrees.
  • 6.2 Efficient Algorithm for Optimal Strategy: The algorithm processes every subtree pair in postorder, evaluates six candidate paths, stores the minimum-cost path, and updates parent cost sums.
  • 6.2 Efficient Algorithm for Optimal Strategy: Algorithm 2 is correct, and its time and space complexity are both O(n2).

7. RELATED WORK

Prior tree edit distance work includes exact algorithms, approximations, specialized variants, and lower or upper bounds. RTED extends this landscape with a general framework, formal strategy optimization, and empirical comparison against existing algorithms.

  • Classical exact tree edit distance algorithms range from Tai’s O(m3n3) method to Zhang and Shasha’s O(m2n2) time and O(mn) space algorithm.
  • Demaine’s algorithm is worst-case optimal but can be slower than Zhang’s algorithm on tree shapes such as balanced trees.
  • Dulucq and Touzet compute a decomposition strategy for one tree, whereas RTED decomposes both trees to achieve worst-case optimality with O(mn) space.
  • RTED provides a formal framework generalizing prior approaches and evaluates its performance against Zhang and Shasha, Klein, and Demaine et al.
  • Other work targets restricted tree shapes, approximate distances, specialized matching tasks, or lower and upper bounds rather than the exact unrestricted problem considered here.

8. EXPERIMENTS

The experiments evaluate RTED against competing tree edit distance algorithms on synthetic and real-world datasets. RTED remains efficient across tree shapes, often computing fewer relevant subproblems and achieving more robust runtimes.

  • Experimental setup: The evaluation compares RTED with Zhang-L, Zhang-R, Klein-H, and Demaine-H on synthetic and real-world tree datasets.Synthetic trees cover six shapes, while the real-world datasets include SwissProt, TreeBank, and TreeFam.
  • Relevant subproblems: RTED is the only algorithm that avoids degeneration across all tested synthetic tree shapes.It ties the best competitor on left branch, right branch, full binary, and zigzag trees, while winning alone on random and mixed trees.
  • Relevant subproblems: 2290 times more relevant subproblems are produced by Zhang-R than RTED for left branch trees with 1700 nodes.The experiments use pairs of identical trees with sizes ranging from 20 to 2000 nodes.
  • Runtime: RTED scales well on full binary and mixed synthetic trees, whereas Demaine-H and Zhang-L grow fast on shapes where their strategies are less suitable.On full binary trees, Zhang-L and RTED compute the same number of subproblems, but RTED has a small additional runtime cost.
  • Similarity join: RTED widely outperforms the other algorithms in similarity joins over trees with different shapes.Competitors degenerate for some cross-shape pairs, including Zhang-L and Zhang-R on pairs of unbalanced left- and right-branch trees.
  • Real-world scalability: 84.2% to 94.4% is RTED’s relevant-subproblem ratio relative to the best competitor on TreeFam partitions, versus 5.6% to 30.6% relative to the worst competitor.For the largest trees, RTED produces 18 times fewer relevant subproblems than the worst competitor.

9. CONCLUSION

The conclusion presents RTED within the broader LRH framework and summarizes its theoretical and empirical advantages. RTED uses quadratic space, has worst-case optimal cubic runtime, and remains efficient across tree shapes.

  • Contributions: The LRH strategy class generalizes previous approaches and includes the best tree edit distance algorithms.RTED is obtained by computing an optimal LRH strategy for the general GTED algorithm.
  • Theoretical guarantees: RTED runs in O(n^2) space and has O(n^3) worst-case runtime, which is worst-case optimal.These bounds match the stated space efficiency and worst-case optimality goals.
  • Robustness: RTED computes no more subproblems than its best competitor for any input instance.The conclusion reports this property as the basis for RTED’s efficiency across tree shapes.
  • Empirical findings: Empirical evaluation shows that RTED is efficient for any input and especially outperforms other approaches when dataset tree shapes vary.The conclusion summarizes results from the paper’s experiments on synthetic and real-world data.
Loading 1201.0230v1…