4 ms·

Add five "a", now remove four "a" Cuckoo claims there are no "a" in the multiset...

• yeahboats 9y ago
  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.
  • jitans 9y ago
    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
    • bdupras 9y 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 - 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.