A survey on tree edit distance and related problems
Theoretical Computer SciencePublished 10 February 2005
Philip Bille
Citations753
SJR quartileQ2
SJR score0.49
SNIP0.94
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work surveys the problem of comparing labeled trees based on simple local operations of deleting, inserting, and relabeling nodes and presents one or more of the central algorithms for solving the problem.
Abstract
We survey the problem of comparing labeled trees based on simple local operations of deleting, inserting, and relabeling nodes. These operations lead to the tree edit distance, alignment distance, and inclusion problem. For each problem we review the results available and present, in detail, one or more of the central algorithms for solving the problem.
Keywords
Computer Science
Journal of the Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
Algorithms on strings, trees, and sequences: computer science and computational biology
3,529 Citations1997Dan Gusfield
Journal of the ACMThe String-to-String Correction Problem
3,063 Citations1974Robert A. Wagner, Michael J. Fischer
An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.
Cambridge University Press eBooksAlgorithms on Strings, Trees and Sequences
3,045 Citations1997Dan Gusfield
Ukkonen’s method is the method of choice for most problems requiring the construction of a suffix tree, and it will be presented first because it is easier to understand.
Storing and querying ordered XML using a relational database system
2,248 Citations2002Igor Tatarinov, Stratis D. Viglas +4 more
This paper shows that XML's ordered data model can indeed be efficiently supported by a relational database system, and proposes three order encoding methods that can be used to represent XML order in the relational data model, and also proposes algorithms for translating ordered XPath expressions into SQL using these encoding methods.
Algorithms on strings, trees, and sequences
1,723 Citations1997Dan Gusfield
SIAM Journal on ComputingSimple Fast Algorithms for the Editing Distance between Trees and Related Problems
1,275 Citations1989Kaizhong Zhang, Dennis Shasha
Algorithms are designed to answer the following kinds of questions about trees: what is the distance between two trees, and the analogous question for prunings as for subtrees.
SIAM Journal on ComputingFast Algorithms for Finding Nearest Common Ancestors
1,066 Citations1984Dov Harel, Robert E. Tarjan
An algorithm for a random access machine with uniform cost measure (and a bound of $\Omega (\log n)$ on the number of bits per word) that requires time per query and preprocessing time is presented, assuming that the collection of trees is static.
Journal of the ACMThe Tree-to-Tree Correction Problem
856 Citations1979Kuo‐Chung Tai
An algorithm is presented which solves the problem of determining the distance from T to T' as measured by the mlmmum cost sequence of edit operaUons needed to transform T into T'.
Proof verification and hardness of approximation problems
741 Citations1992Sanjeev Arora, Carsten Lund +3 more
Change detection in hierarchically structured information
488 Citations1996Sudarshan S. Chawathe, Anand Rajaraman +2 more
This work defines the hierarchical change detection problem as the problem of finding a "minimum-cost edit script" that transforms one data tree to another, and presents efficient algorithms for computing such an edit script.
Journal of the ACMPattern Matching in Trees
440 Citations1982Christoph M. Hoffmann, Michael J. O’Donnell
Five new techniques for tree pattern matching are presented, analyzed for time and space complexity, and compared with previously known methods.
Information Processing LettersThe tree-to-tree editing problem
412 Citations1977Stanley M. Selkow
It is shown that a straightforward generalization of the Sankoff algorithm will provide a solution to the tree-to-tree editing problem and it follows that the algorithm must be optimal over a wide class of computation models.
Journal of AlgorithmsFinding approximate patterns in strings
384 Citations1985Esko Ukkonen
An algorithm is presented to construct a deterministic finite-state automaton that solves the problem of locating in any string a substring whose edit distance from p is at most a given constant t.
Journal of AlgorithmsFast parallel and serial approximate string matching
333 Citations1989Gad M. Landau, Uzi Vishkin
Given a text of lenght n, a pattern of length m and an integer k, this work presents parallel and serial algorthms for finding all occurrences of the pattern in the text with at most k differences.
Information Processing LettersOn the editing distance between unordered labeled trees
317 Citations1992Kaizhong Zhang, Rick Statman +1 more
This paper gives efficient polynomial-time algorithms for the case when one tree is a string or has a bounded number of leaves and shows that the problem is NP-complete even for binary trees having a label alphabet of size two.
Meaningful change detection in structured data
285 Citations1997Sudarshan S. Chawathe, Héctor García-Molina
This paper presents a heuristic change detection algorithm that yields close to “minimal” descriptions of the changes, and that has fewer restrictions than previous algorithms.
Journal of the ACMBounds on the Complexity of the Longest Common Subsequence Problem
248 Citations1976Jeffrey D. Ullman, Alfred V. Aho +1 more
It is shown that unless a bound on the total number of distinct symbols is assumed, every solution to the problem can consume an amount of time that is proportional to the product of the lengths of the two strings.
Lecture notes in computer scienceComputing the Edit-Distance Between Unrooted Ordered Trees
244 Citations1998Philip N. Klein
This work gives an O(n3 log n) algorithm to compute the edit distance between two ordered trees, a tree in which each node's incident edges are cyclically ordered.
Theoretical Computer ScienceAlignment of trees — an alternative to tree edit
242 Citations1995Tao Jiang
SIAM Journal on ComputingOrdered and Unordered Tree Inclusion
201 Citations1995Pekka Kilpeläinen, Heikki Mannila
AlgorithmicaA constrained edit distance between unordered labeled trees
189 Citations1996Kaizhong Zhang
This paper considers the problem of computing a constrained edit distance between unordered labeled trees and presents dynamic programming algorithms solving these problems in sequential timeO(|T1|×|T2|×(deg (T1)+deg(T2)× log2(deg( t2));)
Discrete MathematicsOn the complexity of finding iso- and other morphisms for partial k-trees
170 Citations1992Jiřı́ Matoušek, Robin Thomas
The complexity of these problems when G is restricted to be a partial k -tree is discussed, and a polynomial time algorithm is given for the n disjoint connecting paths problem restricted topartial k -trees (with n part of input).
Helda (University of Helsinki)Tree Matching Problems with Applications to Structured Text Databases
152 Citations1992Pekka Kilpeläinen
Information Processing LettersSome MAX SNP-hard results concerning unordered labeled trees
141 Citations1994Kaizhong Zhang, Tao Jiang
Given two rooted, labeled, and unordered trees, it is shown that both problems are MAX SNP-hard, which means that neither problem has a polynomial time approximation scheme (PTAS) unless P = NP.
IEEE Transactions on Knowledge and Data EngineeringA system for approximate tree matching
140 Citations1994J. Tsong-Li Wang, Kaizhong Zhang +2 more
This paper presents a system, called approximate-tree-by-example (ATBE), which allows inexact matching of trees, and describes the architecture of ATBE, its use and describes some aspects ofATBE implementation.
Theoretical Computer ScienceAlignment of trees — an alternative to tree edit
130 Citations1995Tao Jiang, Lusheng Wang +1 more
This paper proposes the alignment of trees as a measure of the similarity between two labeled trees and shows that the alignment problem can be solved in polynomial time if the trees have a bounded degree and becomes NP-hard if one of the trees is allowed to have an arbitrary degree.
Efficient tree pattern matching
122 Citations1989S. Rao Kosaraju
An O(nM/sup 0.75/ polylog(m))-step algorithm for tree pattern matching problem is designed and the problems of linear string matching with don't care symbols and linear string max-min convolution are treated.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Tree-to-Tree Distance and Its Application to Cluster Analysis
121 Citations1979Shin-Yee Lu
An algorithm that generates the distance for any two trees is presented and cluster analysis for patterns represented by tree structures is discussed, using a tree-to-tree distance to measure the similarity between patterns.
Pattern RecognitionAlgorithms for the constrained editing distance between ordered labeled trees and related problems
106 Citations1995Kaizhong Zhang
The problem of computing a constrained editing distance between ordered labeled trees, which can be applied to pattern recognition, syntactic tree comparison, classification tree comparison and other applications, is considered.
Journal of AlgorithmsNew Algorithm for Ordered Tree-to-Tree Correction Problem
90 Citations2001Weimin Chen
The ordered tree-to-tree correction problem is to compute the minimum edit cost of transforming one ordered tree to another one, and a new algorithm is presented for this problem, which is asymptotically faster for certain kind of trees.
Journal of AlgorithmsApproximate Tree Matching in the Presence of Variable Length Don′t Cares
87 Citations1994Kewen Zhang, Dennis Shasha +1 more
This paper presents algorithms for three problems having to do with approximate matching for such trees with variable length don′t cares (VLDCs) with time complexity O(|P| × |D| × min(depth(P, leaves(P)) × min (depth(D), leaves(D)))
A tree-edit-distance algorithm for comparing simple, closed shapes
83 Citations2000Philip N. Klein, Srikanta Tirthapura +2 more
This paper defines the version of tree edit-distance (it differs from that previously described in the literature), and gives a polynomial-time algorithm to compute the distance between two trees.
Theoretical Computer ScienceOn the approximation of largest common subtrees and largest common point sets
64 Citations2000Tatsuya Akutsu, Magnús M. Halldórsson
It is shown that approximating the problems within a factor of ne is NP-complete, while a general search algorithm which approximates both problems withina factor of O(n/log n) is presented.
AlgorithmicaFinding Largest Subtrees and Smallest Supertrees
58 Citations1998Ajay Gupta, Nobuya Nishimura
This paper presents a general paradigm for sequential and parallel subtree and supertree algorithms for subgraph isomorphism and topological embedding, and presents algorithms for determining a largest tree embeddable in two trees T and T' and a smallest tree in which each of T andT' can be embedded.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAuthors'Reply
57 Citations1984Allen R. Hanson, Edward M. Riseman +1 more
The proposed tree distance is a more appropriate measurement of structural defonnation than the tree distance measure in terms of the number of insertions, deletions, and substitutions of tree nodes, as defined in previous studies.
Journal of the ACMNonlinear pattern matching in trees
53 Citations1992R. Ramesh, I. V. Ramakrishnan
This paper presents new sequential algorithms for nonlinear pattern matching in trees that improves upon know tree pattern matching algorithms in important aspects such as time performance, ease of integration with several reduction strategies and ability to avoid unnecessary computation steps on match attempts that fail.
International Journal of Pattern Recognition and Artificial IntelligenceTHE TREE-TO-TREE EDITING PROBLEM
50 Citations1988Eiichi Tanaka, KEIKO TANAKA
This paper describes the computing alogrithms for the tree distance that can be applied to any problems including pattern recognition, syntactic tree comparison and classification, and tree comparison whose structures are important in structure preserving mapping.
ATreeGrep: approximate searching in unordered trees
49 Citations2003Dennis Shasha, J.T.L. Wang +2 more
This paper presents an approach to the nearest neighbor search problem for unordered labeled trees, a tree in which each node has a string label and the parent-child relationship is significant, but the order among siblings is unimportant.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Tree-Matching Algorithm Based on Node Splitting and Merging
45 Citations1984S. Y. Lu
Symposium on Discrete AlgorithmsFast comparison of evolutionary trees
45 Citations1994Martı́n Farach-Colton, Mikkel Thorup
Faster tree pattern matching
42 Citations2002Moshe Dubiner, Zvi Galil +1 more
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Indexing based on edit-distance matching of shape graphs</title>
40 Citations1998Srikanta Tirthapura, Daniel Sharvit +2 more
This paper introduces a new metric for comparing shock graphs, a symmetry- based representation of shape, for indexing into pictorial databases using shock graphs.
Lecture notes in computer scienceA Fast Algorithm for Optimal Alignment between Similar Ordered Trees
40 Citations2001Jesper Jansson, Andrzej Lingas
A fast algorithm for optimal alignment between two similar ordered trees with node labels, let S and T be two such trees with |S| and |T| nodes, respectively.
Journal of AlgorithmsMore Efficient Algorithm for Ordered Tree Inclusion
37 Citations1998Weimin Chen
This paper improves the previous best algorithms for ordered tree inclusion by means of a sophisticated bottom-up-matching strategy and presents an O(|leaves(S)||T|) time andO(|S|min(depth(T),|le Leaves(T)|)) space algorithm.
Maximum agreement subtree in a set of evolutionary trees-metrics and efficient algorithms
35 Citations2002Dmitry Keselman, Amihood Amir
It is proved that the maximum homeomorphic agreement subtree problem is /spl Nscr//spl Pscr/-complete for three trees with unbounded degrees and an approximation algorithm of time O(kn/sup 5/) for choosing the species that are not in a maximum agreement subtrees of a set of k trees is shown.
Lecture notes on approximation algorithms: Volume I
32 Citations1993Rajeev Motwani
These lecture notes are based on the course CS351 (Dept. of Computer Science, Stanford University) offered during the academic year 1991-92 and are being revised to incorporate the implications of recent results in approximation algorithms and the complexity of approximation problems.
Lecture notes in computer scienceA New Measure of Edit Distance between Labeled Trees
31 Citations2001Chin Lung Lu, Zheng-Yao Su +1 more
A new measure of the edit distance between two rooted labeled trees is defined, called less-constrained edit distance, by relaxing the restriction of constrained edit mapping, and it is shown that this problem is NP-complete and even has no absolute approximation algorithm unless P = NP, which implies that it is impossible to have a PTAS for the problem.
Lecture notes in computer scienceA new algorithm for the ordered tree inclusion problem
26 Citations1997Thorsten Richter
A new algorithm for the ordered tree inclusion problem with time complexity O(∣Σ p ∣ · ∣T∣ +#matches · DEPTH(T)), where Σ p is the alphabet of the labels of the pattern tree and #matches is the number of pairs (v, w).
Lecture notes in computer scienceOn the tree inclusion problem
20 Citations1993Laurent Alonso, René Schott
A New Measure of the Distance between Ordered Trees and its Applications
19 Citations1997Thorsten Richter
This paper presents a new measure of the distance between two ordered trees T 1 and T 2 that is based on a restricted kind of mapping which is called structure respecting and presents a simple dynamic programming algorithm that computes a minimum cost structure respecting mapping.
Approximation Algorithms for the Largest Common Subtree Problem.
16 Citations1995Sanjeev Khanna, Rajeev Motwani +1 more
The largest common subtree problem is to find a largest subtree which occurs as a common subgraph in a given collection of trees and an algorithm is given with approximation ratio O(( n*(loglog n) / log^{2} n) when the trees are unlabeled).
Molecular Biology ReportsThe editing distance between trees: algorithms and applications
15 Citations1989Dennis Shasha, Kaizhong Zhang
It is confirmed that age, smoking and alcohol consumption are risk factors for this disease and the polymorphisms investigated have no association with the development of head and neck cancer.
International Journal of Foundations of Computer ScienceFINDING SMALLEST SUPERTREES UNDER MINOR CONTAINMENT
13 Citations2000Naomi Nishimura, Prabhakar Ragde +1 more
Lecture notes in computer scienceOn the approximation of largest common subtrees and largest common point sets
13 Citations1994Tatsuya Akutsu, Magnús M. Halldórsson
Lecture notes in computer scienceEfficient parallel algorithms for tree editing problems
13 Citations1996Kaizhong Zhang
A framework for solving tree editing problems in parallel by performing a series of weighted edit operations on T1 with overall minimum cost is presented and polylogrithmic time algorithms under this framework are shown.
International Journal of Pattern Recognition and Artificial IntelligenceA NOTE ON A TREE-TO-TREE EDITING PROBLEM
2 Citations1995Eiichi Tanaka
The corrected definition of a structure preserving mapping between rooted and ordered trees and a computing method of the tree distance based on the mapping are described.