6
$\begingroup$

I am reading a few papers on Bloom Filters – Bloom Filters in Probabilistic Verification (Dillinger and Manolios) suggests the following allocations for double and triple hashing respectively

$$\begin{align*} f[i] &= a(δ) + ib(δ)\pmod{m}\\ f[i] &= a(δ) + ib(δ) + (c(δ)(i)(i − 1))/2 \pmod{m} \end{align*}$$

Less Hashing Same Performance: Building A Better Bloom Filter (Kirsch and Mitzenmacher) references the former one and suggests similar double hash function with an implementation difference where a double hash instead gives a slot in $g _i$th subarray:

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

It would seem that will mean the memory footprint should be $kp$ – do I understand this correctly? Secondly the paper states that:

The advantage of our simplified setting is that for any two elements x, y ∈ U, exactly one of the following three cases occurs:

  • $g_i (x) \neq g_i (y)$ for all $i$, or
  • $g_i (x) = g_i (y)$ for exactly one $i$, or
  • $g_i (x) = g_i (y)$ for all $i$.

As for as I understand for the above conditions to be fulfilled (I missed this part on my first look through it) - The following specifications must be observed:

$h_1, h_2$ are two independent, uniform random hash functions on the universe with range $0, 1, 2, . . . , p − 1$.

Otherwise partial collisions would occur when $(h_2(x) - h_2(y))*n = m$ (if $m$ is not prime) and at $(h_2(x) - h_2(y)) = p*n$ when the hash function range is at least $2p$.

The standard estimate for minimizing false positivity in a bloom filter is $k = \frac{m}{n}\ ln 2$ - since a set of $k_i$ subarrays can be treated as a continuous space in memory: with each $k$th hash being allocated within the range $ip$ - $(i+1)p$ for the $i$th subarray of size $p$) - the same estimate (I think) should be applicable where $p \approx m/k$.

But usually the hash functions are limited by a few choices which perform optimally given a CPU architecture, this would appear to leave the options severely constrained in the choice of $p$ specifically by the yield of the hash function (32 bits, 64 bits, 128 bits etc.) which dictate that an optimal $p$ is the nearest prime $<$ the range of the hash function.

Given those constraints it would seem like this scheme is optimized for filters of a very specific size - although I was under the general impression that if a good approximation of number of items that need to be stored is known that hash tables demonstrate better performance?

$\endgroup$
  • 1
    $\begingroup$ You have been editing this a lot. While I always appreciate users improving their posts, note that pushing out a huge number of (minor) edits presents some problems; for one thing, you keep pushing your question to the top of the question list. I recommend you prepare your posts more carefully (let them sit for some days!), and/or collect edits until you have a bigger edit together. (See also here, here and here). $\endgroup$ – Raphael Feb 10 '15 at 6:41
  • $\begingroup$ @Raphael Thanks for the criticism, I'll keep the edits together next time. $\endgroup$ – user3467349 Feb 10 '15 at 7:10

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.