I want an Approximate Member Query structure (that is, something like Bloom filter), but with the highest possible compression ratio. I know that for AMQs where query is done in constant time, the number of bits taken is proportional to the number of items.

I want to go below that, possibly even below 1 bit per item, or below O(n).

My assumptions are humble. For each key in the set, the AMQ has to return positive. For a key not in the set, the probability of false positive must be at most 50%.

I had one idea. Let's make a normal Bloom filter storing n keys, using only one hash and 2n bits. At most half of the bits will be set, so the probability of false positive is below 50%. Then I thought we could just compress the resulting filter using Huffman encoding. The size of the resulting structure would be O(n) in the number of objects stored, but it could be lower than 2 bits per object.

Question 1.: is there any known lower bound for the size of AMQ for given false positive probability, dropping the assumption that query must be constant time?

Question 2.: Are there any practicals algorithms in use capable of doing that, beyond Bloom filter, quotient filter and cuckoo filter?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.