A Cascade Hash Design of Bloom Filter for Signature Detection
Zhang Shenghua, Qin Zheng, Yuan Zhao, Xiaolan Peng · 2009
In this paper, we propose an efficient data structure called Cascade Hash Bloom Filter (CHBF) and the corresponding algorithms. In the programming stage of CHBF, the hash results of the first clusters of hash functions in primary Bloom Filter (PBF) will be connected as a mirror image of the inserted signature. This mirror image will be hashed into another bloom filter like array. And in CHBF, it is not necessary to store all the actual signatures. Thus, with the mirror image information we get from the PBF, we are then able to reduce the false positive rate dramatically. We can also reduce the total consumption of memory involved in the membership query. Through theoretical analysis and experiments we show that the Cascade Hash Bloom Filter is significantly efficient for practical purposes than the Extended Bloom Filter and improved Extended Bloom Filter.