DocumentCode
1505374
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
Volume
14
Issue
6
fYear
2010
fDate
6/1/2010 12:00:00 AM
Firstpage
557
Lastpage
559
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;
fLanguage
English
Journal_Title
Communications Letters, IEEE
Publisher
ieee
ISSN
1089-7798
Type
jour
DOI
10.1109/LCOMM.2010.06.100344
Filename
5474942
Link To Document