#📝 Note: Count-Min Sketch

#Overview

Count-Min Sketch (CMS) is a probabilistic data structure that estimates the frequency of items in a stream using a fixed-size 2D array of counters. It trades a small, controllable overcount error for dramatically reduced memory — O(1/ε × log(1/δ)) space vs O(N) for exact counting.

#Core Idea

Structure: A 2D array with d rows and w columns. Each row uses an independent hash function.
Update: For item x, compute h_i(x) for each row i, increment table[i][h_i(x)] by count.
Query: For item x, return min(table[i][h_i(x)]) across all rows. The minimum is the best estimate — hash collisions only cause overcount, never undercount.
Error Guarantee: With probability ≥ 1 − δ, the estimated count is within ε × N of the true count (N = total stream elements).

#Parameter Selection

Width  w = ceil(e / ε)    → controls error magnitude (e ≈ 2.718)
Depth  d = ceil(ln(1/δ))  → controls error probability

Example: ε=0.001, δ=0.01
  w = ceil(2.718 / 0.001) = 2718 counters per row
  d = ceil(ln(100))       = 5 rows
  Total: 5 × 2718 = 13,590 integers ≈ 54 KB (32-bit counters)
  → Estimates frequency within 0.1% of total events, 99% of the time

#Comparison: Exact vs Probabilistic Counting

Aspect	HashMap (Exact)	Count-Min Sketch
Memory	O(unique items) — could be GBs	O(1/ε × log 1/δ) — often KBs
Error	None	ε × N overcount (no undercount)
Merge	Trivial	Trivially addable across workers
Distributed	Hard (full map sync)	Easy (add tables element-wise)
Deletions	Supported	Not supported (standard CMS)

#When to Use

Top-K / Heavy Hitters: Pair with a min-heap of size K to track top-K frequent items in a stream (trending topics, popular URLs, hot keys).
Network traffic analysis: Count per-IP packet frequencies without storing every IP.
Database query optimization: Estimate column cardinality for query plan selection.
DDoS detection: Identify IPs exceeding request-rate thresholds in real time.

#When NOT to Use

When exact counts are legally or financially required (billing, audit logs).
When the stream contains deletions (use Count-Min with conservative updates or CMS with deletion support).
When the universe of items is small enough for exact counting to fit in memory.

#Trade-offs

Pros: Sub-linear memory; mergeable across distributed workers; constant-time updates and queries; deterministic error bounds.
Cons: Overcounts (never undercounts) — biased estimator; cannot enumerate all items (only answer point queries); not suitable when you need exact zero-count confirmation.

#Used In This Repo

Twitter Trends (#27) — Frequency estimation for hashtag/phrase occurrence in tweet stream before top-K extraction