Basket Bloom Filters for Membership Queries
Kun Xie, Yinghua Min, Dafang Zhang, Gaogang Xie, Jigang Wen · 2005
A bloom filter is a space-efficient data structure allowing membership queries over sets with allowable errors. It is widely used in databases, networks, and distributed systems. This paper presents a novel bloom filter, called basket bloom filter (BBF). The BBF deals with different elements in a data set depending on their query invalidation cost, by clustering elements into different baskets. The total query invalidation cost function is defined. In order to minimize the total query invalidation cost, the genetic algorithm is employed to find the optimal number of hash functions for every basket. Simulation results show that, the BBF has 40% lower total query invalidation cost than the standard bloom filters under the same executing time.