5 ms·

For anyone who wants really good compression of data with a particular characteristic, a very useful approach is to first shrink or reformat the data based on t

For anyone who wants really good compression of data with a particular characteristic, a very useful approach is to first shrink or reformat the data based on that characteristic, then pass the result through a general purpose compressor. For this case that might mean convert the data into deltas, then write those deltas in a byte-oriented variable length integer fashion. The general purpose compressor can then pick up most of what you have left on the table by not being super careful with the balancing of the chosen integer format, and it might find some other useful patterns in the data without you having to worry about those. Theoretically a single compressor crafted purely for the exact characteristics of the data at hand would be able to do a better job. But in practice the skill and time required to beat the hybrid approach tends to be a showstopper.

jhgb 5y ago
> For this case that might mean convert the data into deltas, then write those deltas in a byte-oriented variable length integer fashion. Calculating a trend line and storing deltas off of that trend line might be mildly better for some series. Having an AR model and storing errors of the model might work even better, although the obvious (and common) problem is which AR model of the many possible ones you go for.
- ballenf 5y ago
  Or simply a delta off the last delta (or mean of last n deltas, I guess), so you can do the compression in a stream.
  - jhgb 5y ago
    That might also be equivalent to one of the ARMA models, although I'd have to do the math to prove that (and to derive which one corresponds to what you're describing). Edit: It seems that if you detrend the data, the "delta off the last delta", if I understand it correctly, is an MA(1) model. I think. Maybe. My math is wobbly.
  - wallacoloo 5y ago
    If I understand you & GP, these are both just particular instantiations of Linear Predictive Coding [1]. For both of these approaches, you’d probably get similar or better results just throwing your data into an off-the-shelf LPC, and with less effort. [1] https://en.m.wikipedia.org/wiki/Linear_predictive_coding https://en.m.wikipedia.org/wiki/Linear_predictive_coding
- NohatCoder 5y ago
  If you know the specifics of your data, maybe. But try to err on the side of simpler models, every detail you add slows your code down, and the difference after compression is often small.
ayende 5y ago
Original poster here: I have tried doing that in the past, and the issue is that the overall cost in computation power is higher, and the compression rate is poorer than when you can optimize for that. Other aspects that touch on that is that we are usually not dealing with large amount of data, so there isn't enough room for a general algorithm to play its strengths. For various reasons, we'll rarely see the raw data higher than 1 - 2 KB for each segment.

jhgb 5y ago

> For this case that might mean convert the data into deltas, then write those deltas in a byte-oriented variable length integer fashion. Calculating a trend line and storing deltas off of that trend line might be mildly better for some series. Having an AR model and storing errors of the model might work even better, although the obvious (and common) problem is which AR model of the many possible ones you go for.

ballenf 5y ago
Or simply a delta off the last delta (or mean of last n deltas, I guess), so you can do the compression in a stream.
- jhgb 5y ago
  That might also be equivalent to one of the ARMA models, although I'd have to do the math to prove that (and to derive which one corresponds to what you're describing). Edit: It seems that if you detrend the data, the "delta off the last delta", if I understand it correctly, is an MA(1) model. I think. Maybe. My math is wobbly.
- wallacoloo 5y ago
  If I understand you & GP, these are both just particular instantiations of Linear Predictive Coding [1]. For both of these approaches, you’d probably get similar or better results just throwing your data into an off-the-shelf LPC, and with less effort. [1] https://en.m.wikipedia.org/wiki/Linear_predictive_coding https://en.m.wikipedia.org/wiki/Linear_predictive_coding
NohatCoder 5y ago
If you know the specifics of your data, maybe. But try to err on the side of simpler models, every detail you add slows your code down, and the difference after compression is often small.

ayende 5y ago

Original poster here: I have tried doing that in the past, and the issue is that the overall cost in computation power is higher, and the compression rate is poorer than when you can optimize for that. Other aspects that touch on that is that we are usually not dealing with large amount of data, so there isn't enough room for a general algorithm to play its strengths. For various reasons, we'll rarely see the raw data higher than 1 - 2 KB for each segment.