Improved hierarchical bit-vector compression in document retrieval systems

ABSTRACT

The “concordance” of an information retrieval system can often be stored in form of bit-maps, which are usually very sparse and should be compressed. Hierarchical bit-vector compression consists of partitioning a vector vi into equi-sized blocks, constructing a new bit-vector vi+1 which points to the non-zero blocks in vi, dropping the zero-blocks of vi, and repeating the process for vi+1. We refine the method by pruning some of the tree branches if they ultimately point to very few documents; these document numbers are then added to an appended list which is compressed by the prefix-omission technique. The new method was thoroughly tested on the bit-maps of the Responsa Retrieval Project, and gave a relative improvement of about 40% over the conventional hierarchical compression method.

REFERENCES

• 1: Choueka Y., Full text systems and Research in the Humanities, Computer8 and the Humanities X_IV (1980) 153-169.
• 2: D. R. Davis , A. D. Lin, Secondary key retrieval using an IBM 7090-1301 system, Communications of the ACM, v.8 n.4, p.243-246, April 1965 [doi>10.1145/363831.364908]
• 3: Fraenkel A.S., All about the Responsa Retrieval Project you always wanted to know but were afraid to ask, Expanded Summary, Jurimetric8 J. 16 (1976) 149- 156.
• 4: Fraenkel A.S., Klein S.T., Novel Compression of sparse Bit-Strings-- Preliminaxy Report, Combinatorial Algorithnts on Wo#ds, NATO ASI Series Vol F12, Springer Verlag, Berlin (1985) 169-183.
• 5: Jakobsson M., Huffman coding in Bit- Vector Compression, Inf. Proc. Letters T (1978) 304-307.
• 6: J akobsson M., Evaluation of s Hierarchical Bit-Vector Compression Technique, Inf. Proc. Letters 14 (1982) 147-149.
• 7: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 8: Nevalainen O., Jakobsson M., Berg R., Compression of clustered inverted files, in Proc. of the 7-th Syrup. on Math. Foundations of Comp. Sc., Zakopane, Poland (1978) 393-402.
• 9: Schuegraf E.J., Compression of large in-. verted files with hyperbolic term distribution, Inf. Proc. and Management 12 (1976) 377-384.
• 10: Teuhola 3., A Compression method for Clustered Bit-Vectors, inf. Proc. Letter8 7 (1978) 308-311.
• 11: Oscar Vallarino, On the use of bit maps for multiple key retrieval, ACM SIGMOD Record, v.8 n.2, p.108-114, March 1976
• 12: Wedekind H., H#rder T., Datenbank- 8#teme II, B.-I. Wissenschaftsverlag, Mannheim (1976).