News for hackers. Stuff that matters.
Re:Probabilistic Filters By Example by yeahboats on Wednesday March 28, 2018 @06:24PM (#16702589)
There is a comment elsewhere from the creator I think that explains this. The 5th "a" never gets added, you'll see that the cells turn red. After you remove 4 "a"s then you're back at 0 and it is correctly reporting that there aren't any.
Re:Probabilistic Filters By Example by jitans on Wednesday March 28, 2018 @06:31PM (#16702632)
well the demo then is broken indeed it shows still an "a" inside the multiset. Having say that I would never use a cuckoo in a multiset, indeed it becomes a bounded multiset. Also about the K-hashing for a bloom filter is not exact. You just need need a K-bit hashing function. If the goal is to support deletion then I would go for a Counting Bloom filter
Re:Probabilistic Filters By Example by bdupras on Friday March 30, 2018 @09:14AM (#16715773)
Yeah you're correct in saying that the demo is broken - sorry for the confusion, I stopped working on this when it was good enough for an internal talk at my company.

Re multisets, yes cuckoo filters and counting blooms are bounded - cuckoos by entries or bucket x 2, and blooms by bits per counter. Cuckoo's counting capability is more a side effect of the design. It's really only interesting in that you get limited counting in roughly the same bit space as a non-counting bloom. I suppose you could add counting bits to a cuckoo to support higher bounds in a similar manner to counting blooms.

I'm curious to hear more on your point on K-hashing in bloom filters - would you expand on your statement about only needing a K-bit hashing function? I'm happy to update the text on the tutorial to be more clear/exact.