Main Page
Welcome to the explain xkcd wiki!
We have an explanation for all 2934 xkcd comics,
and only 6
(0%) are incomplete. Help us finish them!
Latest comic
| Bloom Filter |
 Title text: Sometimes, you can tell Bloom filters are the wrong tool for the job, but when they're the right one you can never be sure. |
Explanation
|
This explanation may be incomplete or incorrect: PROBABLY CREATED - Please change this comment when editing this page. Do NOT delete this tag too soon. |
The comic is about a data structure called a Bloom Filter. Software engineers use Bloom Filters to check if something is in a set or estimate how many things are in that set, using limited memory. One example is a web browser checking to see if a URL is malicious without storing a large database locally. (are bloom filters used for that? wouldn't this use cause a bunch of false positives, preventing the user from accessing random legitimate websites? the common bloom filter example is the lite wallet protocol in bitcoin where false positives don't block anything.)
Here's how it works:
- Adding Items: When you add an item, it gets hashed (a way of transforming it into numbers) by several hash functions. These hash functions mark certain spots in a big array of bits (think of it as a row of lights that can be on or off).
- Checking Items: To check if an item is in the set, you hash it with the same functions and see if all the corresponding spots are lit up. If they are, the item might be in the set, but there's a chance of a false positive (the Bloom Filter could mistakenly say the item is there when it’s not). If any spot is not lit up, the item is definitely not in the set.
- False Positives: The larger the array compared to the number of items, the lower the chance of false positives. For example, 10 bits per item gives about a 1% false positive rate.
- Counting Items: By analysing the activated bits, with appropriate calculations, you can derive an estimate of how many individual items are 'stored' for confirmation within the array. This estimate's accuracy will depend upon several factors, but more array-bits (making themselves potentially available to 'remember' each item) will be one of the most important ones when it comes to narrowing down the likelihood.
In the comic, Cueball has a 1-bit Bloom Filter, which is almost useless. When empty, it correctly says nothing is in the set. But as soon as one item is added, the bit is set to 1, and now it falsely says every possible item is in the set. Its size estimate also becomes "between 1 and infinity," which isn’t helpful.
Having multiple hash functions is pointless for a 1-bit filter since they all end up pointing to the same single bit.
The title text carries the characteristics of the bloom filter into the decision making process for choosing a bloom filter over other candidate data structures. In an analogous way (according to the text), you can be sure when they are not the best approach, but only conclude that they are with a limited degree of probability.
Transcript
|
|
This transcript is incomplete. Please help editing it! Thanks. |
- [Ponytail holds out her hand to Cueball, who is holding a paper with a 1 on it.]
- Ponytail: Does your set contai-
- Cueball: Yeah, probably.
- [Caption below the panel:]
- One-Bit Bloom Filter
Is this out of date? .
New here?
Last 7 days (Top 10) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
You can read a brief introduction about this wiki at explain xkcd. Feel free to sign up for an account and contribute to the wiki! We need explanations for comics, characters, themes and everything in between. If it is referenced in an xkcd web comic, it should be here.
- If you're new to wiki editing, see the explain xkcd:Editor FAQ for a specific guidance to this Wiki and the more general help on how to edit wiki pages. There's also a handy wikicode cheatsheet.
- Discussion about the wiki itself happens at the Community portal.
- You can browse the comics from List of all comics or by navigating the category tree at Category:Comics.
- There are incomplete explanations listed here. Feel free to help out by expanding them!
Rules
Don't be a jerk!
There are a lot of comics that don't have set-in-stone explanations; feel free to put multiple interpretations in the wiki page for each comic.
If you want to talk about a specific comic, use its discussion page.
Please only submit material directly related to (and helping everyone better understand) xkcd... and of course only submit material that can legally be posted (and freely edited). Off-topic or other inappropriate content is subject to removal or modification at admin discretion, and users who repeatedly post such content will be blocked.
If you need assistance from an admin, post a message to the Admin requests board.
