Algorithm for compressing binary data that can efficiently be partially decompressed

Question

So I have been given the following problem and since I have no experience at all in this field, I would really appreciate some advice/guidance.

These are the requirements:

So three times per second a certain amount (fixed per session) of 32-bit values come in. These values have to be stored into a file with a timestamp per data-entry and it must be possible to at any time, with a given timestamp and interval, read out the values that are stored in that file.

This is all relatively simple to do, but this produces a 5GB file every 24 hours. If this file is zipped, it just leaves a 500MB file, so it is compressable but in that case you can't instantly retreive datapoints because you would have to unzip the entire file.

So I was thinking that this could be solved like this:

• Buffer the first 10MB of sensor data.
• Then sort all the values by the amount of times that they contain the same value. (Sensor data, so quite a few of the channels will mostly contain stable values)
• Run an algorithm that detects recurring patterns, replaces those patterns with shorter values and defines a table with the recurring patterns and their replacements.
• The compress the buffer and save it to the disk and compress every new series of sensor data with the pre-defined table.

If this would be implemented properly, it should be possible to uncompress an individual datapoint and the file is sorted by timestamp so finding the right one should be trivial with a binary search.

So I guess the questions I'm having are the follwing

1. Is this at all possible? I do not expect compression results near Zip and 2x - 5x would be enough.
2. What is a good (and if possible semi-easy to implement) algorithm to find patterns in binary data? I have been doing some research and I mostly ran into algorithms that only apply to text data.

Any form of help is greatly appreciated!

Answer 1

Eliminate timestamps

If the data is sampled at regular intervals (e.g. three times per second), it is sufficient to store the timestamp of the first point and the interval. This enables you to calulate the offset from a timestamp and vice versa and grants you access to any datapoint in constant time.

Compression schemes

As others have already laid out, you will always lose the ability to seek when using a compression scheme. Compress blockwise and search within the blocks.

Lempel-Ziv-like algorithms

The Lempel-Ziv family and similar algorithms provide good compression for data with many/long reoccurring strings, but fail to recognize the relationship between integers in noisy or slowly changing sequences. Below are three sequences of integers: the first consists of constant values, the second counts upward and somehow resembles timestamps, and the third is noisy and represents a sensor reading.

$$[900, 900, 900, 900, 900, 900, 900, 900, 900, 900]$$ $$[890, 892, 894, 896, 898, 900, 902, 904, 906, 908]$$ $$[900, 890, 905, 901, 918, 892, 919, 916, 904, 920]$$

Zip will greatly reduce the size of the first sequence, have a hard time on the second and won't provide any compression on the third.

Delta encoding

To reduce the number of bits per number, the range of possible numbers must get smaller. If we incorporate the knowledge that values change slowly, we conclude that storing only the difference to the previous value yields values close to zero. The three example sequences above become:

$$[900, 0, 0, 0, 0, 0, 0, 0, 0, 0]$$ $$[890, 2, 2, 2, 2, 2, 2, 2, 2, 2]$$ $$[900, -10, 15, -4, 17, -26, 27, -3, -12, 16]$$

If we know the rate of change is approximately constant, as in case of timestamps, we can apply delta encoding twice. Below is a sequence of timestamps in original form and after applying delta encoding once/twice.

$$[96, 296, 497, 701, 904, 1102]$$ $$[96, 200, 201, 204, 203, 198]$$ $$[96, 104, 1, 3, -1, -5]$$

All we need now is a way to make the (on average) smaller numbers into less disk space.

Variable width integers

We can reduce the number of bits by using variable width integers that use less bits for smaller (by magnitude) numbers. The usual encoding is:

• For numbers that fit into 7-bit signed integers, use one byte.
• For larger numbers
  • store the 7 least significant bits in one byte.
  • set the MSB (continue-flag).
  • encode the remainder in the following bytes, using the same encoding.

This way 32-bit integers are encoded in 1-5 bytes, dependent on the actual value.

Conclusion

• If possible, don't store timestamps at all (independent of compression).
• Compress in blocks. Trade-off between access time and compression.
• If the sensor readings are exactly constant for some periods of time, zip is the way to go.
• If the sensor readings are approximately constant, use delta encoding.
• If the timestamps are changing at approximately constant rate, use delta encoding twice.

Answer 2

One way is to compress the file in smaller chunks. Store the contents of the files in some sort of index to facilitate search. Alternatively, since data is stored 3 times per second, you can just reflect the time chunk of each file through its name, and then search is also easy.

Answer 3

If this would be implemented properly, it should be possible to uncompress an individual datapoint

That is clearly (well, knowing how compression workds) only possible if you compress each data point by itself, which will not do much if these data are small.

I do not expect compression results near Zip and 2x - 5x would be enough.

Keep in mind that no lossless compression algorithm can guarantee any such rate. There's an easy-to-prove no-free-lunch theorem; every such algorithm has to make some inputs longer.

What is a good (and if possible semi-easy to implement) algorithm to find patterns in binary data?

The concept of how humans think about "patterns" is misleading. General-purpose compression algorithms are application- and encoding-agnostic; they won't use any pattern you'll see as such.

it must be possible to at any time, with a given timestamp and interval, read out the values that are stored in that file

The solution is clearly to save smaller files. The size depends on how small you need the resulting files to be, that is how long decompression may take. Say, files with one hour of sensor data are small enough; then you just save one (compressed) file per hour.

You should look into the Lempel-Ziv family of compression algorithms. They work with any string data, and binary strings are just that.

---

That said, there is research on searchable compressed data. I think that is overkill in your situation, though.

Answer 4

Sorry to you guys who posted such a detailed answer, I ended up solving this in a quite simple way.

I ended up just compressing the data points individually and because the entries are quite large (60-600 kb) compression rates up to 12x are possible. (using zlib)

When a new file is created, I reserve the first part of the file to serve as "table of contents". The file starts with a "file-header" that contains the first and last timestamp that can be found in the file and the current amount of data points put in the file. Following that is a long list of equally sized "data-pointers" containing the timestamp and the offset in file. Due to all the reserved space for the headers this initially gives a file of 4MiB even when there is no data in it, but this is quickly negligable by the space saved by the compression. After the "table of contents" is each datapoint in compressed form one after another.

This makes it possible to do a binary search for the right data, and even in a file of several GB's the right data can be found in a matter of milliseconds. I initially set zlib to MAX_COMPRESSION, but this took up way more time than MAX_SPEED and just resulted in a minor change in compression rate. And at maximum stress (600KiB entries at 20Hz) it was barely keeping using MAX_COMPRESSION.