Bicriteria data compression: efficient and usable (Contributo in atti di convegno)

Type
Label
  • Bicriteria data compression: efficient and usable (Contributo in atti di convegno) (literal)
Anno
  • 2014-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1007/978-3-662-44777-2_34 (literal)
Alternative label
  • Farruggia A., Ferragina P., Venturini R. (2014)
    Bicriteria data compression: efficient and usable
    in ESA 2014 - Algorithms. 22th Annual European Symposium, Wroclaw, Poland, 8-10 September 2014
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Farruggia A., Ferragina P., Venturini R. (literal)
Pagina inizio
  • 406 (literal)
Pagina fine
  • 417 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#url
  • http://link.springer.com/chapter/10.1007%2F978-3-662-44777-2_34 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 8737 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#volumeInCollana
  • 8737 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali
  • 12 (literal)
Note
  • PuMa (literal)
  • ISI Web of Science (WOS) (literal)
  • Scopu (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Department of Computer Science, University of Pisa, Italy; Department of Computer Science, University of Pisa, Italy, CNR-ISTI, Pisa, Italy (literal)
Titolo
  • Bicriteria data compression: efficient and usable (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#isbn
  • 978-3-662-44776-5 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#curatoriVolume
  • Andreas S. Schulz, Dorothea Wagner (literal)
Abstract
  • Lempel-Ziv's LZ77 algorithm is the de facto choice for compressing massive datasets (see e.g., Snappy in BigTable, Lz4 in Cassandra) because its algorithmic structure is flexible enough to guarantee very fast decompression speed at reasonable compressed-space occupancy. Recent theoretical results have shown how to design a bit-optimal LZ77-compressor which minimizes the compress size and how to deploy it in order to design a bicriteria data compressor, namely an LZ77-compressor which trades compressed-space occupancy versus its decompression time in a smoothed and principled way. Preliminary experiments were promising but raised many algorithmic and engineering questions which have to be addressed in order to turn these algorithmic results into an effective and practical tool. In this paper we address these issues by first designing a novel bit-optimal LZ77-compressor which is simple, cache-aware and asymptotically optimal. We benchmark our approach by investigating several algorithmic and implementation issues over many dataset types and sizes, and against an ample class of classic (LZ-based, PPM-based and BWT-based) as well as engineered compressors (Snappy, Lz4, and Lzma2). We conclude noticing how our novel bicriteria LZ77-compressor improves the state-of-the-art of fast (de) compressors Snappy and Lz4. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Insieme di parole chiave di
data.CNR.it