Hello Liya Fan,
this explains the technique but for a more complex case: https://fgiesen.wordpress.com/2011/01/24/x86-code-compression-in-kkrunchy/ For FP data, the approach which seemed to be the best is the following. Say we have a buffer of two 32-bit floating point values: buf = [af, bf] We interpret each FP value as a 32-bit uint and look at each individual byte. We have 8 bytes in total for this small input. buf = [af0, af1, af2, af3, bf0, bf1, bf2, bf3] Then we apply stream splitting and the new buffer becomes: newbuf = [af0, bf0, af1, bf1, af2, bf2, af3, bf3] We compress newbuf. Due to similarities the sign bits, mantissa bits and MSB exponent bits, we might have a lot more repetitions in data. For scientific data, the 2nd and 3rd byte for 32-bit data is probably largely noise. Thus in the original representation we would always have a few bytes of data which could appear somewhere else in the buffer and then a couple bytes of possible noise. In the new representation we have a long stream of data which could compress well and then a sequence of noise towards the end. This transformation improved compression ratio as can be seen in the report. It also improved speed for ZSTD. This could be because ZSTD makes a decision of how to compress the data - RLE, new huffman tree, huffman tree of the previous frame, raw representation. Each can potentially achieve a different compression ratio and compression/decompression speed. It turned out that when the transformation is applied, zstd would attempt to compress fewer frames and copy the other. This could lead to less attempts to build a huffman tree. It's hard to pin-point the exact reason. I did not try other lossless text compressors but I expect similar results. For code, I can polish my patches, create a Jira task and submit the patches for review. Regards, Martin ________________________________ From: Fan Liya <liya.fa...@gmail.com> Sent: Thursday, July 11, 2019 11:32:53 AM To: dev@arrow.apache.org Cc: Raoofy, Amir; Karlstetter, Roman Subject: Re: Adding a new encoding for FP data Hi Radev, Thanks for the information. It seems interesting. IMO, Arrow has much to do for data compression. However, it seems there are some differences for memory data compression and external storage data compression. Could you please provide some reference for stream splitting? Best, Liya Fan On Thu, Jul 11, 2019 at 5:15 PM Radev, Martin <martin.ra...@tum.de> wrote: > Hello people, > > > there has been discussion in the Apache Parquet mailing list on adding a > new encoder for FP data. > The reason for this is that the supported compressors by Apache Parquet > (zstd, gzip, etc) do not compress well raw FP data. > > > In my investigation it turns out that a very simple simple technique, > named stream splitting, can improve the compression ratio and even speed > for some of the compressors. > > You can read about the results here: > https://drive.google.com/file/d/1wfLQyO2G5nofYFkS7pVbUW0-oJkQqBvv/view > > > I went through the developer guide for Apache Arrow and wrote a patch to > add the new encoding and test coverage for it. > > I will polish my patch and work in parallel to extend the Apache Parquet > format for the new encoding. > > > If you have any concerns, please let me know. > > > Regards, > > Martin > >
