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

Date

2004

Author

Otlu, Süleyman Onur

Metadata

Show full item record

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.

Subject Keywords

Computer software.

URI

http://etd.lib.metu.edu.tr/upload/12604951/index.pdf
https://hdl.handle.net/11511/14178

Collections

Graduate School of Natural and Applied Sciences, Theses