A new technique: Replace algorithm to retrieve a version from a repository instead of delta application


Thesis Type: Postgraduate

Institution Of The Thesis: Orta Doğu Teknik Üniversitesi, Faculty of Engineering, Department of Computer Engineering, Turkey

Approval Date: 2004

Student: SÜLEYMAN ONUR OTLU

Consultant: ADNAN YAZICI

Abstract:

The thesis introduces a new technique that is an alternative method instead of applying deltas to literal file sequentially to retrieve a version from a repository. To my best knowledge; this is the first investigation about delta combination for copy/insert instruction type with many experimental results and conclusions. The thesis proves that the delta combination eliminates unnecessary I/O process for intermediate versions when delta application is considered, therefore reduces I/O time. Deltas are applied to literal sequentially to generate the required version in the classical way. Replace algorithm combines delta files which would be applied in delta application as combined delta, and applies it to literal to generate the required one. Apply runs in O (size (D)) time where D is the destination file and size (D) is its size. To retrieve nth version in a chain where 1st version is literal, it requires n-1 time apply. Replace algorithm runs in O (i + c * log2 n) time where i is the total length of all inserts, c is the total length of all copies in destination delta, and n is the number of instructions in source delta. To retrieve the same nth version, it requires n-2 time replace and one apply.