So, in this video, we're going to discuss Bloom filters which is a data structure
developed appropriately enough by Burton Bloom back in 1970. Bloom filters are
variant on hash tables, you'll recognize a lot of the ideas from our hash table
discussion. The win that you get in Bloom filters is that they are more space
efficient than run of the mill hash tables and they're going to handle, they
do allow for errors, there is a non zero false positive probability when you do
look ups but that's still a win for some applications. So, it's a very cool idea,
very cool data structure. You do see it used quite a bit in practice so let's
start talking about it. So, we'll go through the usual topics that we do
whenever we discuss a new data structure. So first, I want to tell you what
operations they support and what kind of performance you're going to expect from
those operations, in other words, what is the API corresponding to the data
structure. Secondly, I'm going to talk a little bit about what it's good for. So,
what are some potential application and then we'll take a peek under the hood.
I'll tell you some of the implementation details with an emphasis on explaining why
you get the kinds of performance trade offs that you do with Bloom filters. So,
to first order, the raison d'être of Bloom filters is exactly the same as a
hash table. It supports super fast inserts, super fast look ups. You can put
stuff in there and you can remember what you put in earlier. Now, of course, what
you should be wondering is what we already know what data structure that supports
super fast in certain look ups, a hash table. Why am I bothering to tell you
about yet another data structure with exactly those same operations? So, let me
tell you about the pros and cons of Bloom filters relative to run off the mill hash
tables as we've already discussed. The big win is that Bloom filters are more space
efficient than hash tables. No matter whether they are implemented with chaining
or with open addressing, you can store much less space per objects. In fact, as
we'll see, less space than that of an object itself using a Bloom filter. As
far as the cons, well, first of all, this is really for applications where you just
want to remember what kind of values you see. You are not trying to store pointers
to the objects themselves and just trying to remember values. So, the first drawback
of the Bloom filter is that because we want to be so space efficient, we don't
even want to remember the object itself just whether or not we've seen it before.
We're not going to be able to store the objects or even pointers to the objects in
a Bloom filter. We're just going to remember what we've seen and what we
haven't. So, some of you might know the terminology hash set for this kind of
variant of a hash table as opposed to a full blown hash table or hash map. The
second con is at least in the vanilla implementation of Bloom filters that I'm
going to describe here, deletions are not allowed. You can only insert, you can't
delete. The situation with deletions is very much similar to hash tables
implemented with open addressing. It's not that you can't have a Bloom filter that
accommodates deletion, you can, there are very instances of it but that requires
significantly more work and we're not going to discuss it here. So, the first
order at least for vanilla Bloom filters, you want to think of them as suitable for
applications or deletions or not a first order of operation. Now, the third con and
this is a drawback that we have not see previously using any data structures is
Bloom filters can actually make mistakes. Now, what kind of mistake could this kind
of data structure possibly make when all you're really doing is looking something
up. Well, one of mistake would be a false negative and that means you have inserted
something previously then you look it up and the hash table or the Bloom filter
says, it's not there. So, Bloom filters will not have false negatives of this
form. You've insert something, you look it up later, it's definitely going to
confirm that you inserted it in the past. But Bloom filters will have false
positives, that means that despite the fact you have never inserted say, a given
IP address into the, into the Bloom filter, if you look it up later, it will
say that you have. So, there will sometimes be in some sense phantom objects
in Bloom filters, objects which it thinks have been inserted even though they
haven't been. So, given that, I am now showing you two data structures with
essentially the same functionality, hash tables and Bloom filters, at least, if we
ignore the deletion issue. You might want to wonder which one is more appropriate,
which one is more useful. And because there is these trade offs between the two,
the answer as you expect is, it depends on the application, right? So, if it's an
application where space is really at a premium, you might want to turn to Bloom
filters especially if a small chance of a false positive is not deal breaker. If you
have some kind of application where false positives are absolutely out of the
question, of course, you should not use a Bloom filter and you want to think about a
hash table. So, what are some situations where people actually do use Bloom filters
where you either really care about space and/or you don't really care about this
false positive probability. For one of the earliest applications of Bloom filters,
this is not long time ago, this is something like 40 years ago, was the spell
checkers. So, how would you implement a spell checker using a Bloom filter? Well,
first you have this insert phase where you basically just go through the entire
dictionary word-by-word and you insert every valid word into the Bloom filter.
Then, afterwards, when you're presented with a new document that somebody has
written, you're going to go through the document word-by-word for each word, you
say, is this in the Bloom filter? That is, is this one of the legitimate word from
the dictionary which is previously inserted? If the Bloom filters says yes,
this word is in the dictionary as in we've stored and seen that before, then you
treat is as a correctly spelled word and if it's not in the Bloom filters, then you
treat it as incorrectly spelled word. Now, the false positive probability means this
isn't a perfect spell checker. I mean sometimes, you're going to look up a
misspelled word and the Bloom filter won't catch it and it willl actually say yes,
with small probability, we'll say, this is a legitimate word. So, you know, it's not
ideal but, you know, the, the English language is pretty big and space was
definitely at a premium, 40 plus years ago. So, it was a win for that application
at that time, to use Bloom filters to implement a spell checker. Another
application which, you know, remains relevant today is to keep track of a list
of forbidden passwords. Now, why would you have forbidden passwords? Well, maybe, you
want to keep track of password which are too weak or too easy to guess or too
common. You may, yourself, have used the piece of software or website at some point
where it asked you for a password and if you typed in something which is too simple
or too easy, rejected it and asked you to type in another one. So, one way to
implement a list of forbidden passwords is just with the Bloom filter and the idea is
similar to the spell checker. You first, insert into the Bloom filter all of the
passwords that you don't want anybody to use for whatever reason. Then, when a
client comes and tries to type in a new password, you look it up in the Bloom
filter and if you get a positive look up, then you tell the user, no, that's no
good, you can't use that password, choose another one. And this is an application
where you really don't care about the errors, you really don't care about the
fact that there's a false positive rate. Let's assume that the error rate is
something like one percent or 0.1%. So, what would that means in context, that
would just mean once in a while, one in a hundred clients or one in a thousand
clients actually types in a perfectly strong password that gets rejected by the
Bloom filter and they have to type in a second one. Okay, but big deal and if
space is at the, the premium, this is definitely a win to use this super
lightweight data structure to keep track of these blocked passwords. These days
certainly one the killer applications of Bloom filters is in software deployed on
network routers. So, the machinery out in the Internet which is responsible for
transmitting packets from one place to another. So, what are the reasons why
Bloom filters have found fertile application in network routers? Well,
first of all, you do have a budget on space, typically on network routers.
There's a lot of things that you got to do and you don't want to waste that much of
it on some random data structure to do one's specific task. So, you do have a
budget on space and also, you need super, super fast data structures, right? Since
these packets are coming in at this torrential rate which you can't even
imagine and you want to process these packets in real time, sending them off to
the next top. Bloom filters are the work force behind a lot of different tasks that
is done in the network router. You can imagine wanting to keep track of blocked
IP addresses, you can imagine keeping track of the contents of some cache so you
don't do spurious look ups. You can imagine maintaining statistics to check for denial
of service attacks and so on and so forth. So, summarizing as a expert programmer,
what is it that you should remember about Bloom filters, what purpose does this
tool serve in your tool box? Well, as far as the operation supported which is the
same as a hash table, the point is to have super fast inserts, super fast look ups.
But Bloom filters are more lightweight version of a hash table. So, they are more
space efficient but they do have this drawback of having a small error
probability. So, those are the key features you should remember when deciding
whether or not you are working on an application that could make good use of
this data structure. So, having discussed one of th e operations and what these data
structures are good for, let's take it to the next level, let's peer under the hood
and see how they are actually implemented. Cuz this is really a quite simple, quite
cool idea. So, like hash tables, Bloom filters have essentially two ingredients.
First of all, there's an array and second of all, there's a hash function or in
fact, several hash functions. So, we're going to have a random access array
except, instead of having n buckets or n slots as we've been calling them, each
entry in this array is just going to be a single bit. Each entry in this array can
only take on two values, zero or one. And the way they think about the space
occupied by Bloom filters is in terms of the number of bits per object that has
been inserted into the Bloom filter. So, if you have inserted the data set capital
S, then the total number of bits is n, the number of objects that have been inserted
is cardinality of s. So, n / |s| is the number of bits in this data structure that
you are using per entry in the data set. Now, you can tune a Bloom filter so this
ratio is any number of different quantities but for now, I encourage you to
think of this ratio as being eight, that is for each object stored in the Bloom
Filter, you are using only eight bits of memory. That will help you appreciate just
how amazing this data structures are, right, cuz maybe our data set is something
like IP addresses which is 32 bits so what I'm saying here, if this is eight, I'm
saying we are not, definitely not actually storing the IP address. So, we have this
32-bit object we are inserting and we are only using eight bits of memory. This is
how we are going to remember whether its there or whether its not. And again,
certainly, eight bits per object is way less than keeping a pointer to some
associated memory somewhere. So, this is a really impressive minimal use of space to
keep track of what we've seen and what we haven't. And secondly, we need mappings of
given an object to say, given the IP address, what are the relevant bits for
seeing if we've seen this IP address before or not? So, in a Bloom filter, its
important to have not one hash function, but several hash functions. So, k is going
to denote the number of hash functions in the Bloom filter which you think of k is
some small constant somewhere, you know, three, four, five, or something like that.
So, obviously it's a little bit more complicated to use multiple hash functions
as supposed to just one hash function. But it's really not that big of deal. So, we'll
call from our discussion of say, universal hashing, we have identified the entire
families of hash functions which will work well on average. So, instead of choosing
just using one hash function at random from universal family, you gave me k
independent random choices from universal family. In fact, in practice, it seems to
typically be enough to just use two different hash functions and then generate
k different linear combinations of those two hash functions. But for the purposes
of this video, let's just assume that we've done enough work to come up with k,
different good hash functions and that's what we're going to be using in our Bloom
filter. So, the code for both insert and delete is very elegant. So, let's
start by insertion. So, suppose we have some new IP address and we want to stick
into these Bloom filter, what we do? Well, we'll just evaluate each of our k hash
functions on this new object. Each of those tells us an index into our array of
bits and we'll just set those k bits equal to one. And when we do this insert, we
don't even bother to look at what the previous values of these bits were.. So,
zero or one, we don't care. We'll just blithely go in and set this k bits equal
to one, whatever they were before. So, what about looking up? How are we going to
implement that? Well, all you have to do is check for the footprint that was
inevitably left by a prior insertion. So, if we're looking up an IP address and we
know was inserted sometime in the past, what happened when we evaluated the k hash
functions, we went t o appropriate positions in the array and we set all of
those bits to one. So now, I'll just check that, that indeed happened, that is when
we get a new IP address, we're looking it up. We evaluate the hash functions, all k
of them. We look at the corresponding k positions and we verified that indeed
those k bits have been set to one. So, what I hope is clear fairly quickly from
inspecting this very elegant code is that we will not ever have false negatives,
yet, we might have false positives. So, let's discuss those one other time. So,
remember, a false negative would mean that the Bloom filter says, something isn't
there when in fact, it is, that is we insert something and we'll look it up
later and the Bloom filter rejects us. Well, that's not going to happen. Cuz when
we insert something, we set the relevant k bits to one. Notice when a bit is one, it
remains one forevermore. That bits are never reset back to zero. So, if anything
was ever inserted in the subs when we look it up, definitely we well confirm that all
those bits are one. So, we're never going to be rejected by something we inserted
before. On the other hand, it is totally possible that we will have a false
positive. It's totally possible that there will be a phantom object and we'll
do a look up and the Bloom filter will turn yes when we never inserted that
object. Suppose for example, the k = three. So, we're using three different
hash functions. Consider some IP address, fixed IP address, maybe the three hash
functions tell us the relevant bits are seventeen, 23, and 36. Maybe we never
inserted this IP address, but we have inserted IP address number two and in its
insertion, the seventeenth bit got set to one. We inserted some other IP address, IP
address number three and the twenty-third bit got set to one. And then we inserted
IP address number four and the 36th bit got set to one. So, three different IP
addresses were responsible for setting these three different bits but whatever,
its not like we are remembering that. And that once, once we look up this IP address
we really care about, what do we do, we just inspect bit seventeen, its one.
Inspect the 23, its one. We inspect the 36, its also one. For all we know, this
thing really was inserted and the Bloom filter is going to say, yes, it's in the
table. So, that's how we have false positives. All of the bits that are
indicating whether or not a given object are in, are in the Bloom filter were
previously set by insertions from other objects. So, there are two points that I
hope are clear at this stage of the discussion. First of all, that this Bloom
filter, the idea does suggests a possibility of a super space efficient
variant of a hash table, right. So, we've been talking about setting the number of
bits to be say roughly eight times the number of objects that you're
storing so you're only using eight bits per object and for most objects, that's
going to be radically smaller than just the simple array, storing the objects
themselves. Again, if their IP addresses we're only have 25 percent much space as
we actually stored those IP address in just an array with no extra bells and
whistles. The second point is that we're inevitably going to have errors in a
Bloom filter, we will have false positives or we look something up and it
says, its there when in fact, its not. So, those two points I hope are clear. What's
actually not clear is the bottom line. Is this actually a useful idea? For this to
be useful, it'd better be the case that the error probability can be quite small
even while the space per object is quite small. If we can't get those two things
small simultaneously, this is a bad idea and we should always just use a hash table
instead. So, to evaluate the quality of this idea, we're going to have to do
little bit of mathematical analysis. That's what I'm going to show you in the
next couple of slides.