2934: Bloom Filter

|< < Prev Comic #2934 (May 17, 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: the Chrome web browser used to store a Bloom filter of URLs that were known to be malicious, based on a database that was too large to store locally. Chrome used that Bloom filter to confirm that it didn’t need to warn the user that they were visiting a malicious page. Only in the rare cases that the Bloom filter said the URL might be malicious, Chrome would send the URL to an external service to confirm it was known to be malicious. The developers didn’t want the browser to send every URL to the external service because that would leak the user’s entire browsing history to the service and would add an unnecessary network delay whenever a web page was loaded.

Here's how it works:

1. 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).
2. 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.
3. 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.
4. 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)