Title :
The deletable Bloom filter: a new member of the Bloom family
Author :
Rothenberg, Christian Esteve ; Macapuna, Carlos A B ; Verdi, Fábio L. ; Magalhães, Maurício F.
Author_Institution :
Univ. of Campinas (Unicamp), Campinas, Brazil
fDate :
6/1/2010 12:00:00 AM
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.
Keywords :
data structures; set theory; DlBF design; data structure; deletable bloom filter; encoding; false-negative-free deletions; memory consumption; probabilistic filter applications; Costs; Counting circuits; Data structures; Encoding; Hardware; Helium; Information filtering; Information filters; Mathematics; Roads; Bloom filter, deletions, packet forwarding;
Journal_Title :
Communications Letters, IEEE
DOI :
10.1109/LCOMM.2010.06.100344
