On the deletable bloom filter

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.