| | @@ -2251,14 +2251,17 @@ |

2251 | 2251 | integer called the \emph{threshold}. We call these pairs \emph{lambda |

2252 | 2252 | filters}. Define $\mathit{check}((m,\lambda),v)$ to compute the bitwise AND |

2253 | 2253 | of the mask $m$ and vector $v$, count how many bits are set in the result, |

2254 | | -and then return $\mathsf{T}$ if and only if the count is strictly more than |

2255 | | -the threshold $\lambda$. The filter for \texttt{<foo>!?} will consist of a |

2256 | | -mask that selects the three bits for \texttt{foo}, and a threshold of $2$. |

2257 | | -It matches if and only if those three bits are all set, which is definitely |

2258 | | -true for haystacks that match the needle and reasonably unlikely to be true |

2259 | | -for haystacks that do not match the needle. So far this is just the usual |

2260 | | -lookup algorithm for a Bloom filter. But by choosing different masks and |

2261 | | -thresholds, we can also do other kinds of filtering. |

| 2254 | +and then return $\mathsf{T}$ if and only if the count is strictly |

| 2255 | +more\footnote{This definition may seem to be off by one from |

| 2256 | +the most intuitive way to do it, but $\lambda$ is defined this way for |

| 2257 | +consistency with related work in the combinatorial design theory |

| 2258 | +literature.} than the threshold $\lambda$. The filter for \texttt{<foo>!?} |

| 2259 | +will consist of a mask that selects the three bits for \texttt{foo}, and a |

| 2260 | +threshold of $2$. It matches if and only if those three bits are all set, |

| 2261 | +which is definitely true for haystacks that match the needle and reasonably |

| 2262 | +unlikely to be true for haystacks that do not match the needle. So far this |

| 2263 | +is just the usual lookup algorithm for a Bloom filter. But by choosing |

| 2264 | +different masks and thresholds, we can also do other kinds of filtering. |

2262 | 2265 | |

2263 | 2266 | Suppose we have two filters $(m_1,\lambda_1)$ and $(m_2,\lambda_2)$. Let |

2264 | 2267 | $m_3$ be the bitwise OR of $m_1$ and $m_2$, and let $\lambda_3$ be the |