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

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2004

Öğrenci: SÜLEYMAN ONUR OTLU

Danışman: ADNAN YAZICI

Özet:

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.