A Bloom filter is an array of
M bits which is queried at K quasi-randomly selected positions pk (k < K). If all of the bits are set, then the query returns positive, indicating that someone has already visited the array, setting the bits at all the positions pk.
The filters are quite simple, but the math is a little slippery until you get the right grip on it. Here’s the way I like to grab it, presented in case it helps anyone else.
First of all, the bottom line: Size your Bloom filter to contain NK bits, plus an overhead of 44%. Put another way, for an error rate of ε, allocate lg(1/ε)·lg(e) bits for each key you intend your filter to hold.[Read More]
