You have probably seen it: you click a link, and instead of the site, Chrome shows a red warning that says "Dangerous site." To show it, Chrome has to check every address you visit against Google's list of known bad sites. Google says Safe Browsing checks more than 10 billion URLs and files a day and shows more than 3 million warnings, so nearly every answer is no.
Asking Google's servers about every click would make each page wait on the network, and the servers would learn every address you visit. So around 2011, Chrome ran that check in your computer's memory, with a structure that was allowed to be wrong, and only asked Google when the local check said "maybe." How can a check that makes mistakes keep you safe, and why would anyone build one on purpose? The answer is a five-page paper from 1970.
This paper is hosted by its original publisher.
Read on dl.acm.orgThe Problem in 1970
Burton H. Bloom, at the Computer Usage Company in Newton Upper Falls, Massachusetts, published the paper in Communications of the ACM in July 1970 (volume 13, number 7, pages 422 to 426). His running example was a program for automatic hyphenation: deciding where a word may break with a hyphen at the end of a line.
He assumed that a few simple rules handle about 90 percent of English words, and the other 10 percent need a dictionary lookup. That dictionary is too big for the computer's core memory, so it lives on a disk, which is far slower to reach. In his worked example:
| Thing | Value |
|---|---|
| words to hyphenate | 500,000 |
| handled by the simple rules | 450,000 |
| need the dictionary on disk | 50,000 |
| answer to "is this word in the dictionary?" | no, nine times out of ten |
You ask the question for every word, and the answer is almost always no. So what really has to be fast is the "no." Bloom calls it the reject time: the average time it takes to decide that something is not in the set.
It is the same shape as Chrome's problem about forty years later: a fast check in memory, in front of a slow check that is always right (the disk dictionary in 1970, Google's servers in 2011).
