0, 1, 2, 3, 1000, 1001, 1002, 1003, ...
your deltas (assuming strict monotonicity) are
0, 0, 0, 0, 996, 0, 0, 0 ...
and that 996 breaks a run that you could otherwise encode in 0 bits (plus block metadata).
Variable-length coding requires that each integer somehow encodes its width. That can be very wasteful. Block-based methods exploit the fact that consecutive deltas usually require a similar number of bits, so it's better to waste a bit on each integer, but amortize the block bitwidth, than having to encode each width independently.
In the end the result is probably heavily dependent on the exact structure of the integer lists you want to compress but I do not see how fixed length deltas can be competitive on arbitrary inputs.
> I do not see how fixed length deltas can be competitive on arbitrary inputs.
I also already explained this, most lists in practical applications exhibit local properties that are exploited by blocking.
Using Huffman/arithmetic coding generally doesn't work well because the cost of storing the probability tables does not break even with the savings. There was a recent line of work [1] that attempted this with ANS, a faster cousin of arithmetic coding, and the results were honestly underwhelming considering the complexity involved.
[1] https://dl.acm.org/doi/abs/10.1145/3159652.3159663
> In the end the result is probably heavily dependent on the exact structure of the integer lists
Yes, I did not claim that this works with any list, for any encoding scheme you can construct adversarial cases that do not compress well, that's just information theory. But that applies also to the schemes you're floating.
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
[2] https://dl.acm.org/doi/10.1145/1871437.1871592
[3] https://arxiv.org/pdf/1209.2137.pdf