Istituto di Scienza e Tecnologie dell'Informazione     
Silvestri F., Venturini R. VSEncoding: efficient coding and fast decoding of integer lists via dynamic programming. In: Conference on Information and Knowledge Management (Toronto, Canada, 27 ottobre 2010). Proceedings, pp. 1219 - 1228. ACM, 2010.
Encoding lists of integers efficiently is important for many applications in different fields. Adjacency lists of large graphs are usually encoded to save space and to improve decoding speed. Inverted indexes of Information Retrieval systems keep the lists of postings compressed in order to exploit the memory hierarchy. Secondary indexes of DBMSs are stored similarly to inverted indexes in IR systems. In this paper we propose Vector of Splits Encoding (VSEncoding), a novel class of encoders that work by optimally partitioning a list of integers into blocks which are efficiently compressed by using simple encoders. In previous works heuristics were applied during the partitioning step. Instead, we find the optimal solution by using a dynamic programming approach. 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 a very fast decompression algorithm.
Subject Data Compression
Inverted lists
H.3.2 Information Storage
E.2 Data Storage Representations

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional