Re:Cryptographically Secure Bloom Filters [pdf]
by dllthomas on Tuesday July 23, 2013 @10:09PM
(#6094115)
> It tells you with 100% certainty if the item is NOT in the set, and it tells you with variable certainty if the item MIGHT be in the set.
This wording is hard to understand - particularly the first clause. I assume you grok it, but for anyone confused: it returns either "no" or "maybe". If it returns no, you're 100% confident in that no. If it returns maybe it might be "yes" or "no" so you have to do a more thorough check in another kind of structure. The advantage being that you get that "no" or "maybe" super fast, so much of the time (any time you get a "no") you can stop looking early.
This wording is hard to understand - particularly the first clause. I assume you grok it, but for anyone confused: it returns either "no" or "maybe". If it returns no, you're 100% confident in that no. If it returns maybe it might be "yes" or "no" so you have to do a more thorough check in another kind of structure. The advantage being that you get that "no" or "maybe" super fast, so much of the time (any time you get a "no") you can stop looking early.