1993 · 18 citations · 11 references
ComputingComputer ScienceHigh-performance ComputingData StructuresDatabasesParallel ComputingData CompressionData ParallelismLossy Data CompressionQuery ProcessingText EncodingText RepresentationCompressionCompression AlgorithmsCompression TechniquesIndex CompressionIndexesIndexingInverted IndexesRun-length Encoding
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.
11
Arithmetic coding for data compression
Ian H. Witten, Radford M. Neal, John G. Cleary · Communications of the ACM · 1987 · 2.9K citations · Full text
Solomon W. Golomb · IEEE Transactions on Information Theory · 1966 · 679 citations
Parameterised compression for sparse bitmaps
Alistair Moffat, Justin Zobel · 1992 · 63 citations