Research on High-Performance Tree Differencing Algorithms

Metafor is developing a new class of IT system management solutions and as a part of this, Metafor wants a method to show differences between multiple deployed instances of an application. To implement this, Metafor requires an accurate and 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. And tree differencing algorithms perform differencing on hierarchical or treestructured data. Therefore, 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. Test environments will be designed and algorithms will be implemented correctly so that we can fully evaluate them.

Faculty Supervisor:

Dr. Williams Evans

Student:

Nima Hazar

Partner:

Metafor Software

Discipline:

Computer science

Sector:

Information and communications technologies

University:

University of British Columbia