How Do You Check a Billion Items Without Storing Them? Accept Being Wrong Sometimes

Start with a long row of bits, all set to zero. To add an item, run it through several different hash functions, each of which turns the item into a position in the row, and set the bit at each of those positions to one. To test whether an item is present, compute the same positions and look at those bits. If any of them is zero the item was definitely never added. If all of them are one the item was probably added, or the bits happened to be set by other items. The structure never stores the items themselves.

The asymmetry of the answers is the whole point:

• •A negative answer is always correct and can be trusted
• •A positive answer may be wrong, at a controllable rate
• •The space needed does not depend on how large the items are
• •Roughly ten bits per item gives a one percent error rate
• •Adding more items raises the error rate for everything
• •Items cannot be removed, since bits may be shared

Comparing it with the obvious alternative shows the scale of the difference. Storing a billion web addresses directly requires tens of gigabytes. Storing them in a structure that can be checked quickly requires more still. The approach here needs about a gigabyte for a one percent error rate and about one and a half for a tenth of a percent, regardless of how long each address is, and the check takes constant time. That is why the technique is used wherever the set is too large to hold and where an occasional false yes is cheap because it merely triggers a slower exact check.

Two numbers have to be chosen before anything is stored and getting them wrong is expensive. The length of the row of bits and the number of hash functions together fix the error rate for a given number of items, and both depend on knowing roughly how many items there will be. Too few bits and the row fills with ones until almost everything looks present. Too many hash functions and each item sets too many bits, which fills the row faster, while too few makes collisions more likely. There is a best number of functions for any chosen size, and practical implementations compute it rather than guessing.

The pattern appears throughout large systems, usually as a first filter in front of something expensive. Databases use it to avoid reading a file from disk that certainly does not contain a wanted key, which is a large share of all lookups. Web browsers have used it to check addresses against lists of known malicious sites without downloading the list. Content delivery networks use it to decide whether an item is worth caching. Spell checkers used it when memory was scarce. Cryptocurrency clients use it to request only relevant transactions. In every case a false yes costs a wasted lookup and a false no would cost correctness, which is why the asymmetry fits.

Hashing an item to several positions in a row of bits and setting them allows a later check that answers definitely not or probably yes, without storing the items at all. Roughly ten bits per item gives a one percent false positive rate whatever the items are. Items cannot be removed. The structure sits in front of expensive lookups, where a wasted check is cheap and a missed one is not.