Difference between revisions of "2934: Bloom Filter"
(→Explanation: Rewriting to make it more accessible to the layperson.) |
(→Explanation: Lost this bit of explanation, which made the size-estimate-of-1-bit bit into a bit of an orphan.) |
||
| Line 19: | Line 19: | ||
# '''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. | # '''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. | # '''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. | 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. | ||
Revision as of 19:06, 18 May 2024
| 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. If you can address this issue, please edit the page! Thanks. |
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.
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
add a comment! ⋅ add a topic (use sparingly)! ⋅ 
refresh comments!Discussion
It certaintly does contain a thing. 172.68.23.74 00:10, 18 May 2024 (UTC)
The title text deals with inaccuracies in determining whether you have chosen the right programming tool for your membership query (or some different task), not just inaccuracies in the Bloom filter as one of these tools. This analogy remains unexplained. Transgalactic (talk) 11:24, 18 May 2024 (UTC)
- The title text makes a self-description joke, where it depicts using a bloom filter to determine whether bloom filters are appropriate, as if bloom filters were the only tool available for human decisions. 172.68.1.132 21:52, 18 May 2024 (UTC)
A perfectly functional GetHashCode() override in .net is "return 1;". 172.70.34.82 23:37, 18 May 2024 (UTC)
It could be used to test whether the set is empty. 172.70.39.96 09:01, 20 May 2024 (UTC)
The most likely thing in there is yes. Psychoticpotato (talk) 23:10, 20 May 2024 (UTC)
