What are Bloom filters?
medium.com
medium.com
>I sigh. I’m hungry and the main course has just arrived — venison glazed in honey, served with a sweet potato hash.
I learned more about what the author had for dinner on their last birthday than I did about bloom filters in the first paragraphs.
So while they prefer your blog - they aren't sure what you had for dinner on your last birthday...
https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
The differences are somewhat subtle, but the use cases overlap a lot.
Just go to https://en.wikipedia.org/wiki/Bloom_filter
It's clearer and more informative.
As pedagogy, I think this is the wrong approach.
The author already knows Bloom filters and therefore, it seems like the most logical thing to first talk about is hash functions because that's how it's implemented.
Unfortunately, that's not how a person brand new to the concept thinks about it. The first thing to talk about is motivations and scenarios and use cases.
For that, the first 2 paragraphs of wikipedia article[1] on Bloom filters is fairly straightforward. It explains why it's an interesting technique. Imo, those paragraphs are a better introduction than the author's dive right into "hash functions" immediately after unrelated blurbs of "I put my fork down" and "my wife shakes her head with a rueful smile."
This style is characterized by titles like "Catchy Phrase: The surprising tale of a subtitle that actually tells you what the book is about. Or does it?" "Catchy Phrase" tells the story of an single data point, or maybe three, with edge-of-your-seat tension provided by a jumbled chronology. It opens a generation before the main data point was born, then skips to the present day, before jumping into the middle of a tangential story. Then it's back to where we left the origin story of the data point, but this time we're in a different location looking at the second data point. Next comes some speculation about a possible rosy future and maybe a motivating example. Next we end the tangential story, which introduces the third data point, at it's funeral. The tangential story begins. As you read, you can see a complex theme slowly but deftly woven from the timelines of the several stories. It's a pattern that a knitter might call "felt". You can't help but be drawn in. It's so fascinating and intricate that you, like the author, sometimes have trouble distinguishing cause from effect, which adds an alluring air of mystery. The ideas must be Important. Despite the complexity, in the end the conclusions seem simple and obvious. You feel smart. You go to a dinner party and gush about it to your friends. They wake up the next day and, despite one-too-many cocktails, find that they remember the title of "Catchy Phrase". They look it up, and One-Click (tm) later, the life cycle is complete.
You aren't the audience, you're the vector.
I honestly just closed the article when he started in on hashing, because I want to know about bloom filters (which I don't know about), not the basics of hashing (which I learned as an undergrad, and need to know day-to-day as a working programmer).
I read the article, but am still not grasping the full construct and how it functions. I'm hoping a hands on tutorial might give me a better sense.
When it comes to technical articles this starts to become extremely annoying to read blogs/papers as if it was written for BuzzFeed.
When you are going to fetch data from a remote location, you don't want to make a trip in vain.
So you end up storing them as a fixed size metadata chunk that lets you guess whether to go fetch it or not.
The neat trick is that the bloom filters have no false-negatives - the data might not exist (false positives), but it will never say "no" if it does exist.
But unfortunately, it doesn't really support deletion neatly - so it's really useful for scenarios where it's a first point of lookup before overloading a central source-of-truth.
The best use case I've seen for it is in Chrome, where the "Safe browsing" list is actually a huge bloom filter, which is used to decide whether to ask Google if this domain is safe.
So the list of banned URLs might be in the millions, but the bloom filter is a few megabytes and when it has a false positive, it goes & checks upstream whether it is indeed still banned/problematic.
[1] - http://www.slideshare.net/Hadoop_Summit/orc-2015-faster-bett... [2] - https://issues.apache.org/jira/browse/HIVE-11306
I believe browsers also store their Safe Browsing (anti-malware/phishing) blacklists in bloom filters.
When you check the Bloom filter it tells you:
1) it might be there
or
2) it definitely isn't there.
In the case of 2, you don't need to look it up. In case 1, you'll need to do the actual lookup.
It is commonly used to filter high volume / frequency requests for something. For example, if you have a list of banned IP addresses, user accounts, etc, you can quickly go through the bloom filter without hitting the database.
I can't actually remember what data was being looked up in the tables, though.
The service kept an array of 7 filters, rotated daily - the oldest would be cleared and reused for new items, giving us 6-7 days of history. Each individual header was low-value, and a few false positives every week wasn't a big deal - Usenet servers lost a lot more during their normal course of operation.
A certain product of ours keeps track of certain urls visited. We're talking millions of (unique) urls. We use bloomfilters to quickly check if a url was visited or not. If the bloomfilter search is positive a more expensive search inside a log file begins that gives a conclusive result (since bloomfilters have a (very) small false positive-rate, but we want to be perfectly sure).
One of the neat things about Bloom filters is that you can choose your own false positive rate, by tuning the number of hashes and the storage size.