cfilter
Languages and libraries
probabilistic data structure library
SHOW HN2016
How HN took it
1 positive, 13 neutral or asking, 0 mixed, 3 critical, out of 17 comments about the project. Thread score -0.15.
Execution: 0 for, 2 againstIdea: 1 for, 0 againstDesign: 0 for, 1 against
The thread, comment by comment
Each row is a top-level comment and its replies, in HN's order. Select a cell to open that comment on HN.
positive neutral or mixed critical about another commenter or something else the maker
What HN said
What people liked
Cuckoo filters offer lower space overhead than Bloom filters and support deletion
From 2 comments
> For applications that store many items and target moderately low false positive rates, cuckoo filters have lower space overhead than space-optimised Bloom filters. Some…
irfansharif on HNThe paper also cites the main advantage of cockoo filters over bloom: ability to remove a key. (Vanilla) bloom require a rebuild of the entire filter if a key is removed from the…
rusanu on HN
Objections
Deleting an item can remove another item with the same fingerprint, causing false negatives
From 2 comments
What I don't understand is comment on the delete function: ``` // tries deleting 'bonjour' from filter, may delete another element // this could occur when another byte slice…
Kubuxu on HNEven if the element is definitely in the filter, another element can have the same fingerprint. Thus, deleting that event which is definitely in the filter will also cause false…
kobigurk on HN
Requests
Allow persisting filter items, since struct fields are unexported
From 1 comment
Can you persist your stored filter items with something like bolt? The struct fields are all unexported.
pram on HN
Compare against BoomFilters cuckoo implementation with benchmarks
From 2 comments
How does this compare to the implementation in the "BoomFilters" library? https://godoc.org/github.com/tylertreat/BoomFilters#CuckooFilter
jzelinskie on HNhadn't come across that implementation before, i'll try putting up benchmarks as soon as i can.
irfansharif on HN
Questions
What real-world applications use cuckoo filters
From 3 comments
For the uninformed like me, what is the real world application for this? This is 100% curiosity and not criticism. Basically I'm curious in plain English, what kind of…
donatj on HNSay you are writing a spider and want to determine whether you have to revisit a website today or tomorrow. The minimal chance of visiting it tomorrow instead of today even if…
allendoerfer on HNHere's one example. Web browsers often use bloom filters or similar data structures to check for malicious URLs. They first check the URL against the local bloom filter, and if a…
sluukkonen on HN
How fingerprints are generated
From 2 comments
How are fingerprint's supposed to be generated? Just another hash?
ejbs2 on HNessentially, yes.
irfansharif on HN
Patent status of the cuckoo filter concept
From 1 comment
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…
Lord_Nightmare on HN
Alternatives named
BoomFilters library CuckooFilter
From 1 comment
How does this compare to the implementation in the "BoomFilters" library? https://godoc.org/github.com/tylertreat/BoomFilters#CuckooFilter
jzelinskie on HN
C++ cuckoofilter by original authors
From 1 comment
There is also a C++ implementation by the original authors: https://github.com/efficient/cuckoofilter
lrem on HN
Bloom filters
From 2 comments
Here's one example. Web browsers often use bloom filters or similar data structures to check for malicious URLs. They first check the URL against the local bloom filter, and if a…
sluukkonen on HNBloom filters are [one of?] the most used 'negative cache' structures. Consulting a bloom filter can give a decisive answer that a key is not in a collection (ie. a key was never…
rusanu on HN