Research on High-Performance Tree Differencing Algorithms

Metafor is developing a new class of IT system management solutions and as a part of this, wants a method to show differences between multiple deployed instances of an application. To implement this, Metafor requires an accurate, high-performance generalized tree differencing algorithm. Differencing algorithms are used for comparing different versions of a document or snapshots of data to find similarities and differences between them. Tree differencing algorithms perform differencing on hierarchical or tree-structured data. The goal of this project is to do a comprehensive survey and analysis of the recent research literature in the field of tree differencing and to develop an appropriate algorithm that would fit the best for the type of data Metafor is dealing with. In order to determine the appropriate algorithm, the performance of the algorithms will be evaluated based on running time, memory consumption and the optimality of the results.

Faculty Supervisor:

Will Evans

Student:

Partner:

Discipline:

Computer science

Sector:

Information and cultural industries; Professional, scientific and technical services

University:

The University of British Columbia

Program:

Accelerate