Bicriteria data compression

The advent of massive datasets and the consequent design of high-performing distributed storage systems—such as BigTable by Google [7], Cassandra by Facebook [5], Hadoop by Apache—have reignited the interest of the scientific and engineering community towards the design of lossless data compressors which achieve effective compression ratio and very efficient decompression speed. Lempel-Ziv’s LZ77 algorithm is the de facto choice in this scenario because its decompression is significantly faster than other approaches, and its algorithmic structure is flexible enough to trade decompression speed versus compressed-space efficiency. This algorithm has been declined in many ways, the most famous ones are: the classic gzip, LZ4 and Google’s Snappy. Each of these implementations offers a trade-off between space occupancy and decompression speed, so software engineers have to content themselves by picking the one which comes closer to the requirements of the application in their hands. Starting from these premises, and for the first time in the literature, we address in this paper the problem of trading optimally, and in a principled way, the consumption of thes