The deletable Bloom filter: a new member of the Bloom family
- 3 June 2010
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Communications Letters
- Vol. 14 (6) , 557-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
All Related Versions
This publication has 6 references indexed in Scilit:
- LIPSIN2009
- On the false-positive rate of Bloom filtersInformation Processing Letters, 2008
- Retouched bloom filters2006
- Spectral bloom filters2003
- Summary cache: a scalable wide-area Web cache sharing protocolIEEE/ACM Transactions on Networking, 2000
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970