15
$\begingroup$

In implementing a Bloom filter, the traditional approach calls for multiple independent hash functions. Kirsch and Mitzenmacher showed that you actually only need two, and can generate the rest as linear combinations thereof.

My question is: what, really, is the difference between two hash functions and one with twice the entropy?

This comes from looking at what you actually do with the output of your hash functions: you're going to take your (say) 64-bit hash value and scale it to the size of your bit vector, which is probably significantly smaller than 264. This is clearly an entropy-losing transformation (except in the rare case your hash size and filter capacity exactly coincide). Assuming my filter has less than 232 entries, what's to stop me from splitting my 64-bit hash value into two 32-bit hashes and taking linear combinations of those? Or using it to seed a PRNG?

In other words, how much information do I actually need to know about each element I insert into a Bloom filter to ensure the standard false positive rate holds? Or more generally, what is the relationship between how well I can distinguish elements (how many bits I use to describe them) and how my Bloom filter performs?

It sure seems like I can get away with $2\lg(m)$ bits for a filter size of $m$, or equivalently $2(\lg(-n\ln{p}) - 2\lg(\ln2))$ bits to store $n$ elements with false positive probability $p$....

$\endgroup$
16
$\begingroup$

You're right to think of hash functions in terms of "random bits produced". So if you have a hash function that produces a 64 bit hash, you can treat is as 4 16-bit hashes (by splitting), and so on.

For the scheme described above (which should be attributed to Dillinger and Manolios; Kirsch/Mitzenmacher just analyzed it), that means you're correct; if you have a single hash function with $2 \lg(m)$ bits, you should be fine.

$\endgroup$
  • 5
    $\begingroup$ Welcome to cstheory, Michael :) $\endgroup$ – Suresh Venkat Apr 14 '12 at 17:45

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.