15 fix typo on the research paper topic
source | link

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 BetterSame 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?

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 Better 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?

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?

14 added 102 characters in body
source | link

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

NeverthelessGiven 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?

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

Nevertheless 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?

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 Better 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?

13 added 42 characters in body
source | link

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 Better 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 this will increasemean the memory footprint toshould be $km$$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 - and actually I should be only partially to blame since the implementation I was looking at neglects to use a prime) - they specify thatThe 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$.

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

Nevertheless 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?

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 Better 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 this will increase the memory footprint to $km$ – 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 - and actually I should be only partially to blame since the implementation I was looking at neglects to use a prime) - they specify that:

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

Taking into account CPU architecture limitations of a given system, this would appear to leave the options severely constrained in the choice of $p$ specifically by the yield of the hash function (most probably 32 bits, 64 bits, 128 bits etc.) which dictate that an optimal $p$ is the nearest prime $<$ the range of the hash function.

Nevertheless 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?

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

Nevertheless 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?

12 added 158 characters in body
source | link
11 added 158 characters in body
source | link
10 added 472 characters in body
source | link
9 added 472 characters in body
source | link
    Post Undeleted by user3467349
    Post Deleted by user3467349
8 added 97 characters in body
source | link
7 added 6 characters in body
source | link
    Tweeted twitter.com/#!/StackCompSci/status/564466756040024065
6 edited tags
| link
5 added 1 character in body
source | link
4 Typesetting and tags
source | link
3 added 3 characters in body
source | link
2 added 26 characters in body
source | link
1
source | link