Bitpacking and Compression of Sparse Datasets
moderndescartes.com
Bitpacking and Compression of Sparse Datasets
1–10 of 16 posts
Re: Bitpacking and Compression of Sparse Datasets
#2Try ZDtandard. You can spend as tune compression speed vs. compression ratio. Decompressing is always fast.
It was recently released: https://github.com/facebook/zstd
Re: Bitpacking and Compression of Sparse Datasets
#3Re: Bitpacking and Compression of Sparse Datasets
#4Try ZDtandard. You can spend as tune compression speed vs. compression ratio. Decompressing is always fast. It was recently released: https://github.com/facebook/zstd
[deleted]
Re: Bitpacking and Compression of Sparse Datasets
#5http://roaringbitmap.org/
+1 to this. OP is using the wrong flavor of compression for the task at hand. OP, look up sparse bitmaps.
Re: Bitpacking and Compression of Sparse Datasets
#6RDF HDT (Header Dictionary Triples) is a clever storage format for linked data.
Re: Bitpacking and Compression of Sparse Datasets
#7Informative read, seems like the author learned some things and empirically discovered that his/her solution was ultimately a case of balancing trade-offs in generality vs specificity. As stated in the "Conclusions" section toward the bottom of the page, "If you know the structure of your data, you can easily do a better and faster job of compressing than a generic compression algorithm."
Re: Bitpacking and Compression of Sparse Datasets
#8> If you know the structure of your data, you can easily do a better and faster job of compressing than a generic compression algorithm.
I'd change this to: the ease of doing a better and faster job of compressing than a generic compression algorithm will be a function of the data's Kolmogorov Complexity.
You can easily know your data's structure (e.g. strings no larger than N bytes containing natural language in a line-separated file) and not be able to (easily) do better than a generic compressor due to the complexity of the required compression / reconstruction operations.
Re: Bitpacking and Compression of Sparse Datasets
#9> If you know the structure of your data, you can easily do a better and faster job of compressing than a generic compression algorithm. I'd change this to: the ease of doing a better and faster job of compressing than a generic compression algorithm will be a function of the data's Kolmogorov Complexity. You can easily know your data's structure (e.g. strings no larger than N bytes containing natural language in a l…
Not quite; I would describe it as moving the complexity into the algorithm. For example, even though the bitpacking from the post achieves fast good compression, it is unable to compress floats in general; merely 1.0 and 0.0. The knowledge of that correspondence has been moved into the algorithm.
Re: Bitpacking and Compression of Sparse Datasets
#10> If you know the structure of your data, you can easily do a better and faster job of compressing than a generic compression algorithm. I'd change this to: the ease of doing a better and faster job of compressing than a generic compression algorithm will be a function of the data's Kolmogorov Complexity. You can easily know your data's structure (e.g. strings no larger than N bytes containing natural language in a l…
Not quite; I would describe it as moving the complexity into the algorithm. For example, even though the bitpacking from the post achieves fast good compression, it is unable to compress floats in general; merely 1.0 and 0.0. The knowledge of that correspondence has been moved into the algorithm.
> For example, even though the bitpacking from the post achieves fast good compression, it is unable to compress floats in general; merely 1.0 and 0.0.
Fewer bits does not always mean better compression, particularly if the data has other patterns which is destroyed by the packing.
With Apache ORC, I found out that if you bit-pack data to say 7bits vs leaving it as 8 bits, the 8 bits version compressed much more with Zlib than the 7 bit version.
This had to do with the data getting a bit offset into the previous byte sequence, until what was a sequence of repeating bytes turned into a pattern which repeats far less often.
Leaving the extra bit in place, helped Zlib dictionary encoding and huffman work much better than trying to save a bit.
The final kicker was that the 24 bit sequence was faster to read than a 23 or 21 bit sequence, but purely due to the fact that the word aligned stuff can be decoded in SIMD.
I'm no better at guessing what would work - "whatever works ... works, so try them.".