Concepts
Probabilistic data structures (Bloom, HyperLogLog, Count-Min)
Intuition
Imagine you need to answer questions about an enormous number of items without being able to store the whole list: "have I seen this item?", "how many different items have I seen?", "how many times did this one appear?". Instead of the list, you keep a small, fixed-size board, and each item, after being scrambled by a formula, leaves marks at a few positions on that board. Because the board is much smaller than the data, it keeps only a summary, either because different items end up marking the same positions, or because the marks are only a statistical hint; that is why the answers are approximate and, in exchange, the larger the board, the smaller the error, and you choose how much error to accept.
How it works
All of these structures use hash functions to spread items in a seemingly random way and keep a fixed-size summary instead of the set or the stream. The Bloom filter is a vector of m bits with k hash functions: inserting an item turns on the k corresponding bits, and querying says 'definitely not present' if any of those bits is 0, or 'assumed present' if all are 1, an answer that can be a false positive but never a false negative. After inserting n items, the false-positive rate is approximately (1 − e^(−kn/m))^k, and, given m and n, the k that minimizes it is ln 2 · m/n, at which point half the bits are 0 and the rate is about 0.6185^(m/n). HyperLogLog estimates how many distinct items exist: the first b bits of the hash pick one of m = 2^b registers, the rest of the hash gives the rho (the position of the leftmost 1 bit), and each register stores the largest rho seen, since a prefix with many zeros suggests a large cardinality. The estimate uses the harmonic mean of the 2^register values; in the ideal multiset model (uniform, independent hashed values) and for m ≥ 3, Theorem 1 of the paper gives an asymptotic standard error of β_m/√m plus a small oscillation (less than 5×10^-4 for m ≥ 16), with β_m bounded and equal to about 1.04 in the limit, and a small-range correction handles low cardinalities. Count-Min Sketch estimates the frequency of each item with a matrix of counters with d rows and w columns, with w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉, where each row has its own hash; an update (i, c) adds c to the counter h_j(i) in each row j, and, when the vector's values never go negative, the point query returns the minimum across the rows, because then colliding items only add value to the counter (if values can be negative, the paper uses the median); in the non-negative case the estimate is never below the true value a_i and, with probability at least 1 − δ, does not exceed a_i + ε·||a||₁, where ||a||₁ is the sum of the vector's values, so the error is always upward. These summaries also merge: the bitwise OR of two Bloom filters with the same size and the same hash functions represents the union of the sets, the component-wise maximum of HyperLogLog registers computed over parts of a file gives the registers of the whole file, and the total estimate comes from them, and the linear sum of updates in Count-Min makes it easy to combine sketches from distributed locations.
In practice
You choose the structure by the question and by the error the system tolerates: the Bloom filter for membership, HyperLogLog for counting distinct items, and Count-Min for frequencies. In Summary Cache, each web proxy broadcasts a Bloom filter of its cache instead of a list of URLs, and a false positive only makes the proxy ask another proxy for a page it does not have, a cost that the survey by Broder and Mitzenmacher considers smaller than the gain in traffic; according to that survey, the technique is used in Squid, under the name Cache Digests. In network monitoring, HyperLogLog counts distinct source-destination pairs, which helps detect attacks and worm propagation, and, when counts only grow, Count-Min makes it possible to find heavy hitters (very frequent items) without missing any, since the estimate never falls below the real value.
Use it in a design
Practice the cases that rely on this concept in the System Design school.