In the first article in this series, we introduced Filters for Probabilistic Searches, and their operations. Here we'll start with Bloom Filters, the first implementation to consider.
Bloom Filters
The first implementation we'll look at is a Bloom Filter (BF). The name has nothing to do with flowers or how the filter behaves; the "Bloom" part comes from Burton H. Bloom, a computer scientist who introduced the structure in a 1970 paper published in Communications of the ACM, "Space/Time Trade-offs in Hash Coding with Allowable Errors".
Interestingly, the structure was a relatively obscure theoretical curiosity for decades before becoming widely used several decades later, when memory-constrained, large-scale systems needed exactly the space/accuracy trade-off Bloom described.
The core idea is to use a bit array and several independent hash functions to record a "fingerprint" of added items. Basically, how you add an item is:
- Let the bit array size be b, and the number of hash functions be h. Each hash function maps its input to one of the b positions.
- Apply the hash functions to the input, producing h positions for the array. (Yes, some of the h values may be repeated, but ignore this for the moment.)
- Set the bit at each of those positions to 1.
Let's see an example. Say b=10 and h=3, and we want to add three of the Marx brothers, GROUCHO, HARPO, and CHICO, to the filter.
- Applying the three hashes to GROUCHO may produce 2, 7, and 4; we set the corresponding bits to 1.
- Suppose applying the hashes to HARPO produces 6, 5, and 2; we now have bits 2, 4, 5, 6, and 7 set. Note that bit 2 was already set; it stays that way.
- Applying hashes to CHICO produces 1, 9, and 6; we have bits 1, 2, 4, 5, 6, 7, and 9 set.
See the following figure for a summary of the three additions; dotted gray lines show bits set more than once.
Figure 11½–2: Three additions to a Bloom Filter
Now for the interesting part: how do we search for a string? The way to do a search is:
- Apply the hash functions to the input you want to find, producing h bit positions.
- Check those positions: if any of them (at least one) is not set, the input is definitely NOT in the structure.
- If all are set, the input may be in the structure-but it could be a false positive!
Let's see some examples. We want to check ZEPPO, CHICO, and GUMMO. First, when we search for ZEPPO, assume the hash functions produce 3, 7, and 8. Since at least one of those bits is 0, we can assert that ZEPPO was never added and is not present. The figure below shows the search, with dotted gray lines indicating the unset bits found. Practically, you wouldn't continue checking after finding the first unset bit; a single 0 is enough to declare the search failed.
Figure 11½–3: A failed search; one unset bit is enough.
Now let's see some possibly successful searches. When we search for CHICO, the hashes produce 1, 9, and 6, and all those bits are set to 1. Suppose that when we search for GUMMO, suppose the hash functions produce 1, 2, and 4; again, all those bits are set to 1. We cannot definitely say the searches were successful; in one case (CHICO) the bits were set because we had added that value, but in the other case (GUMMO) other values had set the bits.
Figure 11½–4: Both searches find all bits set, but only one value was actually added.
We now know how to use a filter; we need to decide how to size it before we can write the code for additions and searches.
Sizing a Bloom Filter
As we mentioned in the previous section, to appropriately size a BF, you must know n, how many elements to insert, and the false-positive rate, ε, and you'll decide how many bits to use (b) and how many hash functions are needed (h). By the way, ε is usually set at 0.01, 1%, or much less. The lower the value, the fewer the false positives.
Let's do some math; if you wish, skip ahead! If you insert one element, each of the h functions sets a bit. The probability that any insertion does not hit a particular bit is 1‑1/b, so after n insertions with h hashes each, the probability that the bit is still not set would be (1‑1/b)^hn. For large b, this is approximately e^(‑hn/b). You get a false positive if you search for a value that was never inserted, but all the corresponding h bits happen to be set. This false-positive probability is (1‑e^(‑hn/b))^h, and from this result we'll get the sizes we need.
Let's find how many hashes we need. Fixing b and n, the formula depends only on h, and is optimized when h is (b/n) ln(2). Substituting this value into the false-positive formula and simplifying eventually produces 2^(‑(b ln(2)/n)). Equating this to ε, b should be ‑(n ln(ε))/ln²(2). At this point, we have everything we need to start writing code; let's get to it.
Bye for now! In the next article in the series, we will see how to implement the Bloom Filters we described here, with full JavaScript code for all algorithms.
Top comments (0)