Skip to content

Count-Min Sketch

1. What is it? (2-3 lines)

Count-Min Sketch is a sub-linear probabilistic data structure used to estimate frequencies (counts) of events in high-velocity data streams using a fixed-size 2D array of counters and multiple hash functions.

2. Why does it exist?

Tracking frequency counts for millions of distinct items (e.g. top trending tweets, heavy network flows, top searched items) using a standard Hash Map requires memory proportional to the number of unique items (\(O(N)\) space). Count-Min Sketch uses fixed \(O(1)\) sub-linear memory, estimating frequencies with a bounded error guarantee.

3. Where is it used?

  • Network Traffic Monitoring: Identifying Heavy Hitters / DDOS IP traffic spikes in routers.
  • Trending Topics / Search: Tracking top trending keywords or hashtags in real-time streams (Twitter/X, Google).
  • Caching: LFU eviction policy approximations (e.g., Caffeine cache TinyLFU).

4. How does it work? (simple flow)

  1. Structure: A 2D array of counters with \(d\) rows (hash functions) and \(w\) columns (array width).
  2. Add Event (item):
  3. For each row \(i \in [1 \dots d]\), compute hash index \(c = h_i(\text{item}) \pmod w\).
  4. Increment the counter at matrix position counter[i][c] += 1.
  5. Query Frequency (item):
  6. Compute hash indices across all \(d\) rows.
  7. Frequency estimate \(= \min_{i=1 \dots d} (\text{counter}[i][h_i(\text{item}) \pmod w])\).
  8. Why Minimum?: Hash collisions only over-count (increment existing counters). Taking the minimum across all rows minimizes the over-counting error caused by hash collisions!

5. Advantages

  • Sub-linear memory: Fixed tiny memory footprint independent of stream size or number of unique items.
  • \(O(1)\) update and frequency query time complexity.
  • Guarantees frequency estimates are never under-counted (\(\text{Estimate} \ge \text{True Count}\)).

6. Limitations

  • Always Over-Estimates: Due to hash collisions, frequency estimates may be higher than actual counts (Zero under-counting error, bounded over-counting error \(\epsilon\)).
  • No Deletions: Standard Count-Min Sketch cannot decrement counts without introducing under-counting errors (requires Count-Med-Me Sketch or Heavy-Hitters extensions).

7. Common interview questions (10)

  1. What is the mathematical intuition behind taking the MIN across rows in Count-Min Sketch?
  2. How does Count-Min Sketch achieve \(O(1)\) bounded memory for infinite streaming data?
  3. How does Caffeine Cache use TinyLFU (based on Count-Min Sketch) to improve cache hit ratios?
  4. What is the difference between Count-Min Sketch and HyperLogLog?
  5. How do array width \(w\) and depth \(d\) determine error bound \(\epsilon\) and confidence \(1 - \delta\)?
  6. Why does Count-Min Sketch guarantee zero under-estimation errors?
  7. How do you find the Top-K Heavy Hitters using a Count-Min Sketch paired with a Min-Heap?
  8. How does a Count-Min Sketch detect DDOS attack IP flows at network switch layers?
  9. What happens to Count-Min Sketch accuracy when stream items have a heavy-tailed Zipfian distribution?
  10. How does a Decaying Count-Min Sketch handle aging counts over time?

8. Common misconceptions

  • Misconception: Count-Min Sketch can return exact counts. Fact: It provides an approximate frequency upper bound (\(\text{True Count} \le \text{Estimate} \le \text{True Count} + \epsilon N\)).
  • Misconception: Count-Min Sketch stores the actual item strings. Fact: Like Bloom Filters, it stores only numeric counters in a 2D matrix; item strings are never stored.

10. 30-second cheat sheet

  • Purpose: Estimate frequency counts of items in streaming data in \(O(1)\) fixed RAM space.
  • Update: Increment counter[i][hash_i(item)] across \(d\) rows.
  • Query: Return MIN(counter[i][hash_i(item)]) across all \(d\) rows.
  • Error Guarantee: Never Under-counts (\(\text{Estimate} \ge \text{True Count}\)).