Project: audit four bounded stream views

Last updated: 3 Oct 202630 min read

project

A monitoring service receives a stream too large to retain in its request process. It needs four different views: likely high-frequency incident codes, count ranges for ranked candidates, an approximate number of unique incident IDs across regions, and a small event sample for human review. Build four independent reference checks before combining the views. Keep exact counts and an exact ID set only inside the test reference. A bounded production summary cannot recover every original event. Define whether each input is an event position, an incident code, or a unique ID; mixing those units produces convincing but false conclusions. Save the four bounded states independently and never report an estimate as a verified count.

Acceptance trace

Feed eleven incident codes with pump-47 appearing six times, valve-19 and sensor-61 twice each, and grid-83 once. With two slots, pump-47 must survive Misra–Gries because six exceeds eleven divided by three. For every tracked Space-Saving key, assert exact frequency is between estimate minus error and estimate. Feed one hundred region IDs beginning at 47 and another one hundred beginning at 97; after merging same-precision HyperLogLog registers, compare the estimate with the exact union size 150 but do not require equality. Sample four positions from twenty arriving events using a fixed seed, then repeat across many independent seeds to assess inclusion rates.

Expected review record

verified-heavy-hitter=pump-47 exact-count=6
region-union-exact=150 estimate=approximate
sample-size=4 stream-length=20

Boundary and cost review

Test zero and invalid capacities, a stream shorter than the reservoir, duplicate IDs, candidate false positives, estimate bounds after every Space-Saving replacement, and a HyperLogLog merge with mismatched precision. State that the two frequency summaries are insertion-only, the distinct sketch is hash-dependent and approximate, and the sample is uniform over positions under random draws. Compare their memory with exact dictionaries or sets. If replay is impossible, Misra–Gries candidates cannot be verified by a second pass; the system must either store exact counts elsewhere or clearly show an unresolved candidate list.

Common Mistakes

Do not report candidate keys as verified threshold winners.
Do not discard Space-Saving error bounds.
Do not interpret an HLL estimate as an exact union count.
Do not confuse event sampling with unique-entity sampling.

Connected lessons

data structures

projects