What is a Count-Min Sketch and when would you use it?

Count-Min Sketch is a probabilistic data structure for frequency estimation of items in a stream using sub-linear space. It uses a 2D array with d hash functions (rows) and w counters (columns). Insert: increment counters at hash positions in each row. Query: return minimum across all rows (minimum reduces over-counting from collisions). Space is O(w*d), error is O(n/w) with probability 1-delta for d=log(1/delta). Used for network traffic monitoring, NLP word frequencies, and heavy hitters detection.