CountMinSketch

A Count-Min sketch: approximate per-item frequency over a stream, in fixed width × depth memory. Think of it as the frequency complement to a Bloom filter — where a Bloom filter answers "is X present?", a Count-Min sketch answers "how often?".

How it works

The sketch holds a depth × width matrix of Long cells. Each of the depth rows uses an independent hash function. add hashes the item into one cell per row and increments those cells. estimate hashes the same way and returns the minimum across rows — the cell least likely to be inflated by hash collisions. The estimate never underestimates the true count.

CRDT merge rule

piece takes the element-wise max of the two count matrices. Max-merge is the convergent, idempotent variant of Count-Min (sometimes called the "conservative" or "max" CMS): a re-delivered patch never inflates the count beyond its highest seen value, so the CRDT satisfies all three lattice laws.

Note: max-merge trades a little accuracy for convergence vs. additive merge. For a single-writer counter without distribution constraints, a plain GCounter is simpler; Count-Min shines when you need frequency estimates for a large or unbounded key space over a P2P mesh.

Error guarantee

For width w and depth d the standard Count-Min error bound holds: the probability that the estimate exceeds the true count by more than ε × N (where ε = e/w, N = total items added across all replicas) is at most δ = e^-d.

For example width = 512, depth = 5 gives ε ≈ 0.005, δ ≈ 0.007.

Hash family

One hash function per row, derived from canonical MurmurHash3_x86_32 (Austin Appleby, public domain). Seed for row i is i (row index), giving each row an independent hash function with proper avalanche. The hash is byte-identical on all Kotlin Multiplatform targets.

Delta format

add produces a sparse delta carrying exactly depth entries — one per hash row. Wire cost per add is O(depth) rather than O(depth × width). At typical dimensions (w=512, d=5) this reduces gossip bandwidth 256× per event. Full-state anti-entropy still uses the complete depth × width matrix; only incremental deltas are sparse.

Use

Analytics, rate-limiting, adaptive routing over a P2P mesh. Works on all kuilt targets: JVM, Android, iOS, macOS, wasmJs.

Parameters

Samples

// width=512, depth=5 → ε ≈ 0.005, δ ≈ 0.007 error bound.
var sketch = CountMinSketch.empty(width = 512, depth = 5)

// add() returns a delta; absorb it with piece().
repeat(10) { sketch = sketch.piece(sketch.add("hello")) }
repeat(3) { sketch = sketch.piece(sketch.add("world")) }

check(sketch.estimate("hello") >= 10L)  // never underestimates
check(sketch.estimate("world") >= 3L)
check(sketch.estimate("unseen") == 0L)  // empty sketch returns 0

var a = CountMinSketch.empty(width = 64, depth = 4)
var b = CountMinSketch.empty(width = 64, depth = 4)

// Two replicas observe different occurrences of the same item.
repeat(7) { a = a.piece(a.add("event")) }
repeat(4) { b = b.piece(b.add("event")) }

// After merging, the merged estimate is >= the max of the two.
val merged = a.piece(b)
check(merged.estimate("event") >= 7L)

// Merging again is idempotent — same result.
check(merged.piece(a) == merged.piece(a).piece(a))