In-Place Reconstruction of Version Differences

Appeared in IEEE Transactions on Knowledge and Data Engineering .

Abstract

In-place reconstruction of differenced data allows information on devices with limited storage capacity to be updated efficiently over low-bandwidth channels. Differencing encodes a version of data compactly as a set of changes from a previous version. Transmitting updates to data as a version difference saves both time and bandwidth. In-place reconstruction rebuilds the new version of the data in the storage or memory the current version occupies–no scratch space is needed for a second version. By combining these technologies, we support highly mobile applications on space-constrained hardware. We present an algorithm that modifies a differentially encoded version to be in-place reconstructible. The algorithm trades a small amount of compression to achieve this property. Our treament includes experimental results that show our implementation to be efficient in space and time and verify that compression losses are small. Also, we give results on the computational complexity of performing this modification while minimizing lost compression.

Publication date:
July 2003

Authors:
Randal Burns
Larry Stockmeyer
Darrell D. E. Long

Projects:
Reliable Storage

Available media

Full paper text: PDF

Bibtex entry

@article{TKDE-Burns-2003,
  author       = {Randal Burns and Larry Stockmeyer and Darrell D. E. Long},
  title        = {In-Place Reconstruction of Version Differences},
  journal      = {IEEE Transactions on Knowledge and Data Engineering},
  volume       = {},
  month        = jul,
  year         = {2003},
}