Bloom filter variant

Question

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?

Answer 1

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