Deleting in Bloom Filters

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.

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

StackExchange Computer Science Q#19292, answer score: 8