Architecture & $(\varepsilon, \delta)$ Markov Proof of the Count-Min Sketch
Given a stream of updates $(x_t, c_t)$ with non-negative increments $c_t > 0$ and total stream weight $N = \sum_t c_t$, a Count-Min Sketch allocates a 2D array $C[0..d-1][0..w-1]$ of integer counters initialized to $0$, paired with $d$ hash functions $h_0, \dots, h_{d-1}: \mathcal{U} \to \{0, \dots, w-1\}$ chosen independently from a pairwise-independent (2-universal) family.
update(x, c): For each row $j \in \{0, \dots, d-1\}$, increment $C[j][h_j(x)] \mathrel{+}= c$.estimate(x): Return $\hat{f}_x = \min_{0 \le j < d} C[j][h_j(x)]$. Because all increments are non-negative, every row $C[j][h_j(x)]$ equals the true frequency $f_x$ plus colliding traffic from other keys, so $\hat{f}_x \ge f_x$ always holds (one-sided overestimation error).- Conservative Update (Estan & Varghese, 2002): For positive-only streams, instead of blindly incrementing all $d$ rows, first compute the current estimate $\hat{f}_x = \min_j C[j][h_j(x)]$, set the new target $\text{new\_val} = \hat{f}_x + c$, and update each row to $C[j][h_j(x)] \gets \max(C[j][h_j(x)], \text{new\_val})$. This strictly preserves $\hat{f}_x \ge f_x$ while cutting empirical overestimation error by $2\times$ to $5\times$!
| Streaming Algorithm | Space Complexity | Update / Query Time | Error Guarantee ($N = \|f\|_1$) | Supports Negative Updates? |
|---|---|---|---|---|
| Count-Min Sketch (CMS) | $O\left(\frac{1}{\varepsilon} \ln \frac{1}{\delta}\right)$ counters | O(d) = O(ln(1/δ)) | $f_x \le \hat{f}_x \le f_x + \varepsilon N$ (w.p. $1-\delta$) | Yes (Median query if negative) |
| CMS + Conservative Update | $O\left(\frac{1}{\varepsilon} \ln \frac{1}{\delta}\right)$ counters | O(d) = O(ln(1/δ)) | Strictly tighter $\hat{f}_x$ in practice | No (Positive increments only) |
| Count Sketch (Charikar et al.) | $O\left(\frac{1}{\varepsilon^2} \ln \frac{1}{\delta}\right)$ counters | O(d) = O(ln(1/δ)) | $|\hat{f}_x - f_x| \le \varepsilon \|f\|_2$ (Unbiased $\ell_2$) | Yes (Uses $\pm 1$ sign hashes) |
| Misra-Gries / Space-Saving | $O(1/\varepsilon)$ exact slots | O(1) (Hash + Bucket) | Deterministic heavy hitters $\ge \varepsilon N$ | No (Insertion-only streams) |
Formal Proof: Why $w = \lceil e / \varepsilon \rceil$ and $d = \lceil \ln(1/\delta) \rceil$ Bound Error
Fix a query key $x$ and a single row $j$. Let $X_j = C[j][h_j(x)] - f_x = \sum_{y \ne x} f_y \cdot \mathbb{I}[h_j(y) = h_j(x)]$ be the excess noise in row $j$ caused by collisions. Because $h_j$ is chosen from a 2-universal family, $\Pr[h_j(y) = h_j(x)] \le 1/w$. By linearity of expectation:
$$\mathbb{E}[X_j] = \sum_{y \ne x} f_y \Pr[h_j(y) = h_j(x)] \le \frac{1}{w} \sum_{y \ne x} f_y \le \frac{N}{w} = \frac{\varepsilon N}{e}$$
Since $X_j \ge 0$ (all frequencies are non-negative), Markov's Inequality yields for row $j$:
$$\Pr[X_j > \varepsilon N] \le \frac{\mathbb{E}[X_j]}{\varepsilon N} \le \frac{\varepsilon N / e}{\varepsilon N} = \frac{1}{e}$$
Because the $d$ rows use mutually independent hash seeds, $\hat{f}_x - f_x = \min_j X_j > \varepsilon N$ occurs if and only if every single row $j \in \{0, \dots, d-1\}$ exceeds $\varepsilon N$ simultaneously:
$$\Pr[\hat{f}_x > f_x + \varepsilon N] = \prod_{j=0}^{d-1} \Pr[X_j > \varepsilon N] \le \left(\frac{1}{e}\right)^d = e^{-\lceil \ln(1/\delta) \rceil} \le \delta$$
Visualizing the $d \times w$ Count-Min Matrix & Conservative Update
Step through Count-Min Sketch d × w counter updates and point query f̂(x) = min_j C[j, h_j(x)] (eliminating additive collision noise), or trace HyperLogLog leading-zero registers M[j] = max ρ(w) and Harmonic Mean cardinality estimation.
Invariant & State
Hardware Reality: Flat Power-of-Two Row Alignment & Linear Mergeability
When implementing Count-Min Sketch in C++ or Rust, rounding the width $w = \lceil e / \varepsilon \rceil$ up to the next power of two $W = 2^r$ replaces slow modulo arithmetic with a single bitwise mask h & (W - 1) and allows all $d$ rows to be stored in a single contiguous 1D allocation table[(j << r) | (h & (W - 1))]. Furthermore, standard CMS (without conservative update) is a linear sketch: two sketches $C^{(A)}$ and $C^{(B)}$ computed on separate CPU cores or data centers with the same seeds can be merged in-place via vectorized SIMD addition $C^{(A+B)} = C^{(A)} + C^{(B)}$ (_mm256_add_epi64).
Production C++20 Implementation: Count-Min Sketch with Conservative Update & Heavy-Hitter Heap
// C++20: Count-Min Sketch with Power-of-2 Width, Conservative Update & Distributed Merge
#include <vector>
#include <cstdint>
#include <algorithm>
#include <limits>
#include <bit>
#include <cmath>
class CountMinSketch {
uint32_t depth_;
uint32_t width_; // Power of 2 >= ceil(e / eps)
uint32_t widthMask_;
uint32_t widthShift_;
std::vector<uint64_t> table_;
std::vector<uint64_t> seeds_;
uint32_t hashRow(uint64_t key, uint32_t row) const noexcept {
uint64_t x = key ^ seeds_[row];
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return static_cast<uint32_t>(x ^ (x >> 31)) & widthMask_;
}
public:
CountMinSketch(double epsilon, double delta) {
uint32_t rawW = static_cast<uint32_t>(std::ceil(2.718281828459045 / epsilon));
width_ = std::bit_ceil(std::max(16U, rawW));
widthMask_ = width_ - 1;
widthShift_ = std::countr_zero(width_);
depth_ = std::max(1U, static_cast<uint32_t>(std::ceil(std::log(1.0 / delta))));
table_.assign(static_cast<size_t>(depth_) * width_, 0ULL);
seeds_.resize(depth_);
for (uint32_t j = 0; j < depth_; ++j) {
seeds_[j] = 0x9e3779b97f4a7c15ULL * (j + 1) + 0x6a09e667f3bcc908ULL;
}
}
// Standard linear update (supports distributed sketch addition & deletions)
void updateLinear(uint64_t key, uint64_t count = 1) noexcept {
for (uint32_t j = 0; j < depth_; ++j) {
uint32_t col = hashRow(key, j);
table_[(static_cast<size_t>(j) << widthShift_) | col] += count;
}
}
// Conservative update: tightens accuracy by only raising counters to min_est + count
uint64_t updateConservative(uint64_t key, uint64_t count = 1) noexcept {
uint64_t target = estimate(key) + count;
for (uint32_t j = 0; j < depth_; ++j) {
uint32_t col = hashRow(key, j);
uint64_t& cell = table_[(static_cast<size_t>(j) << widthShift_) | col];
if (cell < target) cell = target;
}
return target;
}
uint64_t estimate(uint64_t key) const noexcept {
uint64_t ans = std::numeric_limits<uint64_t>::max();
for (uint32_t j = 0; j < depth_; ++j) {
uint32_t col = hashRow(key, j);
ans = std::min(ans, table_[(static_cast<size_t>(j) << widthShift_) | col]);
}
return ans;
}
};Failure Modes & Adversarial Pitfalls
- Using Conservative Update When Deletions or Linear Sketch Merging Are Required: Conservative update is non-linear: if you apply conservative updates and later subtract counts on deletion, or add two conservatively updated sketches from two servers together, the invariant $\hat{f}_x \ge f_x$ is violated and you can suffer underestimation errors! Use standard
updateLinearwhenever deletions or distributed sketch merges are required. - Taking the Minimum When Negative Updates (Turnstile Model) Are Present: In turnstile streams where keys can be both incremented and decremented ($c_t \in \mathbb{Z}$) with bounded negative noise, taking the
minfails if a colliding key had a net negative update. In the general turnstile model, query the median across rows (or use Charikar's Count Sketch with $\pm 1$ Rademacher sign hashes).