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?
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
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.
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?"