10
$\begingroup$

I know that standard Bloom Filters only have operations like inserting elements and checking if an element belongs to filter, but are also some modification of Bloom filters which enable a delete operation--for example: counting Bloom filters. I heard also about another method, which uses a second filter. If I want to remove an element I have to 'insert' it into this second filter. I can't find how this proposed structure operates, any article about it, or even the name of the originator. Maybe someone can share with me with a link to any interesting articles about this method? I found a lot of articles about counting Bloom filters and other methods, but I can't find any description of this one.

$\endgroup$
7
$\begingroup$

I couldn't find the source, but the idea is simple: Use additional bloom filter to represent the set of the deletions.

As this is a very simple solution, it might be considered as a folklore.

Anyway, I found a short reference to this solution in the following paper (Theory and Practice of Bloom Filters for Distributed Systems):

http://www.dca.fee.unicamp.br/~chesteve/pubs/bloom-filter-ieee-survey-preprint.pdf

Search for:

Removal of an element can be implemented by using a second Bloom filter that contains elements that have been removed

In the third section of this paper, you can read about many techniques to deal with deletion. Maybe you will find there some reference (again - I'm not sure there is some paper about it, as it is a simple idea).

$\endgroup$
7
  • $\begingroup$ I know how works the idea with using second filter, but I looking for some articles or papers which describe this. But thanks for your suggestions. $\endgroup$
    – Zix
    Dec 26 '13 at 12:26
  • $\begingroup$ @Ziva I wonder if you found such a paper. If you did - please publish some link. $\endgroup$
    – Gari BN
    Dec 30 '13 at 18:33
  • $\begingroup$ Unfortunately, I did't find such a paper. $\endgroup$
    – Zix
    Jan 2 '14 at 13:31
  • 10
    $\begingroup$ I have to say it: This idea does not work. That is why there is no paper about it! in the awesome document linked, it says this definitively: "Removal of an element can be implemented by using a second Bloom filter that contains elements that have been removed. The problem of this approach is that the false positives of the second filter result in false negatives in the composite filter, which is undesirable." $\endgroup$ Apr 10 '18 at 15:37
  • 1
    $\begingroup$ Seconding that this does not work. In particular, say you add(x) to H1, then remove(x) (by putting x in some H2 representing the set of deletions), and then add(x) again? Now you have the exact same problem -- removing x from H2. It's not feasible to create some H3 to represent the set of deletions from H2 with no bound on how many times some element may be removed and re-added. $\endgroup$
    – Matthew C
    Aug 2 '20 at 15:19
3
$\begingroup$

Depending on your intended use, it might not be practical to use counters, e.g. integers instead of bits, but by doing so, you can increment each integer in the array instead of setting a bit when inserting. When removing an element, you can then decrement all of its related integers.

$\endgroup$
3
  • $\begingroup$ But how can you safely remove an element and decrement the related integers if you are not sure whether the element was ever added to the bloom filter before? Consider the set {a, b, c}, all added to a bloom filter B. If I try to remove d from B even before adding it, I may corrupt the bloom filter because I may inevitably decrement an integer incremented by another element (a, b or c). How can I be sure that when I remove d, I know that d has to be removed because I know that it was added before and not that d is "possibly in" B? Thank you! $\endgroup$
    – tonix
    Jul 22 at 23:29
  • 1
    $\begingroup$ That is correct. With that method, removing an element that was not already added will corrupt the filter. Some times the use case ensures that elements are always added before removal. If not, you can use the Bloom filter itself to check whether the element might have been added (which includes false positives), before verifying the element was added using a more expensive method without false positives. $\endgroup$ Jul 26 at 13:20
  • $\begingroup$ Thank you for the clarification. $\endgroup$
    – tonix
    Jul 27 at 22:00
0
$\begingroup$

You can use the concept of invertible bloom filters. See here for a nice explanation. Invertible bloom filters allow you to retrieve and delete key/value pairs from the filter.

$\endgroup$
1
  • $\begingroup$ Could you explain it in your own words or quote appropriate parts? Posts should be self-contained, links tend to rot. Thank you. $\endgroup$
    – Evil
    Oct 11 '20 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.