4.3. Randomness and Accuracy🔗

The random choice is a seed for each hash row. A two-universal family bounds the collision probability of any two distinct items by the reciprocal of the number of buckets. Count-Min needs independent row seeds as well: the guarantee samples a uniform tuple of seeds, rather than reusing one seed across all rows.

For a stream and query fixed before sampling, let M be Cslib.DataStructure.CountMin.mass of the stream and let f be the queried frequency. The theorem Cslib.DataStructure.CountMin.dens_estimate_error_le bounds the probability that the estimate exceeds f + ε * M by (w * ε)⁻¹ ^ d, for positive ε, w, and d. Cslib.DataStructure.CountMin.dens_estimate_error_le_inv_two_pow specializes this to 2⁻ᵈ when 2 ≤ w * ε. With four buckets, three rows, and ε = 1/2, the bound is 1/8. Zero total weight is included and gives an identically zero table.

The concrete family Cslib.DataStructure.CountMin.indexedHash hashes n-bit items to 2^m buckets using a binary matrix with m rows. Its collision guarantee is Cslib.DataStructure.CountMin.isTwoUniversal_indexedHash. Each row of the sketch needs a separate matrix seed with m * n bits.

Cslib.DataStructure.CountMin.sampleSketch is a ProbComp program that calls a supplied seed sampler independently for each row, then processes the stream. Its result stores the seeds and counter table; later queries must use the same hash family. The evaluation theorem assumes that one call to the sampler is exactly uniform. Cslib.DataStructure.CountMin.sampleQuery constructs a sketch and returns one fixed query, and Cslib.DataStructure.CountMin.sampleQuery_error_le_inv_two_pow proves the same failure bound for the actual program's output law.

These results formalize Count-Min's insertion-only point-query guarantee from Cormode and Muthukrishnan, Section 4.1, Theorem 1. They do not cover adaptive updates or queries, deletions, or heavy-hitter enumeration. The table has d * w counters, each at most M, but machine time and bit-space certificates, including the hash seeds, remain separate work. The checked examples include concrete collisions, merging, zero weights, and a universal-hash accuracy instance.