The performance analysis of bloom and random filters

Abstract

The Random filter is a well‐known search filter proposed by Wang et al. The authors of the same paper have compared the Random filter with the Bloom filter, proposed by Bloom. Wang et al. have proved the superiority of the Random filter over the Bloom filter in false drop probability and average testing time. In this article, we shall demonstrate that under some reasonable conditions, the performance of the Random filter is not better than Bloom's by mathematical analysis and numerical comparison.

Key words:

• search filter
• Bloom filter
• Random filter
• differential file
• hash

Notes

Correspondence addressee