Macquarie University
01whole.pdf (7.3 MB)

Bounded tree edit distance algorithms on dynamic graphs

Download (7.3 MB)
posted on 2023-11-16, 03:04 authored by Jonathan Elijah Scott Stacey

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. 


Table of Contents

1. Introduction -- 2. Background -- 3. TED on Dynamic Trees -- 4. Experimental Results -- 5. Conclusion

Awarding Institution

Macquarie University

Degree Type

Thesis MRes


Master of Research

Department, Centre or School

School of Computing

Year of Award


Principal Supervisor

Bernard Mans

Additional Supervisor 1

Luke Mathieson


Copyright: The Author Copyright disclaimer:




29 pages

Former Identifiers

AMIS ID: 258528

Usage metrics

    Macquarie University Theses