Hacker News Reader

Comment by Kubuxu | Hacker News Reader

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?

View on HN

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]

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).

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?

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.

Reply on news.ycombinator.com