Bloom Filters by Example

Re:Bloom Filters by Example by nandemo on Tuesday July 11, 2017 @02:50AM (#14742092)

If I was going to explain a bloom filter like you're 5... a bloom filter is like a savant who never forgets a face -- maybe he's got a job in passport control in Arstotzka -- if you show him someone's face or picture once, he'll never forget it: if any time later you show him the same picture and ask him "have you seen this face before?" he'll say "yes" without fail. If he replies "no way", you can be 100% sure he's never seen it. But his memory isn't photographic: he confuses people's faces after a while, recognizing faces he's never seen, and that becomes worse the more people he's seen. So to be safe he doesn't reply just "yes" but "hmm, I guess so".

In computing terms the interface has 2 methods:

- takeALookAtThisFace(x)

- yaSeenThisFaceBefore?(x) which returns either "no way" or "hmm, I guess so".

"no way" means P(x is a member) = 0. Its negation is not "hell yes" (P(x is a member) = 1), it's "maybe" (P(x is a member) > 0).

[ Parent | on HN ]

Re:Bloom Filters by Example by meenzu on Tuesday July 11, 2017 @05:55AM (#14742811)

Thanks for this explanation it was really helpful!

[ Parent | on HN ]

Re:Bloom Filters by Example by nandemo on Tuesday July 11, 2017 @07:04AM (#14743112)

Glad to help. But I noticed the analogy is a bit flawed; testing for membership does not add anything to the set, but the analogy might imply asking yaSeenThisFaceBefore(x) will make the savant remember x. I should change the story and the 2 functions to "remember this terrorist" and "is this a terrorist?" or something like that.

[ Parent | on HN ]