3 ms·

> 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,

by 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
  The outliers the article is talking about here are in the *deltas*. If you're sorted list is 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).
  - danbruc 5y ago
    Only if you naively use the number of bits required for the largest delta for all deltas. If your goal is good compression, you will use a variable length encoding, probably based on the frequency so that it is independent of the magnitude of the deltas. Why should a hundred times one compress any better than a hundred times a million? Arithmetic coding would probably work equally well.
    - ot 5y ago
      "Naively"? Binary packing encoders are still competitive with the state of the art :) Which notably hasn't included variable-length encodings for quite a while. 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.
      - danbruc 5y ago
        So 1000, 1001, 1000, 1002, 1000, 1003, 1000, 1004 requiring 80 bits is good if you could get it to 16 bits plus a Huffman tree which would admittedly eat up the 64 bits difference in this tiny example? Storing the delta is essentially predicting that x[i + 1] = x[i] and storing the difference to that prediction. One could do better by having a better prediction, for example x[i + 1] = x[i] + median_gap_size which would bring the prediction error down to 0, 1, 0, 2, 0, 3, 0, 4 in my example, which could be encoded in 24 fixed length integers plus the median gap size. This could probably be further improved by adaptively predicting the gap size. Making the prediction errors small and independent of the gap size makes the use of short fixed length integers in the common case and switch to longer integers for outliers by reserving one short code as an escape code a much better choice. 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.

by ot 5y ago

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
The outliers the article is talking about here are in the *deltas*. If you're sorted list is 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).
- danbruc 5y ago
  Only if you naively use the number of bits required for the largest delta for all deltas. If your goal is good compression, you will use a variable length encoding, probably based on the frequency so that it is independent of the magnitude of the deltas. Why should a hundred times one compress any better than a hundred times a million? Arithmetic coding would probably work equally well.
  - ot 5y ago
    "Naively"? Binary packing encoders are still competitive with the state of the art :) Which notably hasn't included variable-length encodings for quite a while. 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.
    - danbruc 5y ago
      So 1000, 1001, 1000, 1002, 1000, 1003, 1000, 1004 requiring 80 bits is good if you could get it to 16 bits plus a Huffman tree which would admittedly eat up the 64 bits difference in this tiny example? Storing the delta is essentially predicting that x[i + 1] = x[i] and storing the difference to that prediction. One could do better by having a better prediction, for example x[i + 1] = x[i] + median_gap_size which would bring the prediction error down to 0, 1, 0, 2, 0, 3, 0, 4 in my example, which could be encoded in 24 fixed length integers plus the median gap size. This could probably be further improved by adaptively predicting the gap size. Making the prediction errors small and independent of the gap size makes the use of short fixed length integers in the common case and switch to longer integers for outliers by reserving one short code as an escape code a much better choice. 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.