2 ms·

What I don't understand is comment on the delete function: // tries deleting 'bonjour' from filter, may delete another element // this could occur when ano

by Kubuxu 10y ago

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 with the same fingerprint // as another is 'deleted' If it deletes another element, then the guarantee of no false negatives is no longer kept. Is that right?

irfansharif 10y ago
yes, you are correct. drawing from the example in the README you could 'delete' "bounjour" assuming it had the same fingerprint as "buongiorno", subsequent lookups for "buongiorno" would thereby return negatives (assuming it was entered only once). the original research paper makes no explicit guarantees of no false negatives, the invariant can only be maintained if prior to deletion of an element it is ensured that the element is definitely in the filter (e.g., based on records on external storage).
- kobigurk 10y ago
  Even 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 negatives for that other element. Isn't that right?
  - irfansharif 10y ago
    are you assuming the other element is also in the filter? my assumption is your 'deletions' occur only when you know before hand the element already is in the filter. if two elements with the same fingerprints are added to the filter, the finger print is stored two separate times. deletion of any one of them would effectively remove only the single copy thereby not affecting the other (you could be deleting the fingerprint that technically belongs to the other element but it's all the same), so no in this case you do not get false negatives.
rusanu 10y ago
This is basically a hash collision, two keys hash to the same digest. You'd need to add refcount to keep track, same as bloom counting filters [https://en.wikipedia.org/wiki/Bloom_filter#Counting_filters https://en.wikipedia.org/wiki/Bloom_filter#Counting_filters]

by Kubuxu 10y ago

irfansharif 10y ago

yes, you are correct. drawing from the example in the README you could 'delete' "bounjour" assuming it had the same fingerprint as "buongiorno", subsequent lookups for "buongiorno" would thereby return negatives (assuming it was entered only once). the original research paper makes no explicit guarantees of no false negatives, the invariant can only be maintained if prior to deletion of an element it is ensured that the element is definitely in the filter (e.g., based on records on external storage).

kobigurk 10y ago
Even 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 negatives for that other element. Isn't that right?
- irfansharif 10y ago
  are you assuming the other element is also in the filter? my assumption is your 'deletions' occur only when you know before hand the element already is in the filter. if two elements with the same fingerprints are added to the filter, the finger print is stored two separate times. deletion of any one of them would effectively remove only the single copy thereby not affecting the other (you could be deleting the fingerprint that technically belongs to the other element but it's all the same), so no in this case you do not get false negatives.

rusanu 10y ago

This is basically a hash collision, two keys hash to the same digest. You'd need to add refcount to keep track, same as bloom counting filters [https://en.wikipedia.org/wiki/Bloom_filter#Counting_filters https://en.wikipedia.org/wiki/Bloom_filter#Counting_filters]