2
$\begingroup$

I've been playing around with a simple probabilistic data structure which is very similar to a Bloom filter. Where a Bloom filter would use $k$ independent hash functions to choose $k$ of the $m$ bits to set, this structure uses $m$ hash functions, and sets each bit with probability $p$.

This structure doesn't produce as low a false-positive rate as Bloom filters, but it seems to be extremely fast to compute, particularly if $m$ is some multiple of the machine word size and $p = 2^{-b}$ for some integer $b$: The hash functions can be computed in parallel by AND-ing $b$ independent $m$-bit hashes, and no dependent indexing or variable bitshifts are required.

I'm certain someone's come up with this idea before me, and done a lot more advanced analysis and comparison of it than I'm qualified to do. Is there a particular name for this type of structure?

$\endgroup$
3
$\begingroup$

Let's analyze how many hash bits you need in your new scheme versus a Bloom filter.

First of all, we need to agree about terminology. I will use $q$ to represent the probability of a false positive.

For a Bloom filter the design problem of choosing $m$ and $k$ given that you want to hold $n$ elements with false positive rate $q$ is solved by $k = -\lg_2 q$ as the number of hashes, and $m=\frac{n k}{\ln 2}$ bits for the table. (See the wikipedia page or several of the previous cs.se questions about Bloom filters.) (This works out to a table with maximum entropy: your table is about half 1s and half 0s after $n$ insertions.) The number of hash bits you need to produce per insertion is $k \lg_2 m$

Now your structure: Let's assume that the desired $n$ and $q$ are the same. $k$ and $m$ are going to be about the same, but now $k$ is going to be the average number of bits that remain set after ANDing your $b$ independent $m$-bit hashes. How big does $b$ need to be? Well you want the probability of any particular bit in your final hash to be about $k/m = p = 2^{-b}$. So $b = -\lg_2 k/m = \lg_2 m - \lg_2 k$. But that means that you have to generate $b m = m(\lg_2m-\lg_2k)$ hash bits, which is way more than $k \lg_2 m$. For example, if $n = 709$ and $q = 1/16$ then $k = 4$ and $m = 4096$. So a bloom filter would require $4 \times 12 = 48$ bits of hash, while your scheme requires $b = 10$ and a total of $40960$ bits of hashing.

Worse, there are some elements whose hash works out to 0 (i.e., whenever you look them up the probability of getting a false positive is 100%). Suppose I AND together 10 different bit vectors of length $m$. The probability that each bit will be set to 1 is 1/1024. The probability that all the bits will be set to 0 is $(\frac{1023}{1024})^{4096}\approx e^{-k} \approx 0.0183$.

$\endgroup$
  • $\begingroup$ Thanks, that's very helpful. The amount of hash that needs to be generated does seem to skyrocket relative to Bloom filters. For smaller sets and higher false-positive probabilities the inherent bit-parallelism might produce a win, but the bounds on that seem to be pretty tight. $\endgroup$ – Sneftel Apr 29 '14 at 19:37

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.