Macquarie University
Browse

Bounded tree edit distance algorithms on dynamic graphs

Download (7.3 MB)
thesis
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. 

History

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

Degree

Master of Research

Department, Centre or School

School of Computing

Year of Award

2023

Principal Supervisor

Bernard Mans

Additional Supervisor 1

Luke Mathieson

Rights

Copyright: The Author Copyright disclaimer: https://www.mq.edu.au/copyright-disclaimer

Language

English

Extent

29 pages

Former Identifiers

AMIS ID: 258528

Usage metrics

    Macquarie University Theses

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC