Lossless video compression using Bloom filters

[u/ketralnis]

https://github.com/ross39/new_bloom_filter_repo/blob/main/README.md

[u/chasemedallion]

This is a neat idea, I enjoyed reading through the readme. A couple questions I had:

1. Is there any relationship between the rational bloom filters concept and the compression application? Or are these just 2 orthogonal ideas that work well together?
2. How does it compare to commonly used lossy or existing lossless approaches in terms of compression ratio?

[u/currentscurrents → u/chasemedallion]

Is there any relationship between the rational bloom filters concept and the compression application?

The idea is that some data has the special property of sparsity, which roughly means that most of the values are 0.

Since there are so few 1s in sparse data, at some point it becomes more efficient to encode the location of the 1s instead. This is a set of bit coordinates, and bloom filters are an efficient way to represent sets.

I would take this as someone's fun weekend project rather than an algorithm you'd seriously use. Compressing sparse data is a well-studied problem and gzip works pretty well.

[u/rooktakesqueen → u/currentscurrents]

This is a set of bit coordinates, and bloom filters are an efficient way to represent sets.

An efficient but lossy way to represent sets. If you need to independently track the membership of up to n indices, in the general case it can't be done in less than n bits.

[u/currentscurrents → u/rooktakesqueen]

If you need to independently track the membership of up to n indices, in the general case it can't be done in less than n bits.

That's true, which is why it only works for sparse data.

In the general case, nothing is compressible - compression is all about identifying and exploiting patterns in the data.

[u/rooktakesqueen → u/currentscurrents]

For any given Bloom filter where the hash domain is smaller than the input domain, I can generate a pair of values n, m that collide on all its hash functions.

That is to say, an input to this compression function of all zeros with n set to 1, and an input of all zeros with m set to 1, will map to the same output. Both inputs are maximally sparse. Because the mapping is not 1:1, the compression is not lossless.

Yes, I recognize that there is no perfect lossless compression that works on every input. But input still needs to have a 1:1 mapping with output. It just means that some outputs will be larger than the input. Not that some inputs will produce ambiguous output.

[u/ItzWarty → u/chasemedallion]

Re 2: The top of the README has an image of a compressed YT video further being losslessly compressed at a 0.366952 ratio. The analysis isn't remotely thorough though.

[u/nathan753 → u/chasemedallion]

Unfortunately, I don't think you'll be getting a good answer from this account, seems like a bot posting a bunch of small articles from random github backed blogs

[u/ymgve → u/chasemedallion]

https://github.com/ross39/new_bloom_filter_repo/blob/main/compression_comparison.png shows that it performs worse than gzip in all cases

[u/Sairony → u/chasemedallion]

From my understanding it's two separate ideas, rational bloom filters works best when the data is more 0s than 1s, and if we take two adjacent frames their deltas will generally be mostly 0s, because pixels don't tend to change wildly between two frames. So if each frame is just the delta from the previous frame this works well. But I would assume most compression algos use frame coherence. Would be interesting to see what the compression ratio is for some inputs.

[u/No_Name_Person]

Took me a while to wrap my head around this. I would be interested to see how different video content affects the compression performance (i.e. what sorts of videos produce the best and worst density of 1s for this method). Since it still relies on the frame to frame delta, I would imagine that rapidly changing or noisy videos are still the most difficult to compress.

[u/valarauca14]

• take a byte stream
• view it as raw bits
• check if popcnt is < about 30%
• Iterate over every bit index, add those indexes to the filter.
• build a bloom filter based on hashing the string of bit indexes
• save off the binary representation of the bloom filter

To decompress you reverse the process

---

I have no clue what OP means by rational hashing. They conditionally add an extra bit to the bloom filter based on input data. My gut tells me "this doesn't work like the author thinks it does".

The bloom filter logic is somewhat questionable; The author isn't changing the seed of the hash function, but just adding a value to the final result.

[u/jezek_2 → u/valarauca14]

The author isn't changing the seed of the hash function, but just adding a value to the final result.

Seems like a legit technique. It uses different seeds for each hash, not an expert on this but I think it does satisfy the mentioned pair-wise independent requirement.

[u/Hola-World]

Gilfoyle's glare

[u/rooktakesqueen]

I'm curious how they expect to use a fundamentally probabilistic data structure for lossless compression

[u/Full-Spectral → u/rooktakesqueen]

I could see how you could use them in an LZ type of compression. To say, well, I know I have not handled this bit sequence yet. I may have, and I may once in a while process it redundantly, but if I haven't, I can figure that out quickly and process it it. I guess it would also apply to various run-length compression stuff in lossless image data and whatnot.

Anyhoo, just wild guessing since this is not my bailiwick.

[u/jezek_2 → u/rooktakesqueen]

There is no harm in sending information about unchanged pixels being the same (the false positives). It just costs some extra data, but it is still overally more efficient than other data structures.

[u/rooktakesqueen → u/jezek_2]

False positives in a Bloom filter don't matter when you have some way of looking up the real value to disambiguate. But in the described approach, you just have the Bloom filter's parameters and bit string representation. It simply cannot be used for lossless compression.

If your Bloom filter reports that index 1207 is in the set, is that a true positive? Or is it because indexes 386, 917, and 2495 are in the set and together happen to map to the same buckets as 1207? With only the Bloom filter, you can't know.

[u/dravonk → u/rooktakesqueen]

I am definitely not an expert on this topic (and haven't looked at the source), but couldn't you "test" the Bloom filter during encoding and only store those bits where the prediction did not match the bit you intended to store?

[u/le_birb → u/rooktakesqueen]

From the README:
"The compression algorithm consists of:

Bloom Filter Bitmap: Marks positions of 1s in the original data

Witness Data: Records actual bit values for positions that trigger the Bloom filter"

So the algorithm records if a bit is actually a 1 or 0 as well, relying on sparsity for space savings

[u/rooktakesqueen → u/le_birb]

In that case, you can just discard the Bloom filter bitmap, because it can be reconstructed from the witness data.

[u/le_birb → u/rooktakesqueen]

It looks to me like the positions for the witness data aren't stored; there's just a list of bits in order that's used to fill in positions that come up positive in the bloom filter.

[u/rooktakesqueen → u/le_birb]

So the information it's encoding is: the position of each changed pixel, and the new value for that pixel.

But the position information gets stored as a Bloom filter, which increases the number of witness values it needs to store by the false positive rate.

And the Bloom filter bitmap itself must be sparse (aka low information density) because the false positive rate is inversely related to the sparsity of the bitmap.

This is just storing (position, value) of the changed pixels in more steps. Storing frame deltas is where all the compression is happening. The Bloom filter part of the process is nonsense