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?
