Literature Review

Goal: Review papers that look at tree diffing for ordered trees.

Overviews

Linear diffs: https://bryanpendleton.blogspot.com/2010/04/more-study-of-diff-walter-tichys-papers.html

A survey on tree edit distance and related problems (2005) Philip Bille

https://doi.org/10.1016/j.tcs.2004.12.030

Papers

Approximate Tree Pattern Matching (1995) Dennis Shasha, Kaizhong Zhang

https://nyuscholars.nyu.edu/en/publications/approximate-tree-pattern-matching

Meaningful change detection in structured data (1997) Chawathe

https://doi.org/10.1145/253260.253266

An improved algorithm for tree edit distance with applications for RNA secondary structure comparison (2014)

https://doi.org/10.1007/s10878-012-9552-1

Has some summaries of other techniques at the end of section 2.

Faster Algorithms for Bounded Tree Edit Distance (2021)

https://arxiv.org/pdf/2105.02428.pdf