Observation: bitstream with low density of 1s (< p=0.32) can be encoded more efficiently by positions of the ones. We store those positions into a set implemented using bloom filter. We can calculate the theoretically optimal parameters for bloom filter to maximize compression. With a bloomfilter bitmap plus a data structure for recovering info in case of false positive we can achieve lossless compression. To decompress, we iterate through all possible positions, set the bit to one by querying set membership of the location.

To compress video, the author encodes the difference between video frames as a bitstream of mostly one, which then gets compressed with bloom filter.

Another innovation is rational bloom filter - the number of optimal hash functions is usually not integer. Typical implementation just round the number to an integer and use that. The author proposed to use ⌊k⌋ hash functions deterministically and with k-⌊k⌋ probability applying an additional hash. The probability is applied deterministically based on the value.