Efficient computation of the tree edit distance

DOI10.1145/2699485MaRDI QIDQ5012520zbMATH OpenOpenAlexFDO

Authors Mateusz Pawlik, Nikolaus Augsten

Publication date 25 November 2021

Published in ACM Transactions on Database Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.0230

zbMATH Keywords

approximate matchingsimilarity searchtree edit distance

Mathematics Subject Classification ID

Trees (05C05) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: 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.

Recommendations

• An Optimal Decomposition Algorithm for Tree Edit Distance
• An optimal decomposition algorithm for tree edit distance
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Fast algorithms for the unit cost editing distance between trees
• Analysis of tree edit distance algorithms

Cited in

(17)

• An improved algorithm for tree edit distance with applications for RNA secondary structure comparison
• Covering tree with stars
• Efficient exponential-time algorithms for edit distance between unordered trees
• Decomposition algorithms for the tree edit distance problem
• Algebraic dynamic programming on trees
• An optimal decomposition algorithm for tree edit distance
• A metric normalization of tree edit distance
• Analysis of tree edit distance algorithms
• scientific article; zbMATH DE number 1844616 (Why is no real title available?)
• Edit distance between unrooted trees in cubic time
• A rearrangement distance for fully-labelled trees
• A multi-labeled tree edit distance for comparing ``Clonal trees of tumor progression
• An Optimal Decomposition Algorithm for Tree Edit Distance
• On the hardness of computing the edit distance of shallow trees
• A gaze into the internal logic of graph neural networks, with logic
• Learning probabilistic models of tree edit distance
• Faster algorithms for guided tree edit distance

Describes a project that uses

Uses Software

• TED

This page was built for publication: Efficient computation of the tree edit distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5012520)