4 ms·
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 extre
by gms7777 14y ago
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
- ajb 14y agoI 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.
- usea 14y agoEven for 0% accuracy?
- gms7777 14y agoIntuitively, I think that might be the case. 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.
- ajb 14y agoThat would be interesting, thanks.