Count-Min Frequency Sketch

The Count-Min Sketch is a probabilistic data structure that serves as a frequency table of events in a stream of data. It uses hash functions to map events to frequencies, but unlike a hash table, it uses sub-linear space at the cost of overcounting some events due to collisions.

Experiment

Let's verify this using the interactive tool. First, select the "Skewed" stream.

1. Set the Stream control to "Skewed" which sets the text "ABAACADAB".
2. Set the Width control to 3.
3. Set the Depth control to 2.
4. Notice the resulting Sketch Data Structure row displays update in real-time.
5. Observe the queried row counts and estimated count are exactly what we calculated manually.