bdupras

6 ms·

1.
by bdupras 8y ago
Yes, cuckoo filters and counting bloom filters can start rejecting insertions before the filter is loaded - cuckoos because of the inability to find an open slot, and counting blooms because of saturation of a counter. Note that this is onl
2.
by bdupras 8y ago
chronolitus did jetrink's comment answer your question? I'm happy to further clarify if needed.
3.
by bdupras 8y ago
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 - c
4.
by bdupras 8y ago
Yeah - pardon the crappy javascript and UX. Notice the colors on the cuckoo filter when you insert this sequence. When you try to insert `3g46stb6vy6vsyosyvosfsdfsdsah`, the fingerprint entries in the cuckoo turn red indicating an unsuccess
5.
by bdupras 8y ago
A few types of filters support deletion (e.g. counting bloom filters and cuckoo filters). To my knowledge all of them require prior knowledge that an entry was successfully inserted. That is, if you guess at deleting an entry and are succes
6.
by bdupras 10y ago
Yeah, absolutely. You get the same "feature" from Counting Blooms - i.e. if an insertion would overflow any of the counters, the filter can knowingly reject the insertion. This is both a feature and a limitation. In our use case,
7.
by bdupras 10y ago
Regarding the second point on deletions, the cool thing about the work by Bin Fan with the Cuckoo filter is that you get the added benefit of deletion in almost the exact memory footprint as a standard Bloom. This was the critical feature t
8.
by bdupras 10y ago
To further clarify, if a Bloom filter query is O(K) where k is the number of hash functions, then when k=7, the filter could be described as O(1). The constant factors here are important for practical use. Hashing 7 times is significantly d
9.
by bdupras 10y ago
It isn't clear in the demo visualization, but insertions into the Cuckoo filter do get rejected after exhausting a maximum number of kick/relocation attempts. If I find some time I'll make that more apparent. As for false neg
10.
by bdupras 10y ago
Guilty. I wanted to be up-front about the constant factor of 1 or 2. I was tired when I wrote that and was actually looking at cleaning that up a couple days ago, but got distracted. Soon.