Probabilistic Data Structure Showdown: Cuckoo Filters vs. Bloom Filters

Re:Probabilistic Data Structure Showdown: Cuckoo Filters vs.... by taeric on Monday November 28, 2016 @03:09PM (#13057977)

This is just one of the hashes, though. If you consider a function of "color of shirt someone is wearing" to "are they here". Then "color of shirt" is now part of the filter. Same for "is wearing a hat", "is exceptionally tall", etc.

So, if you know that Peter is wearing a green shirt today, then you can rule out his being there if the guard says nobody wearing a green shirt has arrived.

Is this a rigorous model? No. It is just an easy mental model for me to conceptualize this.

[ Parent | on HN ]

Re:Probabilistic Data Structure Showdown: Cuckoo Filters vs.... by Retric on Monday November 28, 2016 @03:33PM (#13058155)

Except the hash format needs to be decided ahead of time. If you ask a guard if they had seen someone with a peg leg they may remember this even without any other instruction.

If you really want to use a range of questions then police codes is a good proxy. The guard may say we have people in the drunk tank, but not anything else.

[ Parent | on HN ]

Re:Probabilistic Data Structure Showdown: Cuckoo Filters vs.... by taeric on Monday November 28, 2016 @05:04PM (#13058820)

Yes, this is why I typically stick with easy and likely to be considered questions.

Again, not a rigorous explanation. Just an easy one. For the advanced algo, I typically word it as imagine if the front desk had a notesheet that they would tick next to "person carrying a backpack" and/or "female" and/or "male" and then I could run my candidate through the questions related to them and see if they all have non-zero quantities of people.

But, again, just a mental way of thinking about this in analogy. If you aren't the kind that needs/wants analogies, this is worthless. On that I fully agree.

[ Parent | on HN ]