After the Bloom Filter post the other day, I've been doing a dive on probabilistic data structures. This one was obviously on the list along with: skip list, bloom filter, count-min sketch, linear counting, loglog, hyperloglog. Are there any major ones I'm missing, or even better, any lesser known ones I should be aware of? Are there any good resources/courses on this class of data structure/algorithm?
There is also a C++ implementation by the original authors:<p><a href="https://github.com/efficient/cuckoofilter" rel="nofollow">https://github.com/efficient/cuckoofilter</a>
For the uninformed like me, what is the real world application for this? This is 100% curiosity and not criticism.<p>Basically I'm curious in plain English, what kind of application would use this and for what? Also, am I understanding correctly that this is simply a sort of low fidelity hash table?
This is the paper the the readme links to that explains how a Cuckoo filter works: <a href="https://www.cs.cmu.edu/%7Edga/papers/cuckoo-conext2014.pdf" rel="nofollow">https://www.cs.cmu.edu/%7Edga/papers/cuckoo-conext2014.pdf</a>
What is the situation with Patents on the Cuckoo filter? I saw no less than 2 pending applications with some quick googling, one by NetSpeed, one by TI, and quick uspto search shows over a dozen patents.<p>Is the entire useful concept patented at this point?
What I don't understand is comment on the delete function:<p><pre><code> // tries deleting 'bonjour' from filter, may delete another element
// this could occur when another byte slice with the same fingerprint
// as another is 'deleted'
</code></pre>
If it deletes another element, then the guarantee of no false negatives is no longer kept. Is that right?
How does this compare to the implementation in the "BoomFilters" library?<p><a href="https://godoc.org/github.com/tylertreat/BoomFilters#CuckooFilter" rel="nofollow">https://godoc.org/github.com/tylertreat/BoomFilters#CuckooFi...</a>