Less Hashing Same Performance: Building A Better Bloom Filter (Kirsch and Mitzenmacher) mentioned that we can use

$ g_i(x) = (h_1 (x)+ih_2 (x))\pmod{p}$, where $h_1(x)$ and $h_2(x)$ are two independent, uniform random hash functions on the universe with range ${0, \dots , p − 1}$, and throughout we assume that $i$ ranges from $0$ to $k − 1$.

However, I notice that if $h_2(x) = 0$, all of the hash function $ g_i(x)$ will be all the same as it will become

$ g_i(x) = h_1 (x)\pmod{p}$

In the case of bloom filter, where there is only one table to update, when $h2(x)=0$, only one location will be inspected. I believe that this will make the accuracy of Bloom Filter for certain value will be worse than other values.

Do we need to have an extra clause to bump the function by $ci$ where $c$ is a constant so that it becomes

$ g_i(x) = (h_1 (x)+ih_2 (x) + ci)\pmod{p} $ ?

  • $\begingroup$ I can't quite make sense of the question. $\endgroup$ – theDoctor Jan 3 '18 at 20:17
  • 1
    $\begingroup$ No. Their analysis specifically takes into account this possibility and shows that the scheme performs well; see, e.g., the sentences in Section 3 beginning "we have arranged that if $g_x(x)=g_i(y)$ for at least two values of $i$, ...". $\endgroup$ – D.W. Jan 4 '18 at 5:50
  • $\begingroup$ Ah, you're right. I missed that paragraph. It makes a lot more sense now. $\endgroup$ – Nat Jan 4 '18 at 6:00

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.