This is useful. However, it is larger than a bloom filter, because a bloom filter needs one bit where this stores a value. I suspect that this asymmetry is unavoidable, but I can't prove it. Anyone?
These sorts of filters have limits to accuracy and usefulness (and a definite tradeoff between memory requirements and accuracy). You can take both to the extreme, while still maintaining the definition:
A structure that may report false positives, but no false negatives: A single bit set to 1
A structure that may report false negatives, but no false positives: A single bit set to 0
Obviously that's entirely useless, but I think it shows that you can't make any definitive proof of size requirements
I don't think that shows that you can't make any definitive proof of size requirements. All it shows is that you have to make a statement about the accuracy. For example, it might be possible to prove that for all accuracies, an optimal bloom filter with a particular accuracy will always be smaller than an optimal inverse bloom filter of the same accuracy.
You have to define more specifically what you mean about accuracy here. Accuracy for the bloom filter would be probability of false positives. For the inverse it would be probability of false negatives.
For a bloom filter, if you're targeting a false probability f with n items, you want k = lg(1)/f hash functions, and m = 1.44 k*n bits.
That's the thing though. The bloom filter version scales up easily from the degenerate version (adding more bits increases accuracy). Unless I'm missing something, the inverse bloom filter doesn't scale up from the degenerate version in any natural way.
This will nag at me now. I'm going to need to give this some thought. If I come up with any proof on mem reqs. I'll let you know.
This is a very good point, and one I think the author completely missed.
I use bloom filters in an application at work and was very interested to hear about this, wondering if some sort of hybrid might be useful. But when I saw that the hash map was storing the actual objects, I immediately dismissed the idea for my use case - we can't afford to store anything more than a handful of bits. (Our bloom filters set between 9 and 11 bits per signature.)
The key advantage to bloom filters is that the represent set identity lookups (albeit in an adjustable lossy false-positive way). They do not, however, store actual sets of data. They must be coupled with a storage mechanism (traditionally with a several-order-of-magnitude slower lookup speed than the bloom filter) to actually store the items contained within the set - the bloom filter is just a way of definitively answering the question "Could this set possibly contain this item?"
You'd need to make your claim more precise, in order to prove it, but a proof might go something like this: assume that an anti-bloom filter starts empty, and that it over time sees some small fraction of the possible objects (because objects are 64+ bits, say). If the anti-bloom filter usually reports "yes" for a significant fraction (even just 1%) of the seen objects, then an information theoretic argument tells you it must have size around the number of objects times the object size.
