Optimizing Data Popularity Conscious Bloom Filters
Ming Zhong, Pin Lu, Kai Shen, and Joel Seiferas
Department of Computer Science, University of Rochester
Bloom filters are compact set representations that support set membership
queries with small, one-sided error probabilities. Standard Bloom filters
are oblivious to object popularity in sets and membership queries. However,
sets and queries in many distributed applications follow known, stable,
highly skewed distributions (e.g., Zipf-like). This paper studies the
problem of minimizing the false-positive probability of a Bloom filter by
adapting the number of hashes used for each data object to its popularity in
sets and membership queries. We model the problem as a constrained nonlinear
integer program and propose two polynomial-time solutions with bounded
approximation ratios --- one is a 2-approximation algorithm with O(N^c)
running time (c>=6 in practice); the other is a (2+e)-approximation
algorithm with running time O(N^2/e), e>0. Here N denotes the total number
of distinct data objects that appear in sets or queries. We quantitatively
evaluate our proposed approach on two distributed applications (cooperative
caching and full-text keyword searching) driven by real-life data traces.
Compared to standard Bloom filters, our data popularity-conscious Bloom
filters achieve up to 24 and 27 times false-positive probability reduction
for the two applications respectively. The quantitative evaluation also
validates our solution's bounded approximation ratio to the optimal.