Probabilistic Data Structures: Answers Without the Data

Answering set questions exactly costs memory proportional to the data, and that is a lower bound rather than an inefficiency. Sketches give up exactness in a specific, chosen direction and get constant memory in return. This path builds the three that run modern infrastructure: Bloom filters for membership, HyperLogLog for distinct counts in twelve kilobytes, and count-min for frequency. It ends on the property that actually explains their ubiquity, which is not the space saving.