Computing the approximate population of a bloom filter

Question

Given a bloom filter of size N-bits and K hash functions, of which M-bits (where M <= N) of the filter are set.

Is it possible to approximate the number of elements inserted into the bloom filter?

Simple Example

I've been mulling over the following example, assuming a BF of 100-bits and 5 hash functions where 10-bits are set...

Best case scenario: Assuming the hash functions are really perfect and uniquely map a bit for some X number of values, then given 10-bits have been set we can say that there has only been 2 elements inserted into the BF

Worst case scenario: Assuming the hash functions are bad and consistently map to the same bit (yet unique amongst each other), then we can say 10 elements have been inserted into the BF

The range seems to be [2,10] where abouts in this range is probably determined by the false-positive probability of filter - I'm stuck at this point.

Answer 1

Yes. From Wikipedia:

If you have inserted $i$ elements into a filter of size $n$ using $k$ hash functions, the probability that a certain bit is still 0 is

$$ z = \left(1 - \frac{1}{n}\right)^{ki} $$

You can measure this probability as the proportion of 0 bits in your filter. Solving for $i$ gives

$$ i = \frac{\ln(z)}{k\ln\left(1 - \frac{1}{n}\right)} $$

I have used this in practice, and as long as your filter does not exceed its capacity, the error is generally less than 0.1% for filters up to millions of bits. As the filter exceeds its capacity, the error of course goes up.

Answer 2

If you assume that for each hash function for each object, a bit is set uniformly at random, and you have a count on the number of bits that have been set, you should be able to bound the probability that the number of objects inserted was within a certain range, maybe using a balls and bins formulation. Each bit is a bin, and it's set if it has at least 1 ball in it, each object inserted throws $k$ balls, where $k$ is the number of hash functions, and $nk$ is the number of balls thrown after $n$ objects have been inserted. Given that $b$ bins have at least 1 ball in them, what's the probability that at least $t$ balls were thrown? I think here you can use the fact that: $$P( t \mbox{ balls} | b \mbox{ bins} ) = P(b \mbox{ bins}| t \mbox{ balls}) \cdot P(t)/P(b) $$ But the problem with that formulation is that I don't see a straightforward way to calculate $P(t)$ or $P(b)$, but finding the value of $t$ which maximizes that probability shouldn't be too hard.

Answer 3

Interesting question, lets look at some specific cases.

Let there be $k$ keys, $n_{on}$ bits on, $n_{total}$ bits in total and $m$ elements inserted. We'll first try to find a function $P(k, n_{on}, n_{total}, m)$ which is the probability of a state occurring.

If $km \lt n_{on}$, then $P(k, n_{on}, n_{total}, m)$ must be $0$, ie it's an impossibility.

If $n_{on} = 1$, then we are looking for the probability that $km$ hashes fall in the same bucket, the first one can mark where the others should go. So we want to find the probability that $km - 1$ hashes fall in a specific bucket.

$P(k, 1, n_{total}, m) = (1/n_{total})^{(km-1)}$

That's the really simple cases over. If $n_{on} = 2$ then we want to find the probability that $km$ hashes land in $2$ distinct buckets and at least $1$ falls in each. There are $n_{total}(n_{total} - 1)$ pairs of buckets and the probability that the hashes land in any specific $2$ is $(2/n_{total})^{km}$ so the probability that the hashes fall in up to $2$ buckets is:

$n_{total}(n_{total} - 1)(2/n_{total})^{km}$

We already know the probability that they'll fall in $1$ bucket so let's subtract that to give the probability that they'll fall in exactly $2$.

$P(k, 2, n_{total}, m) = n_{total}(n_{total} - 1)(2/n_{total})^{km} - (1/n_{total})^{(km-1)}$

I think we can generalize this now.

$P(k, n_{on}, n_{total}, m) = {n_{total} \choose n_{on}}(n_{on}/n_{total})^{km} - \sum_{i=1}^{i<n_{on}} P(k, i, n_{total}, m)$

I'm not exactly sure how to make this formula more amenable to computation. Naively implemented, it would result in exponential time execution time, though it's trivial, via memoization, to achieve linear time. It's then just a case of finding the most likely $m$. My instinct says that there will be a single peak so it may be possible to find it very quickly, but naively, you can definitely find the most probably m in $O(n^2)$.

Answer 4

Suppose that hashes are uniformly distributed.

Let $i$ be the number of inserted hashes. Since we have $i$ hashes into $m$ bins if we have $i-1$ hashes into $m$ bins and the next hash goes into one of those $m$ out of $n$ bins OR if we have $i-1$ hashes into $m-1$ bins and the next hash goes into one of the other $n-(m-1)$ bins, we have:

$P(m,i) = P(m,i-1)(m/n) + P(m-1,i-1)(n-(m-1))/n$

Rewriting:

$P(m,i) = \frac{1}{n}(mP(m,i-1) + (n-m+1)P(m-1,i-1))$

We also have $P(0,0) = 1$ and $P(m,0) = 0$ when $m \neq 0$ and $P(0,i) = 0$ when $i \neq 0$. This gives you an $O(mi)$ dynamic programming algorithm for calculating P. Calculating the $i$ that maximizes $P(m,i)$ gives you the maximum likelihood estimate.

If we know that we have hashed into this bloom filter $i$ times and we have $k$ hashes per item, then the number of items is $i/k$.

To speed it up you can do a few things. The factor of $\frac{1}{n}$ can be left out since it doesn't change the position of the maximum. You can share the dynamic programming tables with multiple calls to $P(m,i)$ to reduce the (asymptotic) running time to $O(nm)$. If you're willing to believe that there is a single maximum, you can stop the iteration over $i$ early and get running time $O(jm)$ where $j$ is point where $P$ takes on its maximum, or even do a binary search and get $O(m \log n)$.

Answer 5

The key idea is to approximate the expectation of the number of zero bit.

For each bit, the possibility of being zero after t insertions with K hash functions is: $(1-\frac{1}{N})^{Kt} \approx e^{-\frac{Kt}{N}}$.

Then the expectation of zero bit numbers should be:

$N e^{-\frac{Kt}{N}}$ approximated by the observation $N - M$

Finally we got $t = - \frac{N}{K} ln(1-\frac{M}{N})$

Answer 6

Probability that a particular bit is 1 after n insertions is: P = 1 - (1 - 1/m) ^ (kn)

Let X_i be a discrete random variable which is 1 if the bit at i'th position is 1 and 0 otherwise. Let X = X_1 + X_2 + .... + X_m. Then, E[X] = m * P.

If total number of set bits are S, then: E[X] = S which implies m * P = S. This could be solved for n.