We introduce the Deletable Bloom filter (DlBF) as a new spin on the popular data structure based on compactly encoding the information of where collisions happen when inserting elements. The DlBF design enables false-negative-free deletions at a fraction of the cost in memory consumption, which turns to be appealing for certain probabilistic filter applications
%0 Journal Article
%1 dlbf
%A Rothenberg, Christian Esteve
%A Macapuna, Carlos
%A Verdi, Fabio
%A Magalhães, Mauricio
%D 2010
%E IEEE,
%J IEEE Communications Letters
%K bloom filter
%N 6
%P 557 - 559
%T The deletable Bloom filter: a new member of the Bloom family
%U http://arxiv.org/abs/1005.0352
%V 14
%X We introduce the Deletable Bloom filter (DlBF) as a new spin on the popular data structure based on compactly encoding the information of where collisions happen when inserting elements. The DlBF design enables false-negative-free deletions at a fraction of the cost in memory consumption, which turns to be appealing for certain probabilistic filter applications
@article{dlbf,
abstract = {We introduce the Deletable Bloom filter (DlBF) as a new spin on the popular data structure based on compactly encoding the information of where collisions happen when inserting elements. The DlBF design enables false-negative-free deletions at a fraction of the cost in memory consumption, which turns to be appealing for certain probabilistic filter applications},
added-at = {2010-06-27T18:53:54.000+0200},
author = {Rothenberg, Christian Esteve and Macapuna, Carlos and Verdi, Fabio and Magalhães, Mauricio},
biburl = {https://www.bibsonomy.org/bibtex/2dfe30b9d852755b3073985147975b985/chesteve},
editor = {IEEE},
interhash = {974ddcca1241be893ec6a1e78c028fbe},
intrahash = {dfe30b9d852755b3073985147975b985},
journal = {IEEE Communications Letters},
keywords = {bloom filter},
month = {June},
number = 6,
pages = {557 - 559},
timestamp = {2010-06-27T18:53:54.000+0200},
title = {The deletable Bloom filter: a new member of the Bloom family},
url = {http://arxiv.org/abs/1005.0352},
volume = 14,
year = 2010
}