http://www.cnr.it/ontology/cnr/individuo/prodotto/ID160304

VSEncoding: efficient coding and fast decoding of integer lists via dynamic programming (Rapporti tecnici/preprint/working paper)

Type

Label

VSEncoding: efficient coding and fast decoding of integer lists via dynamic programming (Rapporti tecnici/preprint/working paper) (literal)

Anno

Alternative label

Silvestri F.; Venturini R. (2010)
VSEncoding: efficient coding and fast decoding of integer lists via dynamic programming
(literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note

VSEncoding: Efficient Coding and Fast Decoding of Integer Lists via Dynamic Programming. Technical report, 2010. (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#descrizioneSinteticaDelProdotto

ABSTRACT: 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 t (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#supporto