11
$\begingroup$

A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below).

I am interested in a special application where the number of bits per element $m/n$ is very low, with typically $m<n$ (this results in a very compact set, but of course the price to pay is a lot of false positives).

An issue I run into is that the optimal number of hash functions $k$ is set to be $k^* = \frac m n \log 2$, which is clearly $<1$ when $m<n$. So there is no choice but to use a single hash function, which results in a suboptimal false positive rate of: $$\tilde{p} = 1 - e^{-n/m},$$ instead of the more typical $$p = e^{-m/n (\log 2)^2}.$$

This is suboptimal because the false positive rate is "higher than normal", and it has the effect of predominantly filling the bit vector with ones.

My question is the following: since bloom filters were evidently not designed to be used with such parameters (although technically they still work OK), is there an alternative that would be more efficient ?

Note that I am OK with other limitations of bloom filters (e.g. no deletion possible, false positives, etc.) and that $m/n$ is typically less than $1$ in my case.


Edit: So I came up with some sort of solution, although I still feel there must be something better.

The idea is to have a bloom filter with $k^* = 1$ for a part of the input, and then just output "yes" for any other input. Let's say that you want $m = c n$ with some small $c < 1$.

In the bloom filter (which takes the whole memory space $m$), we have $n_{\text{bf}} = m \log 2 = c n \log 2$, and a probability of false positive of $1/2$ (this is $p = e^{-m/n (\log 2)^2}$ from above instantiated to $k^* = 1$). Indeed, the resulting vector will be on average half ones, half zeroes.

For the rest of the input, that is $n_{\text{rest}} = n - n_{\text{bf}} = n (1 - c \log 2)$, we have a probability of false positive of $1$.

So on average, we have an aggregate $$p_{\text{partial bf}} = c \log(2)/2 + (1-c \log 2) = 1 - c\log(2)/2.$$

This looks better than $\tilde p$ but worse than $p$ (obviously) on (a part of) the area of interest. Here is a graphical comparison.

The rationale behind choosing $k^* = 1$ is that we choose the bloom filter to be as "dense" as we can afford, if that makes sense. A different choice for $k$ leads to worse results (at least for $0 < m < n$).

$\endgroup$
  • 1
    $\begingroup$ Your partial solution at the end is very nice. To elaborate on how to implement it a tiny bit: one way to test whether the input is in the subspace of size $m$ is to build a separate hash function that outputs 'true' on a $c$-fraction of inputs and 'false' on a $1-c$-fraction (e.g., a hash function that outputs a real number in the range $[0,1]$, to $\lg c + O(1)$ bits of precision). If the hash function outputs 'true', then you check the Bloom filter; if the hash function outputs 'false', you just output 'yes'. $\endgroup$ – D.W. Oct 24 '15 at 1:12
  • $\begingroup$ @D.W. Indeed. In fact in my case it is relatively straightforward because the input "universe" is comprised of naturals from 0 to some number $L$, so a simple $x \stackrel{?}{<} (1−c\log2) L$ does the trick. For those you don't even have to do a lookup of course, which is a nice little feature I guess. $\endgroup$ – doc Oct 24 '15 at 1:44
  • $\begingroup$ this analysis is very detailed but wonder about the "big picture" and if some solution may be "outside the box". if "bits per element" is low, just store the actual array, right? what is the thinking/ justification in not doing that? & youve clearly carefully avoided it but think it would be helpful to know more about the app. maybe drop by Computer Science Chat $\endgroup$ – vzn Oct 27 '15 at 21:09
  • $\begingroup$ @vzn The application I'm concerned with is pretty specific, but I still think that it makes sense in some scenarios that just happen to need an extremely compact albeit false-positive-tolerant, set representation. Your suggestion to just store an array would work only if you have enough memory, but here it is the opposite. Maybe the term "bits per element" is confusing. Say you want to have a set of 100 elements each of 32 bits, and only have 80 bits of memory available. Each element is 32 bits long, but is to be stored at a rate of 0.8 "bits per element". $\endgroup$ – doc Oct 27 '15 at 22:39
  • 1
    $\begingroup$ sdarray is may be larger than Bloom filters because it gives you exact answers. However, it doesn't take $O(L)$ space. It's very close to $\log { m \choose L}$ space, which is theoretically optimal for an exact data structure. $\endgroup$ – Pseudonym Nov 18 '15 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.