Build a Count-Min Sketch

min across hashed counter rows

Challenge 3 of Probabilistic StructuresIntermediate~45 min

Count frequencies in a stream using a fraction of the memory a hash map would need. Build the sketch grid, add and query with the min-across-rows trick, prove it never under-counts, and merge two sketches, the probabilistic counter behind heavy-hitter and traffic-analytics systems.

4 steps

1. 1Hashing into the Grid
2. 2Add and Query
3. 3It Never Under-Counts
4. 4Merging Sketches