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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.