CaltechAUTHORS
  A Caltech Library Service

Adaptive Bloom filter

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

[img]
Preview
PDF
See Usage Policy.

1818Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2006.ETR072

Abstract

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)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr072.pdfPublisherUNSPECIFIED
Group:Parallel and Distributed Systems Group
Subject Keywords:Bloom Filter, Membership Query, Combinatorics
Record Number:CaltechPARADISE:2006.ETR072
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:2006.ETR072
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26103
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:24 Jan 2006
Last Modified:26 Dec 2012 13:53

Repository Staff Only: item control page