Space/Time Trade-offs in Hash Coding with Allowable Errors

Why this one

The original Bloom filter paper, and a good demonstration that a well-chosen wrong answer is a design tool. Bloom's insight is that for a membership test you often do not need certainty on both sides: a structure that says 'definitely not present' or 'probably present' can be made an order of magnitude smaller than one that has to be exact, and the false-positive rate is a knob you set with two numbers, bits per element and hash count. Read it when you are in the storage-engines module, because the reason an LSM-tree can answer a read without touching every SSTable on disk is a Bloom filter sitting in front of each one - and the reason your false-positive rate matters is that each one costs a real disk seek.