6
$\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$
  • $\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
  • $\begingroup$ @Ziva I think it's a folklore. There is a nice idea, but not very innovative. $\endgroup$ – Gari BN Jan 2 '14 at 15:45
  • $\begingroup$ Yeah, maybe you are right $\endgroup$ – Zix Jan 2 '14 at 18:40

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.