Cluster based Mixed Coding Schemes for Inverted File Index Compression
Jinlin Chen, Ping Zhong, Terry Cook
Journal of Digital Information Management, Vol. 6, No. 1, 2008.
DOI: 
Link: http://www.dirf.org/jdim/v6n1a4.asp
Abstract:
The cluster property of document collections in todayâ€™s search engines provides valuable information for index compression. By clustering d-gaps of an inverted list based on a threshold, and then encoding clustered and non-clustered d-gaps using different methods, we can tailor to the specific properties of different d-gaps and achieve better compression ratio. Based on this idea, in this paper we propose a cluster based approach and presents two new codes for inverted file index compression: mixed gamma/flat binary code and mixed delta/flat binary code. Experiment results show that the two new codes achieve better or equal performance in terms of compression ratio comparing to interpolative code which is considered as the most efficient bitwise code at present. Besides, the two new codes have much lower complexity comparing to interpolative code and therefore enable faster encoding and decoding. By adjusting the parameters for the mixed codes, even better results may be achieved. Experiments show promising results with our approaches.