An Improved Less Hashing Bloom Filter. (November 2020)

• Record Type: Journal Article
• Authors: Yu, Kuai; Qi, Deyu; Zhang, Changjian
• Is Part Of: Journal of physics. Volume 1684(2020)
• Publication Date: 2020-11
• Subjects: Physics -- Congresses; 530.5
• DOI: 10.1088/1742-6596/1684/1/012145
• Languages: English
• ISSNs: 1742-6588

Abstract

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.