Count-min sketch

Deep dive

How it works

In: an item (hashed to 64 bits) and a count · Out: an estimated frequency, at most ε·N too high · State: a d × w grid of counters plus the total N · Cost: O(d) per update or query; 54 KB for ε = 0.1 %, δ = 1 %

          col: h_i(x) mod w
row 0: [ 3 | 0 | 12 | 1 | ... ]
row 1: [ 0 | 7 | 2  | 9 | ... ]     estimate(x) = min over rows of row_i[h_i(x)]
row 2: [ 5 | 1 | 0  | 4 | ... ]

1. Choose ε (error as a fraction of N) and δ (failure probability); set w and d.
2. Update(x, c): for each row i, T[i][h_i(x)] += c.
3. Conservative update: est = min_i T[i][h_i(x)]; set each T[i][h_i(x)] = max(T[i][h_i(x)], est + c). Same guarantee, much less overestimation, but no longer supports deletes or merges exactly.
4. Query(x): min_i T[i][h_i(x)].
5. Heavy hitters: on each update, query the estimate; keep a min-heap of the top k items whose estimate exceeds the heap minimum.
6. Aging: halve all counters every W updates to track recent frequency (TinyLFU).

Code

fn fmix64(mut x: u64) -> u64 {
    x ^= x >> 33; x = x.wrapping_mul(0xFF51_AFD7_ED55_8CCD);
    x ^= x >> 33; x = x.wrapping_mul(0xC4CE_B9FE_1A85_EC53);
    x ^ (x >> 33)
}

pub struct CountMin { w: usize, d: usize, t: Vec<u32>, total: u64 }

impl CountMin {
    pub fn new(eps: f64, delta: f64) -> Self {
        let w = (std::f64::consts::E / eps).ceil() as usize;
        let d = (1.0 / delta).ln().ceil().max(1.0) as usize;
        CountMin { w, d, t: vec![0; w * d], total: 0 }
    }

    // Row i column via double hashing from one 64-bit hash: g_i = h1 + i*h2 (h2 odd).
    #[inline]
    fn cell(&self, h: u64, i: usize) -> usize {
        let (h1, h2) = (h, fmix64(h) | 1);
        let g = h1.wrapping_add((i as u64).wrapping_mul(h2));
        i * self.w + ((g as u128 * self.w as u128) >> 64) as usize // [0, w) without division
    }

    pub fn estimate(&self, h: u64) -> u32 {
        (0..self.d).map(|i| self.t[self.cell(h, i)]).min().unwrap()
    }

    /// Plain update: supports merge and (with i64 counters) deletions.
    pub fn add(&mut self, h: u64, c: u32) {
        for i in 0..self.d {
            let j = self.cell(h, i);
            self.t[j] = self.t[j].saturating_add(c);
        }
        self.total += c as u64;
    }

    /// Conservative update: raise only counters below the new estimate.
    pub fn add_conservative(&mut self, h: u64, c: u32) {
        let target = self.estimate(h).saturating_add(c);
        for i in 0..self.d {
            let j = self.cell(h, i);
            if self.t[j] < target { self.t[j] = target; }
        }
        self.total += c as u64;
    }

    pub fn merge(&mut self, o: &CountMin) {
        assert!(self.w == o.w && self.d == o.d);
        for (a, b) in self.t.iter_mut().zip(&o.t) { *a = a.saturating_add(*b); }
        self.total += o.total;
    }

    /// Exponential decay: call every W updates to favour recent items.
    pub fn halve(&mut self) {
        for x in &mut self.t { *x >>= 1; }
        self.total /= 2;
    }

    pub fn error_bound(&self) -> f64 { std::f64::consts::E / self.w as f64 * self.total as f64 }
}

Complexity and constants

• Update: d hash-derived indexes and d increments; with the sketch in L1/L2, order of 5-20 ns. Out of cache, d independent misses.
• On Zipf-skewed data (typical), actual error is far below ε·N; for skew z > 1 the needed width shrinks to about O(ε^{-1/z}).
• Conservative update typically reduces mean overestimate by a large factor (often 2-10×) on skewed streams; measure on your data.

Efficiency

• Cost: an update or query touches d counters (d = 5 at δ = 1 %): order of 5-20 ns with the sketch in L1/L2, d independent misses out of cache. Memory is fixed: 54 KB at ε = 0.1 %, δ = 1 %; Caffeine's cache-admission sketch uses 4-bit counters, 16 per u64, and one cache line per item. Bound: memory latency.
• Levers:
  • all d counters in one 64-byte block — d misses become 1 (Caffeine design, as described above) — large sketches
  • conservative update — lower overestimation, often 2-10× on skewed streams (order of; measure) — no deletes or exact merges needed
  • 4-bit saturating counters with aging — 8× less memory than u32 (TinyLFU, Einziger et al. 2017) — only relative popularity matters
  • merge by cell-wise addition — sketches built per shard, combined later (Cormode-Muthukrishnan 2005) — distributed streams
  • narrower w on skewed data — the width needed shrinks for Zipf skew z > 1 (Cormode-Muthukrishnan 2005) — skewed keys
• Naive → standard → state of the art:
  • hash map with one counter per distinct item · memory grows with distinct items
  • count-min sketch, u32 counters · fixed O((1/ε)·ln(1/δ)) counters, d probes
  • blocked 4-bit sketch with conservative update and halving · 1 cache line per update, 16 counters per u64

Implementation notes

• One 64-bit hash per item, then double hashing per row (as above), is enough in practice.
• Make w a power of two and use masks if you derive columns from independent bit slices of a 128-bit hash; otherwise use the multiply-shift reduction.
• Cache admission sketches (Caffeine) pack 16 4-bit counters per u64, use 4 rows inside one 64-byte block per item for one cache miss, and halve all counters when the sample count reaches 10× the cache size.
• Counter width: u32 for most streams; u16/4-bit saturating counters when only relative popularity matters.
• For heavy hitters, Space-Saving / Misra-Gries give deterministic guarantees with O(k) counters and are often simpler.
• Keep total (N) to report the error bound alongside each estimate.

Pitfalls

• Querying rare items and trusting the number: the estimate for an item never seen can be ε·N.
• Merging sketches built with different seeds, widths or update rules (conservative-update sketches are not exactly mergeable).
• Integer overflow on hot counters; saturate.
• Using d rows from correlated hashes (e.g. h + i instead of h1 + i·h2): rows collide together and the min stops helping.
• Forgetting aging in long-running services: counts converge to all-time popularity, not current.

Variants and alternatives

In production

• Caches and databases: Caffeine (TinyLFU frequency sketch, 4-bit counters), Apache Spark (org.apache.spark.util.sketch.CountMinSketch), RedisBloom (CMS.INITBYDIM, CMS.INCRBY).
• Networking: traffic measurement for elephant flows and top talkers (Estan and Varghese 2002; conservative update comes from there); network telemetry systems.
• Streaming analytics: Twitter Algebird (Scala).

Implementations

Sources

• Graham Cormode, S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms 55(1), 2005. paper · pdf
• Cristian Estan, George Varghese, New Directions in Traffic Measurement and Accounting, SIGCOMM 2002 (conservative update). paper
• Moses Charikar, Kevin Chen, Martin Farach-Colton, Finding Frequent Items in Data Streams, ICALP 2002 (Count sketch). paper
• Ahmed Metwally, Divyakant Agrawal, Amr El Abbadi, Efficient Computation of Frequent and Top-k Elements in Data Streams, ICDT 2005 (Space-Saving). paper
• Gil Einziger, Roy Friedman, Ben Manes, TinyLFU: A Highly Efficient Cache Admission Policy, ACM Transactions on Storage, 2017. paper · arXiv · code