Advertisement
Published in:
2015 | OriginalPaper | Chapter
Improved Weighted Bloom Filter and Space Lower Bound Analysis of Algorithms for Approximated Membership Querying
Authors : Xiujun Wang, Yusheng Ji, Zhe Dang, Xiao Zheng, Baohua Zhao
Published in: Database Systems for Advanced Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The elements in a large universe
$$U$$
have different membership likelihoods and query frequencies in many applications. Thus, the number of hash functions assigned to each element of
$$U$$
in the traditional Bloom filter can be further optimized to minimize the average false positive rate. We propose an improved weighted Bloom filter (IWBF) that assigns an optimal number of hash functions to each element and has a less average false positive rate compared to the weighted Bloom filter. We show a tight space lower bound for any approximated membership querying algorithm that represents a small subset
$$S$$
of
$$U$$
and answers membership queries with predefined false positive rates, when the query frequencies and membership likelihoods of the elements in
$$U$$
are known. We also provide an approximate space lower bound for approximated membership querying algorithms that have an average false positive rate, and show that the number of bits used in IWBF is within a factor of
$$1.44$$
of the approximate space lower bound.