Bruck, Jehoshua and Gao, Jie and Jiang, Anxiao (Andrew) (2006) Adaptive Bloom filter. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2006.ETR072
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2006.ETR072
A Bloom filter is a simple randomized data structure that answers membership query with no false negative and a small false positive probability. It is an elegant data compression technique for membership information, and has broad applications. In this paper, we generalize the traditional Bloom filter to Adaptive Bloom Filter, which incorporates the information on the query frequencies and the membership likelihood of the elements into its optimal design. It has been widely observed that in many applications, some popular elements are queried much more often than the others. The traditional Bloom filter for data sets with irregular query patterns and non-uniform membership likelihood can be further optimized. We derive the optimal configuration of the Bloom filter with query-frequency and membership-likelihood information, and show that the adapted Bloom filter always outperforms the traditional Bloom filter. Under reasonable frequency models such as the step distribution or the Zipf's distribution, the improvement of the false positive probability of the adaptive Bloom filter over that of the traditional Bloom filter is usually of orders of magnitude.
|Item Type:||Report or Paper (Technical Report)|
|Group:||Parallel and Distributed Systems Group|
|Subject Keywords:||Bloom Filter, Membership Query, Combinatorics|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechPARADISE|
|Deposited On:||24 Jan 2006|
|Last Modified:||26 Dec 2012 13:53|
Repository Staff Only: item control page