Approximation with a Contract: Error, Randomness, and Mergeability in Streaming Sketches

Codex (AI) | Commissioned review v1 | 2026-10-22

Streaming sketches trade exact state for compact summaries with probabilistic or asymptotic error guarantees. Those guarantees differ in direction, norm, randomness, and admissible updates. This review compares Count-Min, CountSketch, and HyperLogLog through a small frequency-summary example. It derives the elementary Count-Min one-sided bound under nonnegative frequencies, distinguishes a fixed-query guarantee from repeated or adaptive use, and explains why mergeability does not imply duplicate-safe merging. Two analytical figures show the memory-accuracy scaling of Count-Min and the asymptotic register-error relation of HyperLogLog. The accompanying program checks overestimation and linear merge behavior on a finite constructed stream; it does not claim a new benchmark or empirical validation of asymptotic constants.

Approximation should be a contract

A frequency estimate can be wrong in only one direction, in either direction, or with a stated probability of exceeding an additive threshold. A distinct-count estimator addresses a different quantity altogether. Calling all of these structures approximate counters obscures the information needed to use them safely.
The contract should identify the stream model, update signs, queried quantity, randomness, and error metric. An error proportional to total stream mass can be acceptable for heavy hitters yet useless for a rare item. A relative cardinality error can be suitable for telemetry but inappropriate for enforcing a hard capacity limit. The decision to use a sketch should begin with the downstream consequence of error, not with a memory reduction ratio alone.

Three primary structures, different guarantees

Cormode and Muthukrishnan's Count-Min sketch uses multiple hashed counters and a minimum estimate, yielding a useful one-sided additive guarantee for nonnegative frequencies. Charikar, Chen, and Farach-Colton's CountSketch uses signed contributions and supports a different frequency-estimation analysis. Flajolet and colleagues' HyperLogLog estimates distinct cardinality using compact register statistics.
We do not reproduce their full analyses or compare their historical benchmark numbers. The purpose of the comparison is to show that the structures summarize different aspects of a stream. A Count-Min frequency table is not a substitute for a cardinality estimator, and a signed estimate does not carry the same one-sided interpretation as a minimum of nonnegative collision counts. Correct use requires choosing the guarantee that matches the question.

References: cs-12-1, cs-12-2, cs-12-3

The Count-Min estimate and its deterministic side

For each row, hash an item into one counter and add its update weight. To estimate an item's frequency, inspect its counter in each row and take the minimum. When all final frequencies are nonnegative, each queried counter equals the item's true count plus nonnegative collision mass. The estimate therefore cannot be below the true count, assuming exact arithmetic and a compatible update model.
This deterministic fact is separate from the probability that collision mass is small. The finite appendix uses a deliberately simple fixed hash family and checks overestimation on a constructed stream. It does not claim that those illustrative hashes meet the theorem's independence requirements. General turnstile streams with negative final frequencies can invalidate the one-sided argument because colliding contributions can cancel rather than only add.

Where the probabilistic bound comes from

For a fixed queried item, a row's expected collision mass is at most the total L1 mass divided by the row width when the hash family has the required collision property. With width at least e divided by epsilon, that expectation is at most epsilon times the L1 mass divided by e. Markov's inequality then bounds the probability that one row exceeds epsilon times the mass by at most one over e.
With independent rows, all rows exceed the threshold with probability at most exp of minus d, where d is the depth. Taking the minimum gives the familiar failure bound when depth is at least the natural logarithm of one over delta. The derivation exposes every dependency: nonnegative mass, a fixed query, appropriate hashing, independent rows, and no counter overflow. Removing one assumption changes the claim.

Fixed-query accuracy is not universal adaptive accuracy

A guarantee for one fixed query does not automatically hold simultaneously for every possible query. For a finite predetermined set of Q queries, a union bound can allocate a smaller per-query failure probability to obtain a desired family-level bound. This may require additional rows.
Adaptive selection is more subtle when queries or updates depend on information revealed by the sketch. The randomness assumptions used in a simple fixed-input analysis may no longer describe that interaction. A service that exposes estimates to an adversarial client should not simply quote a textbook one-query bound as an unlimited adaptive guarantee. The evaluation must state whether the stream and query set are fixed independently of the sketch's random choices and whether seeds are public or private.

Mergeability is linearity, not idempotence

Two Count-Min arrays built with identical dimensions and hash functions can be added to summarize the sum of their frequency vectors. This is useful for distributed aggregation. However, adding the same shard twice doubles its contribution. The merge is not idempotent, so a retrying transport needs shard identities, version control, or another duplicate-prevention mechanism.
HyperLogLog uses a different merge operation based on register maxima under compatible hashing and representation. That operation has different algebraic properties. The lesson is that mergeability is not one universal behavior: the operation, compatibility constraints, and duplicate semantics must be named. A distributed pipeline can use a mathematically correct sketch yet produce incorrect aggregates if it applies the wrong delivery assumptions to its merge.

Cardinality error has a regime of validity

HyperLogLog's familiar relative-standard-error approximation is approximately 1.04 divided by the square root of the number of registers in its asymptotic setting. The second figure plots that expression for register counts from small powers of two through larger arrays. It is labeled as an asymptotic formula, not a guarantee for every cardinality and hash implementation.
Small-cardinality corrections, finite hash width, register representation, and estimator variants affect practical behavior. A relative standard error is also not a deterministic maximum error or a confidence interval by itself. At 16,384 registers, the formula gives about 0.8125 percent. A deployment requiring a specified tail probability must use an appropriate distributional analysis or calibrated evidence rather than treating that standard deviation as an absolute bound.

References: cs-12-2

Counter width and overflow belong in the model

A theoretically compact sketch can still fail if its counters saturate or wrap. Saturation changes the estimator's behavior, while modular wraparound can destroy one-sided overestimation. Weighted updates and long retention windows make this a practical concern even when the number of distinct keys is modest.
The memory budget should include counter width, seeds, metadata, and any structures used to identify candidate heavy hitters. A frequency sketch alone does not necessarily enumerate the keys with large estimates; it answers queries for keys supplied to it. If the application needs a list of heavy hitters, the candidate-generation mechanism must be included in both accuracy and cost. Otherwise the published memory footprint omits a component required to answer the actual question.

A meaningful evaluation separates three errors

Measurement error from a sketch should be separated from ingestion error and query mismatch. Missing records, duplicated shards, or inconsistent time windows can dominate the sketch's probabilistic error. A precise estimator of the wrong stream is still the wrong result.
The proposed protocol retains an exact small-stream oracle, tests compatible and incompatible merges, and includes duplicate delivery and counter-boundary cases. Larger experiments should vary skew, total mass, rare-item frequency, cardinality, and update signs under a declared randomization scheme. Report distributions over independent seeds when the claim depends on randomized hashing. One favorable seed or one convenient Zipf distribution cannot establish broad accuracy across the intended workload.

Conclusion: carry the assumptions into the pipeline

Streaming sketches make large-scale measurement practical by replacing exact state with explicit approximation. Their value depends on preserving the conditions under which the error statement was derived. The update model, query selection, hash independence, arithmetic, and merge protocol are all part of the result.
The finite example shows both a useful one-sided property and the duplication hazard of additive merging. The analytical curves explain how memory changes nominal accuracy without pretending to be deployment measurements. A defensible system uses these mathematical contracts to design its ingestion and query paths, then tests the complete measurement pipeline against an exact oracle wherever feasible.

Executed finite checks

Toy Count-Min insertion, merge and signed-stream counterexample

13 assertions passed.

Fixed explicit hashes; no probabilistic hash guarantee or HyperLogLog implementation is claimed.

{
  "positive_updates": [
    [
      0,
      3
    ],
    [
      1,
      2
    ],
    [
      4,
      5
    ],
    [
      2,
      7
    ],
    [
      7,
      1
    ]
  ],
  "signed_estimate": -2,
  "true_frequency": 3
}

Code: analysis/examples.py; results: analysis/example-results.json

Equations

(1) \hat f_i=\min_{1\le j\le d} C_{j,h_j(i)}

Count-Min estimate with compatible row hashes and exact counters.

(2) f_i\le\hat f_i\le f_i+\varepsilon\|f\|_1\quad\text{with probability at least }1-\delta

Fixed-query bound for nonnegative frequencies and the required random hash assumptions; the lower bound is deterministic under exact arithmetic.

(3) w=\lceil e/\varepsilon\rceil,\qquad d=\lceil\log(1/\delta)\rceil

Sufficient Count-Min width and depth for the stated bound; total counter count is wd.

(4) \mathrm{RSE}_{\mathrm{HLL}}\approx\frac{1.04}{\sqrt m}

Asymptotic relative standard error for m registers in the classical HyperLogLog analysis; not a universal maximum-error guarantee.

Analytical figures

Figure 1. Width sets a Count-Min error scale

Standard insertion-only Count-Min sizing relation. A probability guarantee additionally needs appropriate independent hashing and depth; the toy appendix hashes do not establish that guarantee.

figures/streaming-sketches-1.csv

Figure 2. HyperLogLog trades registers for precision

Classical approximate error scale under suitable hashing and asymptotic conditions. Small-cardinality corrections, bias and implementation choices are excluded.

figures/streaming-sketches-2.csv

Comparison

Structure | Question answered | Important boundary

Count-Min | Frequency of a supplied key | Nonnegative-frequency and hash assumptions; additive merge duplicates

CountSketch | Signed frequency estimation | Different error norm and two-sided behavior

HyperLogLog | Number of distinct values | Asymptotic regime and compatible hashing

Distributed aggregation | Summary of a defined stream | Exactly which shards, versions, and windows are included

Proposed validation protocol

1. Build an exact oracle for a finite stream and compare every queried key.

2. Check nonnegative overestimation and a general-turnstile negative control separately.

3. Verify linear merge for disjoint shards with identical hash configuration.

4. Demonstrate that duplicate additive merging changes the answer.

5. Test counter overflow, incompatible seeds, and candidate-key enumeration requirements.

6. Use multiple independent seeds and workload regimes for any empirical accuracy claim.

Limitations

1. The fixed illustrative hash family is not presented as satisfying the probabilistic theorem.

2. The HyperLogLog figure is an asymptotic formula, not an implementation benchmark.

3. General adaptive robustness and every turnstile variant are outside scope.

4. The Count-Min source's bibliographic identity was verified; full original text was not retrieved in this session.

Research questions

1. Does the actual stream satisfy the update and randomness assumptions of the chosen bound?

2. Can duplicate shard delivery overwhelm the nominal approximation error?

3. Does the application need a fixed-query estimate, simultaneous guarantees, or adaptive robustness?

Source evidence

cs-12-1: Count-Min provides a compact frequency summary with a useful additive error analysis.

Boundary: The one-sided interpretation requires nonnegative frequencies and appropriate hashing.

Locator: Author-hosted manuscript, sections 3 and 4.1, Theorem 1; publication-version note retained.

cs-12-2: HyperLogLog analyzes compact cardinality estimation and its register-based error scaling.

Boundary: Small-range behavior and practical variants require their own treatment.

Locator: Publisher record and classical cardinality-estimation analysis.

cs-12-3: CountSketch estimates frequencies using signed hashed summaries.

Boundary: Its guarantee differs from Count-Min's nonnegative collision bound.

Locator: Abstract and frequency-summary construction.

References

cs-12-1. Graham Cormode, S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms (2005). https://www.cs.ox.ac.uk/people/graham.cormode/pubs/papers/cm-full.pdf | DOI: 10.1016/j.jalgor.2003.12.001

cs-12-2. Philippe Flajolet, Éric Fusy, Olivier Gandouet, Frédéric Meunier. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. Discrete Mathematics & Theoretical Computer Science (2007). https://dmtcs.episciences.org/articles/3545 | DOI: 10.46298/dmtcs.3545

cs-12-3. Moses Charikar, Kevin Chen, Martin Farach-Colton. Finding Frequent Items in Data Streams. Lecture Notes in Computer Science; Automata, Languages and Programming (2002). https://www.cs.yale.edu/homes/el327/datamining2011aFiles/FindingFrequentItemsInDataStreams.pdf | DOI: 10.1007/3-540-45465-9_59

cs-12-1 access: Author-hosted manuscript retrieved; sections 3 and 4.1, including the sizing rule and Theorem 1, inspected. The accessible manuscript is dated December 2003; the bibliography identifies the 2005 journal publication.

Version note: The linked author manuscript predates the 2005 journal publication. This article uses the matching Count-Min construction and fixed-query nonnegative-frequency bound; it does not claim a complete version-difference audit.

cs-12-2 access: Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

cs-12-3 access: Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

Provenance

A focused analytical review of three selected foundational primary sources, with original worked examples. This is not an exhaustive or systematic survey of the literature through 2026. Source access and version notes are recorded with the bibliography.

Written and technically self-reviewed by Codex (AI). References identify the original researchers; the analytical constructions and proposed evaluation designs are attributed to this article.

Covers are conceptual ImageGen illustrations. Technical figures are computed from declared models or finite examples, with Python and CSV supplied. They are not measurements of deployed products or reproduced performance benchmarks.

This local draft has no independent peer-review or journal-acceptance record. Bounded executable examples check the stated small models; they are not formal verification of the cited systems.