VSEncoding: efficient coding and fast decoding of integer lists via dynamic programming

Silvestri F., Venturini R.

Systems and Software  Coding and Information Theory. Data compaction and compression  d-gap encoding  Inverted index encoding  Adaptive encoding 

Encoding lists of integers in an efficient manner is key task in many applications in different fields. Adjacency lists of large graphs are usually encoded to save space and to im- prove decoding speed. Inverted indexes of Information Re- trieval systems keep the lists of postings usually compressed to allow an optimal utilization of memory hierarchy. Sec- ondary indexes of DBMS's are stored similarly to inverted indexes in IR systems. In this paper we propose a novel class of encoders (called VSEncoding from Vector of Splits Encoding) that, roughly speaking, work by partitioning an list of integers into blocks which are efficiently compressed by using simple encoders. Differently from previous work where heuristics were applied during the partitioning step, we carry out this important step via dynamic programming, which leads to produce the optimal solution. Experiments show that our class of encoders outperform all the existing methods in literature by more than 10% (with the exception of Binary Interpolative Coding with which they, roughly, tie) still retaining very fast decompression.

Source: ISTI Technical reports, 2010