Bloom Filter

A Bloom filter is a trick from computer science that lets a program answer a single question: Have I seen this thing before? Instead of fully storing all previous entries, the Bloom filter only remembers a kind of short note for each entry. This requires extremely little storage space, but it comes at a price. The filter can say with full certainty that something never occurred before. In the case of a hit, however, it only says that it very probably occurred. Such false hits are called false positive results, and their frequency can be set when building the filter.

Why memory is sacrificed for this

Large systems constantly need to check whether something is already known. A search engine doesn’t want to download a web page twice. A database doesn’t want to search the hard drive on every request if the sought entry doesn’t exist anyway. This check happens millions of times per second and therefore must be tiny and fast.

A classic list of all previous entries would be far too large for this. For a billion web addresses, one would easily need several tens of gigabytes. A Bloom filter for the same amount of data gets by with about one gigabyte at an error rate of one percent. This difference determines whether the check takes place in fast working memory or on the slow hard drive.

The direction of the error is important. The filter never claims that something is new when it is actually old. At most, it claims that something is old when it is actually new. For many applications, this is exactly the harmless direction of error. In the worst case, an unnecessary but correct re-check is triggered.

Flipping bits instead of remembering entries

At its core, a Bloom filter consists of a very long series of switches that are either off or on. At the start, all are set to off. When a new entry is added, it is run through several computational procedures, so-called hash functions. Each of these transforms the entry into a position number within this series. The switches at these positions are set to on.

During a query, the same thing happens again. The program calculates the positions and checks. If even a single switch is off, the entry was guaranteed never present. If all are on, the answer is: probably already present. This is not certain, however, since these switches could have been flipped by other entries.

You can imagine this like stamp imprints on a sheet of paper. Each visitor leaves three stamps at fixed spots. If you find all three stamps of a visitor, they were probably there. But it could also have been three other people whose stamps happened to land exactly there. The fuller the sheet gets, the more often this happens. That’s why the size of the filter is set in advance to match the expected amount of data. A typical misconception, by the way, is the assumption that entries can be deleted again. This is not possible, because a switch can belong to multiple entries.

Where Bloom filters run quietly in the background

Databases such as Cassandra or HBase use Bloom filters to avoid hard drive accesses. Bitcoin software used them for a time so that lightweight devices only had to request the transactions relevant to them. Web browsers, too, have used similar methods to check addresses against lists of known fraudulent sites without storing the entire list locally.

In the AI context, Bloom filters appear in the preparation of training data. Training texts come from enormous web collections and contain massive amounts of duplicates. Removing these duplicates measurably improves the quality of a language model. With billions of text passages, a Bloom filter is often the only practical way to detect repetitions.

In news articles about infrastructure, the term usually appears as a side note about efficiency. Related are hash tables, which answer exactly but require significantly more memory. Anyone who knows the difference understands a fundamental rule of computer science: a bit of accuracy is often traded for a great deal of speed.