Say you want to lookup if a username is in a database. That could take a while if you have a really large db of usernames, but you want to tell a user quickly if a name is taken.
So what you can do is make a bloom filter, which is basically just an array of bits of n length. Let’s say 10 for our example.
Then gather some hash functions (h1, h2, and h3).
When someone inputs a username, you run it through the hash functions, and modulo by the number of bits, and get an integer result.
So:
h1(“rattlesnakedave”) % 10 = 3 h2(“rattlesnakedave”) % 10 = 7 h3(“rattlesnakedave”) % 10 = 2
Then you check the bits at position 3,2, and 7 in the array.
If they any of the bits are set to 0, we haven’t seen the username before.
If they’re all set to 1, we have possibly seen the username before.
Let’s say they’re all set to 0, so we probably haven’t seen it. We can present the message that the username is available, and allow registration. During registration, we can do a slower more expensive verification that the username isn’t actually in the dataset.
Now that the username is in the dataset, we can flip the bits on our bloom filter at position 3,2, and 7 to 1. So the next time we lookup that username we can tell quickly that it’s probably taken.
There is no way to delete from the bloom filter. The more values you store relative to its size, the more false positives you get.
Hopefully that makes sense, and is correct.
If any of the bits is zero, the value definitely isn't in the set (also not "probably haven't", but definitely not).
Was trying to keep the initial explanation simple by leaving out the false positives scaling relative to the size of the array and set, and then clarifying at the end.
The second part (any 0 bits it hasn’t been seen) is true, a goof up on my part.
Look at all the usernames in the input, keep track of all the letters you’ve seen. When you get a new name, if you’ve seen all the letters before, you might have seen the name before. If there’s a new letter, it must be a new name.
Obviously that isn’t a great hash function, some letters are more common than others, so real Bloom filters use better ones, but it works basically the same way.
Think of them as asking a bouncer if they have seen a suspect enter a club. They don't know folks by name, but can answer a series questions about the people that entered.
Then, the "hashes" are effectively your new questions. Did someone with green hair enter? Did someone limping enter? Wearing a hat? Etc
To that end, it is clear that you won't get a definitive yes to entry. You may get a sufficient no, though.
say though nummerology you reduce the character values of a name to a number 0-10. Lots of names will reduce to the same number. We take 11 bits and for "jim" we set the first bit. We have only one name in our data set so all other bits are 0. Now if someone types "joe" in the search box and it reduces to 2 we look at the second bit, see it is a zero and know 100% *for sure* that this name is not in the data set. If "jack" reduces to 1 and we look him up we see 1 is set so this name *might be* there.
- Syndrome
I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!