Data structures
Bloom filter
"A Bloom filter is a space-efficient probabilistic data structure [...] used to test whether an element is a member of a set"[1], with occasional false positives (and quantifiable amount of them), but no false negatives.
A little more mechanically put, a bloom filter is
- a fixed-size structure (a balance between 'small meaning not wasting space' and 'larger to improve effectiveness')
- with constant-time adds and checks,
- where we add() all things we see,
- where a get() of the same key, asking "have we added (seen) X before", is answered either with
- "quite possibly" or
- "definitely not"
Why is that useful at all?
Consider you have huge yet slow-to-access storage.
It would be great if we only access that when we need to.
If we had an index-like thing in RAM that could answer "I definitely don't have this" or "I definitely have this", that would be excellent, but the size of that structure will grow with the amount of data in the store, so over time you won't be able to guarantee you can keep it in RAM.
It turns out that if you can accept the answer "definitely not" and "possibly yes",
you can make a much smaller (and fixed-size) data structure.
With fully correct answers, there is a size at which you have to say you can't.
Bloom filters instead slowly degrades the quality of its answers instead.
So yes, as the store actual store grows, our index becomes slowly less useful, having to say 'definitely not' less often, and 'possibly' more often.
But as long as it can say 'definitely not' a bunch, this still keeps on being useful. ...in ways you can quantify when you know how much that difference costs you.
How does it work?
While it's not precisely how they work, you can intuit the properties of how Bloom filters work, by modifying a hash map.
Consider
- deciding how many buckets you have up front
- for each bucket, store just true or false (instead of all values going to that bucket, as a real hashmap would do)
Since you're still deciding bucket by hash of the key,
- it fills the allocated space pretty evenly
- if you fetch a false from that it means you didn't previously set a key like that.
- if you fetch get a true from that, it ends up meaning "the hash can always have collided, so I can only answer possibly".
This also helps the intuition on why having a smaller-sized bloom filter (in the hashmap analogy: fewer buckets) increases the the possibility of getting a 'possibly' rather than a certain 'nope'.
You probably want to make the bloom filter as large as your RAM allows (...wel, up to the current/expected amount of items stored), to increase the amount of "nope"s and decrease the amount of false possibles.
But for some applications, the bloom filter can be quite small, and still e.g. save a reasonable amount of accesses, which is why this is useful even on microcontrollers.
You can quantify how large of a bloom filter you will want for a given set size, and desired error rate - there are calculators.
See also