Show HN: Cuckoo Filter Implementation in Go, Better Than Bloom Filters

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:&#x2F;&#x2F;github.com&#x2F;efficient&#x2F;cuckoofilter" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;efficient&#x2F;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&#x27;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:&#x2F;&#x2F;www.cs.cmu.edu&#x2F;%7Edga&#x2F;papers&#x2F;cuckoo-conext2014.pdf" rel="nofollow">https:&#x2F;&#x2F;www.cs.cmu.edu&#x2F;%7Edga&#x2F;papers&#x2F;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&#x27;t understand is comment on the delete function:<p><pre><code> &#x2F;&#x2F; tries deleting &#x27;bonjour&#x27; from filter, may delete another element &#x2F;&#x2F; this could occur when another byte slice with the same fingerprint &#x2F;&#x2F; as another is &#x27;deleted&#x27; </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 &quot;BoomFilters&quot; library?<p><a href="https:&#x2F;&#x2F;godoc.org&#x2F;github.com&#x2F;tylertreat&#x2F;BoomFilters#CuckooFilter" rel="nofollow">https:&#x2F;&#x2F;godoc.org&#x2F;github.com&#x2F;tylertreat&#x2F;BoomFilters#CuckooFi...</a>

Can you persist your stored filter items with something like bolt? The struct fields are all unexported.

How are fingerprint&#x27;s supposed to be generated? Just another hash?