Bloom Filters
It turns out that even though a classic bit vector can’t store strings compactly, a similar data structure called a Bloom filter can. The Bloom filter, named after its inventor, Burton Bloom, has been put to widespread use in all sorts of applications ever since the 1970s.
A Bloom filter is a space-efficient data structure used for storing a set. It’s a variation of the bit vector, but can be used to store all sorts of data, not only a small range of integers. To make this work, Bloom filters make use of Monte Carlo principles, as you’ll soon see.
To make it a tad easier to understand how Bloom filters work, I’m going to first introduce a similar but simpler data structure, which I call the Gloom filter. Please don’t ever use a Gloom filter. I made it up for educational purposes only; it’s not a real thing.
Gloom Filters
The Gloom filter utilizes hashing so that we can store strings inside bit vectors—or at least, kind of.
As you learned in Chapter 10, , we can use a hash function, such as division hashing, to transform a string into an integer. Suppose we choose a hash function that produces hash codes that are integers from 0 to 7. Armed with such a hash function, we can store any string inside a byte-sized (8 bits) bit vector, as shown in the .
Because the hash code of "apple" is 4, we flip the bit at index 4 to 1.
Similarly, we can also add "banana" to our Gloom filter:
Our Gloom filter now contains both "apple" and "banana".
And that, my friends, is the Gloom filter. In short, it uses a hash function to transform each value into an integer, and then sets the corresponding index in a bit vector to 1. It’s basically a bit vector, except that we first hash each value to decide which bit we should store it in.
Okay, that seems pretty cool. Let’s analyze what we can and cannot accomplish with a Gloom filter.
One-Directional
If we had a Gloom filter and wanted to know what values it contains, we’d have absolutely no way to do that. The 1 bits in the byte 00010100 could represent anything. They could represent any string that hashes into 2 or 4. A bit vector, on the other hand, only stores integers, and so 00010100 can only represent the integers 2 and 4. As such, we can always draw out the integer values from the bit vector.
However, the fact that Gloom filters are one-directional doesn’t mean that they can’t be useful. Take the finding duplicates problem, for example. We never need to pull values out of the set; we only need the set to tell us if we’ve encountered a value before. So, if the Gloom filter returns True when we ask it if we’ve encountered "apple" before, we’ll know that we’ve found a duplicate.
But there’s a pretty big problem with this.
Collisions
As I covered in Volume 1, Chapter 8, and touched on in Chapter 10, , hashing can lead to collisions. That is, multiple values can all be hashed into the same hash code. This presented a potential problem for hash tables, but we were able to deal with collisions by using approaches such as separate chaining, which I discussed in Volume 1, Chapter 8.
However, collisions can derail Gloom filters since collisions cause false positives. To see what this means in our context, let’s continue with the example of finding duplicates.
In the previous Gloom filter example, we encountered and stored the strings "apple" and "banana" in our Gloom filter, giving us the byte 00010100. Cool.
Say that the next item in our array is "cucumber" and that "cucumber" hashes to 4. When we check our Gloom filter to see whether we’ve encountered "cucumber" before, we’ll find that there’s a 1 bit at index 4, and our code will tell us that we’ve already encountered "cucumber" before. In truth, though, this 1 bit was placed there because of "apple", which happens to hash to the same value. At this point, our program will happily shut down and tell us that we found a duplicate—but we haven’t!
This is what I mean by a false positive; the computer thinks it found a duplicate since it’s confusing "cucumber" with "apple", as they have the same hash codes. In any case, this problem of false positives is, well, problematic, as it means that a Gloom filter cannot help us detect duplicates properly.
No False Negatives
Now, I’d like to point out that even though Gloom filters suffer from false positives, it doesn’t mean that Gloom filters are utterly useless. In particular, here’s one thing that Gloom filters have going for them: they don’t produce false negatives.
That is, if a Gloom filter declares that a value does not exist in the set, then the Gloom filter is 100 percent trustworthy. The reason for this is logical. A Gloom filter states that a value is nonexistent when the value’s hash code corresponds to an index with a 0 bit. If the value was seen before, that index would definitely contain a 1 bit. If there’s a 0 bit, we can be guaranteed that we’ve never encountered that value before.
To recap: a Gloom filter can produce false positives, meaning it may think that a value is a duplicate even though it’s not. This can happen when two different values share the same hash code. However, a Gloom filter cannot produce false negatives. Accordingly, if the Gloom filter claims that the value does not exist, we can absolutely believe that.
Blacklists
Believe it or not, false positives can potentially be tolerable in a number of applications. One example of this is a blacklist.
Suppose we’re maintaining a web server and the server has been suffering from a number of malicious attacks. Luckily, we’ve been able to check the logs and discover that these attacks are coming from a relatively small set of IP addresses. To combat the nefarious hackers, we create a blacklist of these IP addresses and tell the server to deny access to all of them.
To save space, we can store these IP addresses inside a Gloom filter. Then, each time our server receives a web request, we check the request source against our blacklist. That is, we hash the IP address into an integer and check the corresponding index inside our Gloom filter to see if there’s a 1 bit. If there is, it means that this IP has previously been blacklisted, and we will therefore deny access to the request.
Now, because there may be false positives, it’s possible that we end up blocking a request from a benign IP address. This can happen if the benign IP address hashes into the same hash code as an address from our blacklist. However, depending on the application, this may be okay. That is, it may not be a big deal for us to block a few valid requests here or there in the name of defending ourselves from hackers.
At the same time, our blacklist is ironclad, as we will never end up accidentally allowing a request from an IP address on our blacklist. Because a Gloom filter reports no false negatives, if it says that the current request’s IP address is not on the blacklist, we can trust it fully.
The Return of Monte Carlo
So far, we’ve seen that a Gloom filter can be used to represent a set. The Gloom filter is kind of like a bit vector, but it can be used to store even non-integer data (like strings)—something that bit vectors cannot do.
Sure, a hash table can also be used to store strings as a set. The advantage of Gloom filters, though, is that they take up less space than hash tables. That being said, Gloom filters have the disadvantage of potentially producing false positives.
You learned in Chapter 9, that a Monte Carlo algorithm can sacrifice accuracy in order to gain speed. It emerges that Gloom filters use another type of Monte Carlo algorithm. That is, they sacrifice accuracy to gain space. We could even say that a Gloom filter is a Monte Carlo data structure since it’s a data structure that operates on Monte Carlo principles.
But is a Gloom filter a good Monte Carlo data structure? Indeed, all Monte Carlo algorithms and data structures, by definition, sacrifice some accuracy. But to be an effective Monte Carlo algorithm, we need to ensure that the chances of error are low enough to satisfy our application’s needs. To determine whether Gloom filters are effective, we need to measure how accurate or inaccurate they are.
So, let’s do that.
Gloom Filter Error Rate
In the previous example, where all values hash into one of eight possible hash codes, any two values will have a 1 in 8 chance of colliding. This means that if we have a single item in our Gloom filter, when we check to see if some other item is in the Gloom filter, there’s a 1 in 8 chance we’ll get a false positive.
Now, say that there are four different items already in our Gloom filter, and they’re all marked by different bits. The next item we check against our set will have a 4 in 8, or 50 percent, chance of being a false positive. That’s a pretty high error rate. If you’re using a Gloom filter for a blacklist, you’d be wiping out half of all legitimate traffic, which may be too much.
The question, then, is how we can reduce the false positive error rate of Gloom filters.
Increasing the Gloom Filter Size
Perhaps the easiest approach to reduce Gloom filter error rates is to simply increase the size of the Gloom filter. If we made it so that our Gloom filter uses 100 bits and the hash function produces 100 possible hash codes, there’s only a 1 percent chance that two different values will collide. And if we make the Gloom filter the size of 10,000, the chances of any two values colliding will be a mere 1 in 10,000. Whether or not that’s okay for your application is up to you, but this is most certainly a great improvement.
The downside, though, of increasing the Gloom filter’s size is the fact that now we’re taking up more space. The entire point of the Gloom filter was to reduce space, so by increasing its size, we’re neutralizing the Gloom filter’s main advantage. It’s pretty hard to get a Gloom filter to an acceptable level of accuracy while still allowing us to save significant space.
But we can do better. In the next section, I’ll introduce a new technique for reducing the filter’s error rate. With this approach, we can turn our Gloom filter into a Bloom filter and achieve some impressive results for striking a solid balance between accuracy and space savings.
