12
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Why not keep a counter of the number of elements inserted? It only takes an additional $O(\log n)$ bits, if you inserted $n$ elements. $\endgroup$ – Joe Feb 3 '12 at 23:33
  • $\begingroup$ @Joe, whilst that is a good idea, it does ruin a really interesting question. $\endgroup$ – dan_waterworth Feb 17 '12 at 16:28
  • $\begingroup$ Just noting that with duplicates, Joe's method will have some small error since we can't always tell for sure when adding an element whether it is already present (and hence should we increment the count or not). $\endgroup$ – usul Apr 3 '15 at 21:28
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ I think your formula cancels out to ${n_{total} \choose n_{on}}n_{on}^{km}- {n_{total} \choose n_{on}-1}(n_{on}-1)^{km}$ (ignoring constant factors). You can compute the maximum of this analytically: expand the first factor of the second term and remove constant factors to get rid of all n choose k, and then your formula becomes very simple. $\endgroup$ – Jules Feb 17 '12 at 12:57
  • $\begingroup$ @Jules, great, I was sure something like that would happen, but didn't have the time to figure it out. $\endgroup$ – dan_waterworth Feb 17 '12 at 16:12
  • $\begingroup$ You can also arrive at that formula directly in the following way: $P(n_{on} = x) = P(n_{on} \leq x) - P(n_{on} < x) = P(n_{on} \leq x) - P(n_{on} \leq x-1)$. Then plug in ${n_{total} \choose x} (x/n_{total})^{km}$ for $P(n_{on} \leq x)$. $\endgroup$ – Jules Feb 18 '12 at 0:24
2
$\begingroup$

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)$.

$\endgroup$
2
$\begingroup$

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})$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.