An Improved Less Hashing Bloom Filter. (November 2020) - Yu, Kuai; Qi, Deyu; Zhang, Changjian
Abstract: Bloom filter is a useful data structure, which is often used in the membership query with allowing errors. However, high computational cost of the hash functions limits the performance of the Bloom filter. In this paper, we propose a new Bloom filter based on a single hash function named No-partition Single-hashing Bloom filter (NPSHBF). Compared with the Standard Bloom filter (SBF), we theoretically prove that the false positive probability of NPSHBF is approximately equal to SBF. At the same time, we theoretically prove that the processes of modulo are independent to each other, which greatly improves the querying performance of the Bloom filter. After theoretical verification, we can see from a series of experimental results that the false positive probability of NPSHBF is consistent with the theoretical speculation, and the querying efficiency and generating efficiency of NPSHBF are much higher than SBF.