Data compression on a database system

ABSTRACT

A general-purpose data-compression routine—implemented on the IMS database system—makes use of context to achieve better compression than Huffman's method applied character by character. It demonstrates that a wide variety of data can be compressed effectively using a single, fixed compression routine with almost no working storage.

REFERENCES

• 1: Gordon V. Cormack , R Nigel Horspool, Algorithms for adaptive Huffman codes, Information Processing Letters, v.18 n.3, p.159-165, March 1984 [doi>10.1016/0020-0190(84)90021-8]
• 2: Huffman, D. A method for the construction of minimumredundancy codes. Proc. 1.R.E. 40. 9 (Sept. 1952). 1098-1101. This original paper on Huffman's compression method contains a proof that the method is optimal.
• 3: IBM. Information management system: Programming reference manual. 9th ed. SHZO-9027-8. IBM. 1981. pp. 3.3-3.38. Describes the IMS system from the system programmer's point of view. including the implementation and use of the data-compression exit facility: Contains a sample compression routine that implements run-length encoding.
• 4: Reghbati, H. An overview of data compression techniques. Compufer 14.4 (May 1981). 71-75. Surveys briefly a number of cnmmnn datacompression methods.
• 5: Schuegraf, E.J. A survey of data compression methods for nonnumeric records. Can. 1. In/. Sci. 2, I {May 1977), 93-105. Provides an abstract overview of the information theory behind data compressiop, and a presentation of several classes of compression methods.
• 6: Severance, D. A practitioner's guide to data base compression. If. Syst. 8, 1 (1983). 51-62. Covers in detail a large number of datacompression methods that may be applicable to database systems: Includes a comprehensive list of ao references to the literature.
• 7: Ziv. J,, and Lempel, A. A universal algorithm for sequential data compression. IEEE Trans. tnf Theory 23,3 (May 1977), 337-343. Describes an adaptive coding scheme that encodes progressively longer input strings as integers.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Management, Performance