{"id":75,"date":"2012-09-26T18:21:24","date_gmt":"2012-09-26T22:21:24","guid":{"rendered":"https:\/\/michaelnielsen.org\/ddi\/?p=75"},"modified":"2012-09-27T08:21:57","modified_gmt":"2012-09-27T12:21:57","slug":"why-bloom-filters-work-the-way-they-do","status":"publish","type":"post","link":"https:\/\/michaelnielsen.org\/ddi\/why-bloom-filters-work-the-way-they-do\/","title":{"rendered":"Why Bloom filters work the way they do"},"content":{"rendered":"

Imagine you’re a programmer who is developing a new web browser. There are many malicious sites on the web, and you want your browser to warn users when they attempt to access dangerous sites. For example, suppose the user attempts to access http:\/\/domain\/etc<\/tt>. You’d like a way of checking whether domain<\/tt> is known to be a malicious site. What’s a good way of doing this?<\/p>\n

An obvious naive way is for your browser to maintain a list or set data structure containing all known malicious domains. A problem with this approach is that it may consume a considerable amount of memory. If you know of a million malicious domains, and domains need (say) an average of 20 bytes to store, then you need 20 megabytes of storage. That’s quite an overhead for a single feature in your web browser. Is there a better way?<\/p>\n

In this post I’ll describe a data structure which provides an excellent way of solving this kind of problem. The data structure is known as a Bloom filter<\/a>. Bloom filter are much more memory efficient than the naive “store-everything” approach, while remaining extremely fast. I’ll describe both how Bloom filters work, and also some extensions of Bloom filters to solve more general problems.<\/p>\n

Most explanations of Bloom filters cut to the chase, quickly explaining the detailed mechanics of how Bloom filters work. Such explanations are informative, but I must admit that they made me uncomfortable when I was first learning about Bloom filters. In particular, I didn’t feel that they helped me understand why<\/em> Bloom filters are put together the way they are. I couldn’t fathom the mindset that would lead someone to invent<\/em> such a data structure. And that left me feeling that all I had was a superficial, surface-level understanding of Bloom filters.<\/p>\n

In this post I take an unusual approach to explaining Bloom filters. We won’t<\/em> begin with a full-blown explanation. Instead, I’ll gradually build up to the full data structure in stages. My goal is to tell a plausible story explaining how one could invent Bloom filters from scratch, with each step along the way more or less “obvious”. Of course, hindsight is 20-20, and such a story shouldn’t be taken too literally. Rather, the benefit of developing Bloom filters in this way is that it will deepen our understanding of why Bloom filters work in just the way they do. We’ll explore some alternative directions that plausibly could<\/em> have been taken – and see why they don’t work as well as Bloom filters ultimately turn out to work. At the end we’ll understand much better why Bloom filters are constructed the way they are.<\/p>\n

Of course, this means that if your goal is just to understand the mechanics of Bloom filters, then this post isn’t for you. Instead, I’d suggest looking at a more conventional introduction – the Wikipedia article<\/a>, for example, perhaps in conjunction with an interactive demo, like the nice one here<\/a>. But if your goal is to understand why Bloom filters work the way they do, then you may enjoy the post.<\/p>\n

A stylistic note:<\/strong> Most of my posts are code-oriented. This post is much more focused on mathematical analysis and algebraic manipulation: the point isn’t code, but rather how one could come to invent a particular data structure. That is, it’s the story behind<\/em> the code that implements Bloom filters, and as such it requires rather more attention to mathematical detail.<\/p>\n

General description of the problem:<\/strong> Let’s begin by abstracting away from the “safe web browsing” problem that began this post. We want a data structure which represents a set S of objects. That data structure should enable two operations: (1) the ability to add<\/tt> an extra object x to the set; and (2) a test<\/tt> to determine whether a given object x is a member of S. Of course, there are many other operations we might imagine wanting – for example, maybe we’d also like to be able to delete<\/tt> objects from the set. But we’re going to start with just these two operations of add<\/tt>ing and test<\/tt>ing. Later we’ll come back and ask whether operations such as delete<\/tt>ing objects are also possible.<\/p>\n

Idea: store a set of hashed objects:<\/strong> Okay, so how can we solve the problem of representing S in a way that’s more memory efficient than just storing all the objects in S? One idea is to store hashed versions of the objects in S, instead of the full objects. If the hash function is well chosen, then the hashed objects will take up much less memory, but there will be little danger of making errors when test<\/tt>ing whether an object is an element of the set or not.<\/p>\n

Let’s be a little more explicit about how this would work. We have a set S of objects x_0, x_1, \\ldots, x_{|S|-1}, where |S| denotes the number of objects in S. For each object we compute an m-bit hash function h(x_j) – i.e., a hash function which takes an arbitrary object as input, and outputs m bits – and the set S is represented by the set \\{ h(x_0), h(x_1), \\ldots, h(x_{|S|-1}) \\}. We can test<\/tt> whether x is an element of S by checking whether h(x) is in the set of hashes. This basic hashing approach requires roughly m |S| bits of memory.<\/p>\n

(As an aside, in principle it’s possible to store the set of hashed objects more efficiently, using just m|S|-\\log(|S|!) bits, where \\log is to base two. The -\\log(|S|!) saving is possible because the ordering of the objects in a set is redundant information, and so in principle can be eliminated using a suitable encoding. However, I haven’t thought through what encodings could be used to do this in practice. In any case, the saving is likely to be minimal, since \\log(|S|!) \\approx |S| \\log |S|, and m will usually be quite a bit bigger than \\log |S| – if that weren’t the case, then hash collisions would occur all the time. So I’ll ignore the terms -\\log(|S|!) for the rest of this post. In fact, in general I’ll be pretty cavalier in later analyses as well, omitting lower order terms without comment.)<\/p>\n

A danger with this hash-based approach is that an object x outside the set S might have the same hash value as an object inside the set, i.e., h(x) = h(x_j) for some j. In this case, test<\/tt> will erroneously report that x is in S. That is, this data structure will give us a false positive<\/em>. Fortunately, by choosing a suitable value for m, the number of bits output by the hash function, we can reduce the probability of a false positive as much as we want. To understand how this works, notice first that the probability of test<\/tt> giving a false positive is 1 minus the probability of test<\/tt> correctly reporting that x is not in S. This occurs when h(x) \\neq h(x_j) for all j. If the hash function is well chosen, then the probability that h(x) \\neq h(x_j) is (1-1\/2^m) for each j, and these are independent events. Thus the probability of test<\/tt> failing is:<\/p>\n p = 1-(1-1\/2^m)^{|S|}. \n

This expression involves three quantities: the probability p of test<\/tt> giving a false positive, the number m of bits output by the hash function, and the number of elements in the set, |S|. It’s a nice expression, but it’s more enlightening when rewritten in a slightly different form. What we’d really like to understand is how many bits of memory are needed to represent a set of size |S|, with probability p of a test<\/tt> failing. To understand that we let \\# be the number of bits of memory used, and aim to express \\# as a function of p and |S|. Observe that \\# = |S|m, and so we can substitute for m = \\#\/|S| to obtain<\/p>\n p = 1-\\left(1-1\/2^{\\#\/|S|}\\right)^{|S|}. \n

This can be rearranged to express \\# in term of p and |S|:<\/p>\n \\# = |S|\\log \\frac{1}{1-(1-p)^{1\/|S|}}. \n

This expression answers the question we really want answered, telling us how many bits are required to store a set of size |S| with a probability p of a test<\/tt> failing. Of course, in practice we’d like p to be small – say p = 0.01 – and when this is the case the expression may be approximated by a more transparent expression:<\/p>\n \\# \\approx |S|\\log \\frac{|S|}{p}. \n

This makes intuitive sense: test<\/tt> failure occurs when x is not in S, but h(x) is in the hashed version of S. Because this happens with probability p, it must be that S occupies a fraction p of the total space of possible hash outputs. And so the size of the space of all possible hash outputs must be about |S|\/p. As a consequence we need \\log(|S|\/p) bits to represent each hashed object, in agreement with the expression above. <\/p>\n

How memory efficient is this hash-based approach to representing S? It’s obviously likely to be quite a bit better than storing full representations of the objects in S. But we’ll see later that Bloom filters can be far more memory efficient still.<\/p>\n

The big drawback of this hash-based approach is the false positives. Still, for many applications it’s fine to have a small probability of a false positive. For example, false positives turn out to be okay for the safe web browsing problem. You might worry that false positives would cause some safe sites to erroneously be reported as unsafe, but the browser can avoid this by maintaining a (small!) list of safe sites which are false positives for test<\/tt>.<\/p>\n

Idea: use a bit array:<\/strong> Suppose we want to represent some subset S of the integers 0, 1, 2, \\ldots, 999. As an alternative to hashing or to storing S directly, we could represent S using an array of 1000 bits, numbered 0 through 999. We would set bits in the array to 1 if the corresponding number is in S, and otherwise set them to 0. It’s obviously trivial to add<\/tt> objects to S, and to test<\/tt> whether a particular object is in S or not.<\/p>\n

The memory cost to store S in this bit-array approach is 1000 bits, regardless of how big or small |S| is. Suppose, for comparison, that we stored S directly as a list of 32-bit integers. Then the cost would be 32 |S| bits. When |S| is very small, this approach would be more memory efficient than using a bit array. But as |S| gets larger, storing |S| directly becomes much less memory efficient. We could ameliorate this somewhat by storing elements of S using only 10 bits, instead of 32 bits. But even if we did this, it would still be more expensive to store the list once |S| got beyond one hundred elements. So a bit array really would be better for modestly large subsets.<\/p>\n

Idea: use a bit array where the indices are given by hashes:<\/strong> A problem with the bit array example described above is that we needed a way of numbering the possible elements of S, 0,1,\\ldots,999. In general the elements of S may be complicated objects, not numbers in a small, well-defined range.<\/p>\n

Fortunately, we can use hashing to number the elements of S. Suppose h(\\cdot) is an m-bit hash function. We’re going to represent a set S = \\{x_0,\\ldots,x_{|S|-1}\\} using a bit array containing 2^m elements. In particular, for each x_j we set the h(x_j)th element in the bit array, where we regard h(x_j) as a number in the range 0,1,\\ldots,2^m-1. More explicitly, we can add<\/tt> an element x to the set by setting bit number h(x) in the bit array. And we can test<\/tt> whether x is an element of S by checking whether bit number h(x) in the bit array is set.<\/p>\n

This is a good scheme, but the test<\/tt> can fail to give the correct result, which occurs whenever x is not an element of S, yet h(x) = h(x_j) for some j. This is exactly the same failure condition as for the basic hashing scheme we described earlier. By exactly the same reasoning as used then, the failure probability is<\/p>\n [*] \\,\\,\\,\\, p = 1-(1-1\/2^m)^{|S|}. \n

As we did earlier, we’d like to re-express this in terms of the number of bits of memory used, \\#. This works differently than for the basic hashing scheme, since the number of bits of memory consumed by the current approach is \\# = 2^m, as compared to \\# = |S|m for the earlier scheme. Using \\# = 2^m and substituting for m in Equation [*], we have:<\/p>\n p = 1-(1-1\/\\#)^{|S|}. \n

Rearranging this to express \\# in term of p and |S| we obtain:<\/p>\n \\# = \\frac{1}{1-(1-p)^{1\/|S|}}. \n

When p is small this can be approximated by<\/p>\n \\# \\approx \\frac{|S|}{p}. \n

This isn’t very memory efficient! We’d like the probability of failure p to be small, and that makes the 1\/p dependence bad news when compared to the \\log(|S|\/p) dependence of the basic hashing scheme described earlier. The only time the current approach is better is when |S| is very, very large. To get some idea for just how large, if we want p = 0.01, then 1\/p is only better than \\log(|S|\/p) when |S| gets to be more than about 1.27 * 10^{28}. That’s quite a set! In practice, the basic hashing scheme will be much more memory efficient.<\/p>\n

Intuitively, it’s not hard to see why this approach is so memory inefficient compared to the basic hashing scheme. The problem is that with an m-bit hash function, the basic hashing scheme used m|S| bits of memory, while hashing into a bit array uses 2^m bits, but doesn’t change the probability of failure. That’s exponentially more memory!<\/p>\n

At this point, hashing into bit arrays looks like a bad idea. But it turns out that by tweaking the idea just a little we can improve it a lot. To carry out this tweaking, it helps to name the data structure we’ve just described (where we hash into a bit array). We’ll call it a filter<\/em>, anticipating the fact that it’s a precursor to the Bloom filter. I don’t know whether “filter” is a standard name, but in any case it’ll be a useful working name.<\/p>\n

Idea: use multiple filters:<\/strong> How can we make the basic filter just described more memory efficient? One possibility is to try using multiple filters, based on independent hash functions. More precisely, the idea is to use k filters, each based on an (independent) m-bit hash function, h_0, h_1, \\ldots, h_{k-1}. So our data structure will consist of k separate bit arrays, each containing 2^m bits, for a grand total of \\# = k 2^m bits. We can add<\/tt> an element x by setting the h_0(x)th bit in the first bit array (i.e., the first filter), the h_1(x)th bit in the second filter, and so on. We can test<\/tt> whether a candidate element x is in the set by simply checking whether all the appropriate bits are set in each filter. For this to fail, each individual filter must fail. Because the hash functions are independent of one another, the probability of this is the kth power of any single filter failing:<\/p>\n p = \\left(1-(1-1\/2^m)^{|S|}\\right)^k. \n

The number of bits of memory used by this data structure is \\# = k 2^m and so we can substitute 2^m = \\#\/k and rearrange to get<\/p>\n [**] \\,\\,\\,\\, \\# = \\frac{k}{1-(1-p^{1\/k})^{1\/|S|}}. \n

Provided p^{1\/k} is much smaller than 1, this expression can be simplified to give<\/p>\n \\# \\approx \\frac{k|S|}{p^{1\/k}}. \n

Good news! This repetition strategy is much more memory efficient than a single filter, at least for small values of k. For instance, moving from k = 1 repetitions to k = 2 repititions changes the denominator from p to \\sqrt{p} – typically, a huge improvement, since p is very small. And the only price paid is doubling the numerator. So this is a big win.<\/p>\n

Intuitively, and in retrospect, this result is not so surprising. Putting multiple filters in a row, the probability of error drops exponentially with the number of filters. By contrast, in the single filter scheme, the drop in the probability of error is roughly linear with the number of bits. (This follows from considering Equation [*] in the limit where 1\/2^m is small.) So using multiple filters is a good strategy.<\/p>\n

Of course, a caveat to the last paragraph is that this analysis requires that p^{1\/k} \\ll 1, which means that k can’t be too large before the analysis breaks down. For larger values of k the analysis is somewhat more complicated. In order to find the optimal value of k we’d need to figure out what value of k minimizes the exact expression [**] for \\#. We won’t bother – at best it’d be tedious, and, as we’ll see shortly, there is in any case a better approach.<\/p>\n

Overlapping filters:<\/strong> This is a variation on the idea of repeating filters. Instead of having k separate bit arrays, we use just a single array of 2^m bits. When add<\/tt>ing an object x, we simply set all the bits h_0(x), h_1(x),\\ldots, h_{k-1}(x) in the same bit array. To test<\/tt> whether an element x is in the set, we simply check whether all the bits h_0(x), h_1(x),\\ldots, h_{k-1}(x) are set or not.<\/p>\n

What’s the probability of the test<\/tt> failing? Suppose x \\not \\in S. Failure occurs when h_0(x) = h_{i_0}(x_{j_0}) for some i_0 and j_0, and also h_1(x) = h_{i_1}(x_{j_1}) for some i_1 and j_1, and so on for all the remaining hash functions, h_2, h_3,\\ldots, h_{k-1}. These are independent events, and so the probability they all occur is just the product of the probabilities of the individual events. A little thought should convince you that each individual event will have the same probability, and so we can just focus on computing the probability that h_0(x) = h_{i_0}(x_{j_0}) for some i_0 and j_0. The overall probability p of failure will then be the kth power of that probability, i.e.,<\/p>\n p = p(h_0(x) = h_{i_0}(x_{j_0}) \\mbox{ for some } i_0,j_0)^k \n

The probability that h_0(x) = h_{i_0}(x_{j_0}) for some i_0 and j_0 is one minus the probability that h_0(x) \\neq h_{i_0}(x_{j_0}) for all i_0 and j_0. These are independent events for the different possible values of i_0 and j_0, each with probability 1-1\/2^m, and so<\/p>\n p(h_0(x) = h_{i_0}(x_{j_0}) \\mbox{ for some } i_0,j_0) = 1-(1-1\/2^m )^{k|S|}, \n

since there are k|S| different pairs of possible values (i_0, j_0). It follows that<\/p>\n p = \\left(1-(1-1\/2^m )^{k|S|}\\right)^k. \n

Substituting 2^m = \\# we obtain<\/p>\n p = \\left(1-(1-1\/\\# )^{k|S|}\\right)^k \n

which can be rearranged to obtain<\/p>\n \\# = \\frac{1}{1-(1-p^{1\/k})^{1\/k|S|}}. \n

This is remarkably similar to the expression [**] derived above for repeating filters. In fact, provided p^{1\/k} is much smaller than 1, we get<\/p>\n \\# \\approx \\frac{k|S|}{p^{1\/k}}, \n

which is exactly the same as [**] when p^{1\/k} is small. So this approach gives quite similar outcomes to the repeating filter strategy.<\/p>\n

Which approach is better, repeating or overlapping filters? In fact, it can be shown that<\/p>\n \\frac{1}{1-(1-p^{1\/k})^{1\/k|S|}} \\leq \\frac{k}{1-(1-p^{1\/k})^{1\/|S|}}, \n

and so the overlapping filter strategy is more memory efficient than the repeating filter strategy. I won’t prove the inequality here – it’s a straightforward (albeit tedious) exercise in calculus. The important takeaway is that overlapping filters are the more memory-efficient approach.<\/p>\n

How do overlapping filters compare to our first approach, the basic hashing strategy? I’ll defer a full answer until later, but we can get some insight by choosing p = 0.0001 and k=4. Then for the overlapping filter we get \\# \\approx 40|S|, while the basic hashing strategy gives \\# = |S| \\log( 10000 |S|). Basic hashing is worse whenever |S| is more than about 100 million – a big number, but also a big improvement over the 1.27 * 10^{28} required by a single filter. Given that we haven’t yet made any attempt to optimize k, this ought to encourage us that we’re onto something.<\/p>\n

Problems for the author<\/h3>\n