Fast dictionary-based compression for inverted indexes

Pibiri G. E., Petri M., Moffat A.

Compression  Efficiency  Decoding  Inverted index 

Dictionary-based compression schemes provide fast decoding operation, typically at the expense of reduced compression effectiveness compared to statistical or probability-based approaches. In this work, we apply dictionary-based techniques to the compression of inverted lists, showing that the high degree of regularity that these integer sequences exhibit is a good match for certain types of dictionary methods, and that an important new trade-off balance between compression effectiveness and compression efficiency can be achieved. Our observations are supported by experiments using the document-level inverted index data for two large text collections, and a wide range of other index compression implementations as reference points. Those experiments demonstrate that the gap between efficiency and effectiveness can be substantially narrowed.

Source: International Conference on Web Search and Data Mining, pp. 6–14, 11/02/2019,15/02/2019

Metrics