The picture to keep in your head

Every question below is answered twice: first at the door, so you can picture it, then in the system, so you know exactly how it works. Each answer ends with a memory code to lock it in.

The picture to keep in your head

A busy club has a bouncer at the door. The guest list is thousands of names long, and checking it properly takes time. But this bouncer has a trick: a small card of marks that lets them say "definitely not on the list" in a second. If the card says "maybe", they check the real list. Most people who aren't invited are turned away instantly; the slow check only happens for the few "maybes".

The bouncer has other small tricks. A tally they can rub out when someone leaves. A rough way to say "about 900 different people came tonight" without writing down every name. A sense of "that one's been in and out a lot" that's never lower than the truth. And a short list of the regulars, the few faces seen most often.

None of these tricks is exact. All of them are tiny and fast. That's a probabilistic data structure: give up a little accuracy, in a way you control, and the answer fits in kilobytes instead of gigabytes.

Our running example is the bookstore again: 10 million customer accounts, around 2 million visitors a day and 100,000 searches an hour (assumptions for practice). We want to check "is this username taken?", count unique visitors, count how often each search term is used, and show trending searches.

Figure: each structure answers one question, approximately, in a tiny amount of memory.

---