Compression of indexes with full positional information in very large text databases

ABSTRACT

This paper describes a combination of compression methods which may be used to reduce the size of inverted indexes for very large text databases. These methods are Prefix Omission, Run-Length Encoding, and a novel family of numeric representations called n-s coding. Using these compression methods on two different text sources (the King James Version of the Bible and a sample of Wall Street Journal Stories), the compressed index occupies less than 40% of the size of the original text, even when both stopwords and numbers are included in the index. The decreased time required for I/O can almost fully compensate for the time needed to uncompress the postings. This research is part of an effort to handle very large text databases on the CM-5, a massively parallel MIMD supercomputer.

REFERENCES

• 1: IJsbrand Jan Aalbersberg, Posting compression in dynamic retrieval environments, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.72-81, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122868]
• 2: Bookstein, A., S.T. Klein, and T. Raita. "Compression Concordances Subject to Clustering." Proceedings: Data Compression Conference (Snowbird, Utah), April 1993, to appear.
• 3: Abraham Bookstein , Shmuel T. Klein , D. A. Ziff, A systematic approach to compressing a full-text retrieval system, Information Processing and Management: an International Journal, v.28 n.6, p.795-806, Nov.–Dec. 1992 [doi>10.1016/0306-4573(92)90069-C]
• 4: Y. Choueka , A. S. Fraenkel , S. T. Klein, Compression of concordances in full-text retrieval systems, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.597-612, May 1988, Grenoble, France [doi>10.1145/62437.62500]
• 5: Elias, P. "Universal Code-Word Sets and Representations of the Integers." IEEE Transactions on Information Theory, p. 194-203, March 1975.
• 6: Goulomb, Solomon. "Run-length Encodings." IEEE Transactions on Information Theory, 12(3):399-401, July 1966.
• 7: Harmon, Donna. "How Effective is Suffixing?" Journal of the American Society for Information Science, 42(1):7-15, January 1991.
• 8: Haskin, Roger. "Special Purpose Processors for Text Retrieval." Database Engineering, 4(1): 16-29.
• 9: Huffman, David. "A Method for the Construction of Minimum-Redundancy Codes." Proceedings of the IRE, 40(9):1098-1101, September 1932.
• 10: Shmuel T. Klein , Abraham Bookstein , Scott Deerwester, Storing text retrieval systems on CD-ROM: compression and encryption considerations, ACM Transactions on Information Systems (TOIS), v.7 n.3, p.230-245, July 1989 [doi>10.1145/65943.65946]
• 11: Moffat, Alistair and Justin Zobel. "Coding for Compression in Full-Text Retrieval Systems." Proceedings IEEE Data Compression Conference (Snowbird, Utah), March 1992, pp. 23-32.
• 12: Alistair Moffat , Justin Zobel, Parameterised compression for sparse bitmaps, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.274-285, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133210]
• 13: Van Rijsbergen, C.J. Chapter 2, "Automated Text Analysis" in information Retrieval, 2nd edition. Butterworth & Co., London, U.K., 1979, pp. 14-35.
• 14: Witten, Ian, Timothy Bell, and Craig Nevill. "Models for Compression in Full-Text Retrieval Systems." Proceedings: Data Compression Conference(Snowbird, Utah), April 1991, pp. 23-32.
• 15: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data dictionary/directory
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Documentation, Languages