Bounded tree edit distance algorithms on dynamic graphs

Finding the edit distance between two similar rooted ordered trees is a well-studied problem, as hierarchical data is often modelled as trees. Existing algorithms for this problem often use Dynamic Programming (DP) to improve efficiency. Dynamic graphs are graphs that change with time, captured by dynamic graph models, which enable dynamic graph algorithms to solve problems faster than would be possible on non-dynamic graphs. Both dynamic graph algorithms and DP seek to reuse previous work, and can operate in tandem: DP memoizes subproblem results, in turn providing a basis for reuse by algorithms on dynamic graphs for related graph (or tree) states. 

We describe a way of reusing DP-subproblems between algorithm executions when finding the distance between similar pairs of similar trees, using a well-grounded model of dynamic trees similar to snapshot, event, and streaming dynamic graph models, as well as to widely adopted version control software. Our technique needs only a constant factor more memory than the best existing algorithms, and it substantially improves performance in empirical testing. This approach should also allow for new variations of bounded algorithms for edit distance on trees, and may generalize to algorithms using DP for distance-based problems on other dynamic data structures.