6 ms·

Sorted Integer Compression

63 points by GordonS 5y ago

touisteur 5y ago
I've been having loads of fun and success with roaring bitmaps recently, to create this type of index for large data.
PaulHoule 5y ago
This book has a nice treatment of that kind of compression: https://www.amazon.com/Managing-Gigabytes-Compressing-Multimedia-Information/dp/1558605703 https://www.amazon.com/Managing-Gigabytes-Compressing-Multim... For instance you might be keep track of facts like the word "the" is contained in document 1 the word "john" is contained in document 1 the word "the" is contained in document 2 ... the word "john" is contained in document 12 and you code the gaps; the word "the" appears in every document and the gap is always 1, but the gap for "john" is 11. With a variable-sized encoding you use fewer bits for smaller gaps -- with that kind of encoding you don't have to make "the" be a stopword because you can afford to encode all the postings.
- atombender 5y ago
  That book is great, and relies on a combination of Golomb-Rice, delta coding, and arithmetic coding. I wonder how this compares with the OP's compression.
  - PaulHoule 5y ago
    ... it doesn't just "rely on" that stuff, but it explains the fundamentals of them really well!
- tgv 5y ago
  The Standard MIDI file spec had something similar back in 80s. They code gaps between successive events with increasingly longer byte sequences. Never mind that they waste a whole bit to do that.
- ot 5y ago
  That book is really dated (1994), but unfortunately there aren't much better options. It is unfortunate because the understanding of the field has improved dramatically over the past decades, and explanations from a more modern perspective would benefit even novices.
ot 5y ago
> For my purpose, I want to get as high a compression rate as possible, and I need to store just the list of integers Then PFor(Delta) is not the best option, that class of algorithms is intentionally a trade-off between compression rate and decoding speed, as it's meant to store posting lists in inverted indexes. If you want higher compression, a better option would be Binary Interpolative Coding [1], which has some of the highest compression rate among the schemes that are relatively simple to implement. Then you can go down the rabbit hole and start to use entropy compression, complex modeling, etc... But there are diminishing returns. > The problem with PFor, however, is that if you have a single large outlier, you’ll waste a lot of bits unnecessarily. This is not true, the author is describing binary packing of deltas, and mistaking it for PFor. What PForDelta means is - P -> Patched: Outliers are stored separately in a list of "exceptions", so that does not affect the bit size of the rest of the block - For -> Frame of Reference: the min value of the block is subtracted from the values in block, which are then encoded with the minimum number of bits necessary for the adjusted maximum (this is just binary packing) - Delta -> Deltas are encoded instead of values, only used if your sequence is monotonic. If it is strictly monotonic, you can encode v[i+1] - v[i] - 1 and save a little more. > This encoder will [...] Then we check the top and bottom halves of the batch, to see if we’ll get a benefit from recording them separately. What this is describing is an algorithm for partitioning lists in order to optimize for the overall binary packing compression rate; but it is greedy, and optimal algorithms exist based on dynamic programming [2] EDIT: Forgot to mention that everything I wrote above is also explained in the paper cited in the post [3], which is indeed a very good survey of this stuff. [1] https://link.springer.com/article/10.1023/A:1013002601898 https://link.springer.com/article/10.1023/A:1013002601898 [2] https://dl.acm.org/doi/10.1145/1871437.1871592 https://dl.acm.org/doi/10.1145/1871437.1871592 [3] https://arxiv.org/pdf/1209.2137.pdf https://arxiv.org/pdf/1209.2137.pdf
- recursive 5y ago
  In a sorted list, all the outliers are grouped at the beginning or the end. It's hard to understand how storing the single big delta is using any bits unnecessarily.
  - ot 5y ago
7373737373 5y ago
There is the Hutter Prize for English text compression (http://prize.hutter1.net/ http://prize.hutter1.net/), I wish there was an equivalent for the https://oeis.org https://oeis.org database: https://github.com/void4/notes/issues/72 https://github.com/void4/notes/issues/72
raphlinus 5y ago
It reminds me of the classic interview problem, attributed to Google: sort 1 million 32 bit integers (provided as a stream) using 2 megabytes of memory. Most people's first instinct is that it can't be done, you need almost 4 megabytes to store the input, but of course it can be, you keep the sorted list in compressed form. I haven't found a really good writeup, most of the hits on Google (SO, earlier HN stories) fail to get the answer.
- tyingq 5y ago
  Guido van Rossum's answer, of course with Python: http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html http://neopythonic.blogspot.com/2008/10/sorting-million-32-b... It sounds like "break up into smaller sorted sets, then do a merge sort". Does the Google interview question allow for temp file storage?
  - raphlinus 5y ago
    There are two versions of the question. One allows external storage (Guido's answer and the top hit on SO), the other does not.
- sltkr 5y ago
  I think there are two difficulties here. 1. How to even represent 1,000,000,000 sorted integers in only 2 megabytes, which means you can use (slightly more than) 2 bytes per integer. The central observation is that the sum of the deltas is no more than 4294967296. 4294967296 / 1000000 = 4295 which is about 13 bits, so it seems like it should be possible, but it's not easy. For example, if you use a standard variable length encoding where the highest bit indicates continuation, you would have 7 data bits per byte, but you could have 743,665 times 128 and 256,335 times 16384, which would require 743,665*2 + 256,335*3 = 2,256,335 bytes, which is slightly over 2 megabyte. If you use the first two bits of the initial byte (so that K bytes encode 8*K - 2 bits). You could have 740,749 times 64 259,251 times 16384, for a total of 259251*3 + 740749*2 = 2,259,251 bytes, slightly worse even. With 1 continuation bit per nibble the math similarly doesn't work out. So this is starting to look, if not impossible, at least very hard. 2. Imagine that you could represent 1,000,000 sorted integers in 2 megabytes somehow. Then the next problem is to actually create such a sorted sequence from the input. - Insertion sort works, but O(N^2) time complexity is not great with a million elements. - Quick sort doesn't work since you'd start with an unsorted array which you cannot represent in memory. - Heap sort doesn't work because it requires random access to the array, which doesn't work with a variable-length encoding. - Merge sort works in the beginning, but you need temporary space equal to the size of your input, so towards the end you're in trouble. I think you could make merge sort work if the requirement is "output the elements in sorted order" rather than actually constructing a sorted representation of the array. In that case, you could create sorted sequences of the first 500,000, 250,000, 125,000 etc. elements, and do a 20-way merge in the end, which is O(N log N) overall. This is still somewhat tricky because the average delta of e.g. 500,000 elements can be twice as large as for the overall array, so you might need slightly more space to encode it, so we would need a really efficient compression scheme to make this work. All in all I'm gravitating towards: this problem isn't generally solvable under the given constraints. With 3 megabytes I think the scheme outlined above works.
glebm 5y ago
Elias-Fano would probably be a better option here
- js8 5y ago
  Yeah, and somebody has even done that: https://www.antoniomallia.it/sorted-integers-compression-with-elias-fano-encoding.html https://www.antoniomallia.it/sorted-integers-compression-wit...
- ot 5y ago
  EF doesn't compress that well if your data exhibits regularities, it uses exactly a number of bits that only depends on the sequence upper bound and length. There are ways to make it compress better though, like splitting the sequence into chunks, optimizing for the overall compressed size.
pklausler 5y ago
The Burrows-Wheeler transform (https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf...) might be handy for this problem case; encode the deltas with something like UTF-8 first.
NohatCoder 5y ago
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

63 points by GordonS 5y ago

I've been having loads of fun and success with roaring bitmaps recently, to create this type of index for large data.

This book has a nice treatment of that kind of compression: https://www.amazon.com/Managing-Gigabytes-Compressing-Multimedia-Information/dp/1558605703 https://www.amazon.com/Managing-Gigabytes-Compressing-Multim... For instance you might be keep track of facts like the word "the" is contained in document 1 the word "john" is contained in document 1 the word "the" is contained in document 2 ... the word "john" is contained in document 12 and you code the gaps; the word "the" appears in every document and the gap is always 1, but the gap for "john" is 11. With a variable-sized encoding you use fewer bits for smaller gaps -- with that kind of encoding you don't have to make "the" be a stopword because you can afford to encode all the postings.

atombender 5y ago
That book is great, and relies on a combination of Golomb-Rice, delta coding, and arithmetic coding. I wonder how this compares with the OP's compression.
- PaulHoule 5y ago
  ... it doesn't just "rely on" that stuff, but it explains the fundamentals of them really well!
tgv 5y ago
The Standard MIDI file spec had something similar back in 80s. They code gaps between successive events with increasingly longer byte sequences. Never mind that they waste a whole bit to do that.
ot 5y ago
That book is really dated (1994), but unfortunately there aren't much better options. It is unfortunate because the understanding of the field has improved dramatically over the past decades, and explanations from a more modern perspective would benefit even novices.

ot 5y ago

> For my purpose, I want to get as high a compression rate as possible, and I need to store just the list of integers Then PFor(Delta) is not the best option, that class of algorithms is intentionally a trade-off between compression rate and decoding speed, as it's meant to store posting lists in inverted indexes. If you want higher compression, a better option would be Binary Interpolative Coding [1], which has some of the highest compression rate among the schemes that are relatively simple to implement. Then you can go down the rabbit hole and start to use entropy compression, complex modeling, etc... But there are diminishing returns. > The problem with PFor, however, is that if you have a single large outlier, you’ll waste a lot of bits unnecessarily. This is not true, the author is describing binary packing of deltas, and mistaking it for PFor. What PForDelta means is - P -> Patched: Outliers are stored separately in a list of "exceptions", so that does not affect the bit size of the rest of the block - For -> Frame of Reference: the min value of the block is subtracted from the values in block, which are then encoded with the minimum number of bits necessary for the adjusted maximum (this is just binary packing) - Delta -> Deltas are encoded instead of values, only used if your sequence is monotonic. If it is strictly monotonic, you can encode v[i+1] - v[i] - 1 and save a little more. > This encoder will [...] Then we check the top and bottom halves of the batch, to see if we’ll get a benefit from recording them separately. What this is describing is an algorithm for partitioning lists in order to optimize for the overall binary packing compression rate; but it is greedy, and optimal algorithms exist based on dynamic programming [2] EDIT: Forgot to mention that everything I wrote above is also explained in the paper cited in the post [3], which is indeed a very good survey of this stuff. [1] https://link.springer.com/article/10.1023/A:1013002601898 https://link.springer.com/article/10.1023/A:1013002601898 [2] https://dl.acm.org/doi/10.1145/1871437.1871592 https://dl.acm.org/doi/10.1145/1871437.1871592 [3] https://arxiv.org/pdf/1209.2137.pdf https://arxiv.org/pdf/1209.2137.pdf

recursive 5y ago
In a sorted list, all the outliers are grouped at the beginning or the end. It's hard to understand how storing the single big delta is using any bits unnecessarily.
- ot 5y ago

7373737373 5y ago

There is the Hutter Prize for English text compression (http://prize.hutter1.net/ http://prize.hutter1.net/), I wish there was an equivalent for the https://oeis.org https://oeis.org database: https://github.com/void4/notes/issues/72 https://github.com/void4/notes/issues/72

raphlinus 5y ago

It reminds me of the classic interview problem, attributed to Google: sort 1 million 32 bit integers (provided as a stream) using 2 megabytes of memory. Most people's first instinct is that it can't be done, you need almost 4 megabytes to store the input, but of course it can be, you keep the sorted list in compressed form. I haven't found a really good writeup, most of the hits on Google (SO, earlier HN stories) fail to get the answer.

tyingq 5y ago
Guido van Rossum's answer, of course with Python: http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html http://neopythonic.blogspot.com/2008/10/sorting-million-32-b... It sounds like "break up into smaller sorted sets, then do a merge sort". Does the Google interview question allow for temp file storage?
- raphlinus 5y ago
  There are two versions of the question. One allows external storage (Guido's answer and the top hit on SO), the other does not.
sltkr 5y ago
I think there are two difficulties here. 1. How to even represent 1,000,000,000 sorted integers in only 2 megabytes, which means you can use (slightly more than) 2 bytes per integer. The central observation is that the sum of the deltas is no more than 4294967296. 4294967296 / 1000000 = 4295 which is about 13 bits, so it seems like it should be possible, but it's not easy. For example, if you use a standard variable length encoding where the highest bit indicates continuation, you would have 7 data bits per byte, but you could have 743,665 times 128 and 256,335 times 16384, which would require 743,665*2 + 256,335*3 = 2,256,335 bytes, which is slightly over 2 megabyte. If you use the first two bits of the initial byte (so that K bytes encode 8*K - 2 bits). You could have 740,749 times 64 259,251 times 16384, for a total of 259251*3 + 740749*2 = 2,259,251 bytes, slightly worse even. With 1 continuation bit per nibble the math similarly doesn't work out. So this is starting to look, if not impossible, at least very hard. 2. Imagine that you could represent 1,000,000 sorted integers in 2 megabytes somehow. Then the next problem is to actually create such a sorted sequence from the input. - Insertion sort works, but O(N^2) time complexity is not great with a million elements. - Quick sort doesn't work since you'd start with an unsorted array which you cannot represent in memory. - Heap sort doesn't work because it requires random access to the array, which doesn't work with a variable-length encoding. - Merge sort works in the beginning, but you need temporary space equal to the size of your input, so towards the end you're in trouble. I think you could make merge sort work if the requirement is "output the elements in sorted order" rather than actually constructing a sorted representation of the array. In that case, you could create sorted sequences of the first 500,000, 250,000, 125,000 etc. elements, and do a 20-way merge in the end, which is O(N log N) overall. This is still somewhat tricky because the average delta of e.g. 500,000 elements can be twice as large as for the overall array, so you might need slightly more space to encode it, so we would need a really efficient compression scheme to make this work. All in all I'm gravitating towards: this problem isn't generally solvable under the given constraints. With 3 megabytes I think the scheme outlined above works.

glebm 5y ago

Elias-Fano would probably be a better option here

js8 5y ago
Yeah, and somebody has even done that: https://www.antoniomallia.it/sorted-integers-compression-with-elias-fano-encoding.html https://www.antoniomallia.it/sorted-integers-compression-wit...
ot 5y ago
EF doesn't compress that well if your data exhibits regularities, it uses exactly a number of bits that only depends on the sequence upper bound and length. There are ways to make it compress better though, like splitting the sequence into chunks, optimizing for the overall compressed size.

pklausler 5y ago

The Burrows-Wheeler transform (https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf...) might be handy for this problem case; encode the deltas with something like UTF-8 first.

NohatCoder 5y ago

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