Compactly encoding unstructured inputs with differential compression

ABSTRACT

The subject of this article is differential compression, the algorithmic task of finding common strings between versions of data and using them to encode one version compactly by describing it as a set of changes from its companion. A main goal of this work is to present new differencing algorithms that (i) operate at a fine granularity (the atomic unit of change), (ii) make no assumptions about the format or alignment of input data, and (iii) in practice use linear time, use constant space, and give good compression. We present new algorithms, which do not always compress optimally but use considerably less time or space than existing algorithms. One new algorithm runs in O(n) time and O(1) space in the worst case (where each unit of space contains [log n] bits), as compared to algorithms that run in O(n) time and O(n) space or in O(n²) time and O(1) space. We introduce two new techniques for differential compression and apply these to give additional algorithms that improve compression and time performance. We experimentally explore the properties of our algorithms by running them on actual versioned data. Finally, we present theoretical results that limit the compression power of differencing algorithms that are restricted to making only a single pass over the data.

REFERENCES

• 1: Miklós Ajtai, Determinism versus non-determinism for linear time RAMs (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.632-641, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301424]
• 2: Banga, G., Douglis, F., and Rabinovich, M. 1997. Optimistic deltas for WWW latency reduction. In Proceedings of the 1997 USENIX Annual Technical Conference. USENIX Association, Berkeley, Calif., 289--303.
• 3: Randal C. Burns , Darrell D. E. Long, Efficient distributed backup with delta compression, Proceedings of the fifth workshop on I/O in parallel and distributed systems, p.27-36, November 17-17, 1997, San Jose, California, United States [doi>10.1145/266220.266223]
• 4: Randal C. Burns , Darrell D. E. Long, In-place reconstruction of delta compressed files, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.267-275, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277747]
• 5: Chan, M., and Woo, T. 1999. Cache-based compaction: A new technique for optimizing web transfer. In Proceedings of the IEEE Infocom '99 Conference. IEEE Computer Society Press, Los Alamitos, Calif.
• 6: Sudarshan S. Chawathe , Hector Garcia-Molina, Meaningful change detection in structured data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.26-37, May 11-15, 1997, Tucson, Arizona, United States
• 7: de Jong, S. P. 1972. Combining of changes to a source file. IBM Tech. Discl. Bull. 15, 4 (Sept.), 1186--1188.
• 8: Robert G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, Inc., New York, NY, 1968
• 9: Roberto Grossi , Jeffrey Scott Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.397-406, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335351]
• 10: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 11: Hardy, G. H., Littelwood, J. E., and Pólya, G. 1964. Inequalities. Cambridge University Press, London.
• 12: James J. Hunt , Kiem-Phong Vo , Walter F. Tichy, Delta algorithms: an empirical analysis, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.2, p.192-214, April 1998 [doi>10.1145/279310.279321]
• 13: Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
• 14: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 15: Korn, D. G., and Vo, K.-P. 1999. The VCDIFF generic differencing and compression format. Tech. Rep. Internet-Draft draft-vo-vcdiff-00.
• 16: Stefan Kurtz, Reducing the space requirement of suffix trees, Software—Practice & Experience, v.29 n.13, p.1149-1171, Nov. 1999 [doi>10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O]
• 17: MacDonald, J. P. 2000. File system support for delta compression. Masters thesis. Department of Electrical Engineering and Computer Science, University of California at Berkeley, Berkeley, Calif.
• 18: Miller, W., and Myers, E. W. 1985. A file comparison program. Softw. Pract. Exper. 15, 11 (Nov.), 1025--1040.
• 19: Jeffrey C. Mogul , Fred Douglis , Anja Feldmann , Balachander Krishnamurthy, Potential benefits of delta encoding and data compression for HTTP, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.181-194, September 14-18, 1997, Cannes, France
• 20: Christoph Reichenberger, Delta storage for arbitrary non-text files, Proceedings of the 3rd international workshop on Software configuration management, p.144-152, June 12-14, 1991, Trondheim, Norway [doi>10.1145/111062.111081]
• 21: Rochkind, M. J. 1975. The source code control system. IEEE Trans. Softw. Eng. SE-1, 4 (Dec.), 364--370.
• 22: Walter F. Tichy, The string-to-string correction problem with block moves, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.309-321, Nov. 1984 [doi>10.1145/357401.357404]
• 23: Walter F. Tichy, RCS—a system for version control, Software—Practice & Experience, v.15 n.7, p.637-654, July 1985 [doi>10.1002/spe.4380150703]
• 24: Tudor, P. N. 1995. MPEG-2 video compression. Elect. Commun. Eng. J. 7, 6 (Dec.), 257--264.
• 25: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
• 26: Weiner, P. 1973. Linear pattern matching algorithms. In Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory. IEEE Computer Society Press, Los Alamitos, Calif., 1--11.
• 27: Yao, A. C. 1977. Probabilistic computation: towards a unified measure of complexity. In Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 222--227.
• 28: Philip Zimmermann, PGP source code and internals, MIT Press, Cambridge, MA, 1995
• 29: Ziv, J., and Lempel, A. 1977. A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23, 3 (May), 337--343.
• 30: Ziv, J., and Lempel, A. 1978. Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory 24, 5 (Sept.), 530--536.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Version control

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data warehouse and repository
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
Delta compression, differencing, differential compression