3
$\begingroup$

The Bloom filter data structure requires a set of hashing functions. The Murmur3 family is a great fit, as it contains the seed parameter to easily create a variety of different functions (plus it has good distribution of values and adequate speed).

Choosing the seed

Is there any particular method of choosing the seed values for the Bloom filter application? By selecting them randomly, I give up the deterministic nature of the algorithm and hand-picking these values seems a little bit too brave. Is it known, whether two seed values s1 and s2, where s1 != s2, yield the same function (borrowing a linear algebra term: they would be linearly dependent) ?

Limiting the hash domain

The Murmur3 hash is a 32-bit value. Since the Bloom filter might not need all 32 bits, is it still OK with respect to the uniformity to just apply the modulo function to this value?

$\endgroup$
4
$\begingroup$

You have asked two questions. I will answer them one by one.

Choosing the seed. The usual approach here is to choose the seeds randomly once and for all, and to hard-code them. If the hash family is reasonable, then all small sets of seeds should look "the same". I don't know the Murmur3 family, but it's probably reasonable enough.

Note that linear dependence is not the correct measure here — you want a $k$-tuple of hash values generated from $k$ different seeds to look like a random $k$-tuple of values, either statistically or computationally. Linear dependence is just one possible wrong thing that could happen.

Limiting the hash domain. If the modulus isn't a power of 2 then the resulting value wouldn't be uniform, but usually it will be "close enough" to uniform, particular with respect to the performance of a Bloom filter. Indeed, it is standard practice to generate a random number in a range $\{0,\ldots,m-1\}$ by taking a random 32-bit or 64-bit value modulo $m$.

In the specific case of Bloom filters, if you know that every value in $\{0,\ldots,m-1\}$ appears with probability in the range $[c/m,C/m]$ then you can adjust the analysis of the Bloom filter to see what you get. You can then calculate $c,C$ in your case (exercise) and choose parameters for the Bloom filter accordingly. You will probably find out that in most cases the parameters you get by assuming $c=C=1$ are very close to the ones that you get by taking into account the actual $c,C$.

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