A survey on tree edit distance and related problems

By Philip Bille. Theoretical Computer Science, 2005

864 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/531c174de0474a8309a9b3be36b3ec04b011e0ab

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

Citations in the corpus

A Survey on Metric Learning for Feature Vectors and Structured Data (2013, background): “Edit distance has attracted most of the interest in the context of metric learning for structured data because (i) it is defined for a variety of objects: sequences (Levenshtein, 1966), trees (Bille, 2005) and graphs (Gao et al.”
Efficient Search for Transformation-based Inference (2012, neutral): “Textual inference systems limited to the standard tree-edit operations (insertion, deletion, substitution) can use an exact algorithm that ﬁnds the optimal solution in polynomial time under certain constraints (Bille, 2005).”
A survey of graph edit distance (2010, methodology): “The similarity of labeled trees is compared in [61] by various methods, in which deﬁnitions of cost functions are given ahead.”
Measuring Compositionality in Representation Learning (2019, background): “As the derivations considered in this paper are all tree-structured, it is natural to use a simple tree edit distance (Bille, 2005) for this purpose.”
Fine-grained and accurate source code differencing (2014, background): “The tree differencing problem has been largely investigated when considering only the add node, delete node and update node actions [4].”
Answer Extraction as Sequence Tagging with Tree Edit Distance (2013, methodology): “Following Bille (2005), we deﬁne an edit script be-tween trees T 1 , T 2 as the edit sequence transforming T 1 to T 2 according to a cost function , with the total summed cost known as the tree edit distance .”
Supervised classification and mathematical optimization (2013, background): “Computing in these cases a dissimilarity δ for a given pair of objects may lead to hard combinatorial optimization problems, [27].”
Retrieval-based Neural Source Code Summarization (2020, methodology): “In our work, since the training set is very large and the unsupervised method is preferred, we efficiently measure the syntactic similarities of code snippets based on the token sequences of ASTs without training.”
Tree Edit Models for Recognizing Textual Entailments, Paraphrases, and Answers to Questions (2010, neutral): “See Bille (2005) for a review.”