On the deletable bloom filter

Hyesook Lim, Jungwon Lee, Changhoon Yim

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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
Volume7
Issue number6
DOIs
StatePublished - Dec 2018

Keywords

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

Fingerprint

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

Cite this