K-Divided Bloom Filter Algorithm and Its Analysis
Xiaoguang Liu, Jun Lee, Gang Wang, Guangjun Xie, Jing Liu · 2007
By using a bit vector and a set of hash functions to represent data set, bloom filter can query a given data effectively. Bloom filter can be used to determine an element belongs to data set or not. Split bloom filter is amelioration to the bloom filter, which use a S times N bit matrix to represent data set. In distributed systems, if the number of the elements increases continually, the increasing error rate of bloom filter will make the representation nonsensically. Split bloom filter can only weaken this problem. In this paper, a new kind of bloom filter, named as K-divided bloom filter, is presented. Compared with split bloom filter, it can reduce space and time spending and has a resembling or better performance. K-divided bloom filter gets better tradeoff among error rate, space and time.