the count-min sketch

You want to keep an approximate tally for every distinct item in a massive stream — how many times has each URL, word, or IP appeared? — but there are far too many distinct items to give each its own counter. The count-min sketch is a small two-dimensional table of counters, plus a few hash functions, that lets you bump an item's tally on the fly and later ask 'about how many times did item x appear?' and get a close answer, all in space that does not grow with the number of distinct items.

Here is the mechanism. Take a table with d rows and w columns of counters, all starting at 0, and pick d independent hash functions h1..hd, one per row, each mapping any item into one of the w columns. To record an arrival of item x, add 1 in every row at the column its hash picks: increment row1[h1(x)], row2[h2(x)], ..., rowd[hd(x)]. To estimate x's count, look at those same d cells and report the MINIMUM of them. Why the minimum? Every cell that x touches contains x's true count PLUS whatever other items happened to collide into that cell — collisions only ever add, never subtract. So each cell over-estimates, and the smallest is the least polluted, hence closest to the truth. With w = e/epsilon and d = ln(1/delta), the estimate exceeds the true count by at most epsilon*m (m = stream length) with probability at least 1 - delta.

The count-min sketch matters because it is the go-to frequency estimator for streams: it powers heavy-hitter detection, finds frequent network flows, supports approximate database query sizes, and serves caches deciding what is hot — all in fixed kilobytes regardless of how many keys exist, with O(d) work per update and per query. The honest caveats: its error is one-sided — it can OVER-count (because collisions add) but never under-count, so it is ideal when over-estimates are tolerable; it works best for skewed data with genuine heavy hitters; and the guarantee is probabilistic and proportional to the total stream mass m, so rare items sit in the noise.