On the deletable bloom filter

Hyesook Lim, Jungwon Lee, Changhoon Yim

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


The deletable Bloom filter (DBF) enables false negative–free deletions that are not possible in a standard Bloom filter or in a counting Bloom filter. The DBF is expected to be applied to many Bloom filter applications that require delete operations. Hence, the characteristics and the performance of the DBF should be studied further, as well as the error in the DBF. The first contribution of this paper is to provide the correct probability for the element being deletable in the DBF. The second contribution is to discuss the tradeoff between two important performance metrics (false positive probability and deletability probability), and to propose a cost function combining them. The third contribution is to provide a mathematical analysis of the false positive probability related to deletion rates. We also provide a comparison of the false positive probability between the analytical results and the simulation results as the deletion rate increases.

Original languageEnglish
Pages (from-to)489-495
Number of pages7
JournalIEIE Transactions on Smart Processing and Computing
Issue number6
StatePublished - Dec 2018

Bibliographical note

Funding Information:
This research was supported by National Research Foundation of Korea grants funded by the Korean Government (Ministry of Science and ICT) - 2017R1A2B4 011254 (for H. Lim), 2018R1A6 A3A11040736 (for J. Lee), and 2016R1A2B1008349 (for C. Yim).

Publisher Copyright:
© 2018 Institute of Electronics and Information Engineers. All Rights Reserved.


  • Bloom filter
  • Deletable bloom filter
  • Deletion rate
  • Element deletion
  • False positive rate


Dive into the research topics of 'On the deletable bloom filter'. Together they form a unique fingerprint.

Cite this