Streaming Algorithms for Data That Does Not Fit in Memory

A stream changes the algorithmic contract. When events cannot be retained, an algorithm cannot sort the complete input, revisit arbitrary records, or allocate one map entry per distinct key. It must summarize the past in one or a few passes. The central question is which property of the full data can be preserved within a fixed memory and error budget?

That question leads to different summaries for different jobs. Reservoir sampling preserves an unbiased sample without knowing the final length. Count-Min Sketch estimates frequencies with one-sided additive error. HyperLogLog estimates distinct cardinality from the distribution of hash values. None reconstructs the stream, and none is universally interchangeable with the others. Their value comes from narrow, explicit guarantees that survive inputs far larger than memory.

This article derives those guarantees through telemetry examples and treats mergeability, hostile inputs, and verification as part of the interface. Approximation should be explicit enough to budget and test.

Define the Streaming Contract First #

Let a stream be a sequence $x_1, x_2, \ldots, x_n$, where $n$ may be unknown until the stream ends. A strict streaming algorithm updates a state $S_t$ from the previous state and the next item:

The state must be substantially smaller than the input, commonly bounded by an accuracy parameter rather than by $n$. This rules out an exact frequency map when the key space can grow without limit. Calling that map “streaming” because it consumes an iterator only changes the input API; its memory still grows with distinct cardinality.

The contract must name the query, byte and update budget, number of passes, error model, and composition needs. Sampling records, estimating a supplied key’s count, and counting distinct keys are different queries. Error may be additive or relative, one- or two-sided, and deterministic or probabilistic. Summaries may also need to merge across partitions or windows.

An error statement needs a probability as well as a magnitude. “Approximately 10,000” is not a guarantee. A useful contract says, for example, that an estimated frequency exceeds the true frequency by at most $\epsilon N$ with probability at least $1-\delta$, where $N$ is the total number of updates. The caller then chooses whether that uncertainty is acceptable for dashboard ranking, abuse detection, billing, or neither.

These structures naturally summarize updates since initialization. A last-hour report instead needs time buckets, expiration, or a window algorithm; resetting one global summary creates boundary artifacts. Deletion is also not automatic: arbitrary negative corrections can invalidate a structure designed for positive increments.

Finally, hashes are part of correctness, not incidental plumbing. Their output must be sufficiently uniform for the proof assumptions, consistently encoded across producers, and versioned if summaries persist. A hash change halfway through a period makes old and new states mathematically incompatible even when their serialized shapes match.

Sample an Unknown Stream with a Reservoir #

Suppose an operations team wants 100 representative request traces from a day, but the service may produce billions and the daily total is unknown. Taking the first 100 favors startup traffic. Keeping each event with fixed probability produces a variable-size sample and still requires knowing how much storage to provision. Reservoir sampling maintains exactly $k$ items and gives every observed item the same inclusion probability.

For reservoir size $k$, retain the first $k$ items. When one-based item $i>k$ arrives, draw $j$ uniformly from $1$ through $i$. Replace slot $j$ when $j\le k$; otherwise discard the item. An implementation needs only the item array, a count of items seen, and an injectable random source. It must reject invalid capacities and avoid biased integer selection.

The proof is an invariant. After processing $i$ items, every one appears in the reservoir with probability $k/i$. The new item is selected with probability $k/i$. An older item was present before with probability $k/(i-1)$ and survives this update unless its particular slot is replaced. That survival probability is $1-1/i$, giving

Consider a reservoir of two over events A, B, C, D. A and B begin in the reservoir. At C, each of the three events has probability $2/3$ of being retained. At D, the new event enters with probability $2/4$, while each prior event has inclusion probability $(2/3)(3/4)=1/2$. The algorithm does not make every run look balanced; it makes inclusion unbiased across repeated runs.

Sampling records is not sampling users: heavy users produce more records. Uniform user or weighted sampling needs a different design. A basic reservoir is also awkward to merge; equal-size reservoirs from unequal partitions cannot simply be concatenated and truncated. Retain partition counts for a valid weighted merge, or use reproducible random priorities.

Estimate Frequencies with Count-Min Sketch #

A Count-Min Sketch answers a different question: “How many times has key $q$ appeared?” It stores a matrix of counters with width $w$ and depth $d$. Each row has an independent hash function. Updating key $q$ increments one counter per row; querying returns the minimum of those counters.

Every counter includes the true updates for $q$, so with nonnegative increments the estimate can never be below the true count. Collisions add counts from other keys. Taking the minimum chooses the row with the least collision noise. With conventional dimensions $w=\lceil e/\epsilon \rceil$ and $d=\lceil \ln(1/\delta) \rceil$, the estimate obeys

with probability at least $1-\delta$. The guarantee is additive in total stream weight $N$, not relative to the queried key. A rare key in a huge stream can therefore have a large relative error even when the sketch meets its contract exactly.

For $N=1,000,000$ route observations, $\epsilon=0.001$ permits 1,000 collision overcount at the stated confidence. That can identify very hot routes but cannot distinguish counts of 7 and 12. Such a query needs a smaller $\epsilon$, more memory, or an exact method.

Count-Min Sketch finds a candidate’s frequency only when given the candidate. It does not enumerate keys because it does not retain them. A top-k system therefore needs a bounded candidate mechanism alongside the sketch, such as a heap updated from a controlled key set or a heavy-hitter algorithm. Retaining every key “just for enumeration” would reintroduce unbounded memory.

Counter width is a hard limit: saturation avoids wraparound but loses future information, while wider counters cost memory. Conservative update may reduce practical overestimation, but has separate behavior and merge rules. Negative updates break the simple one-sided guarantee and require a turnstile-stream design.

Estimate Distinct Values with HyperLogLog #

Counting unique users exactly requires remembering which users have appeared. HyperLogLog instead observes a property of uniform hashes: long prefixes of zero bits are rare. If a hash begins with one zero before its first one, that occurs often; a prefix of twenty zeros occurs roughly once per million independent hashes. The longest observed prefix therefore carries information about how many distinct values were seen.

A single maximum has high variance, so HyperLogLog splits hashes into $m=2^p$ registers. The first $p$ bits choose a register; the remaining bits determine a rank, usually one plus the number of leading zeros. Each register stores its maximum rank. The cardinality estimate combines all registers with a bias-corrected harmonic mean. Its relative standard error is approximately

This is a standard deviation, not a deterministic maximum. With $m=16,384$, the expression is about $0.0081$, or 0.81%. Saying “the error is always below 0.81%” would be false. Results vary around the true cardinality, and implementation-specific corrections matter especially for very small or very large ranges.

Suppose events contain (tenantId, userId) and a dashboard needs daily distinct users per tenant. Give each admitted tenant bucket a sketch, hash a canonical userId, and update one register per event. Repeated users produce the same hash and stop changing that register after its maximum. If tenant count is unbounded, the outer allocation still needs admission, eviction, or fixed partitioning.

HyperLogLog cannot list the distinct users, prove that one user appeared, or remove a user exactly. It estimates cardinality only. Hashing truncated identifiers or inconsistent text normalization changes the domain being counted. For example, lowercasing user IDs may merge identities that the source system treats as distinct. Canonicalization must be specified before hashing, and the same hash seed and precision must be used by every merge participant.

Merge Summaries Without Replaying Events #

Mergeability is what turns these structures from single-process tricks into distributed algorithms. If summaries form a mergeable algebra, workers can process partitions independently and combine bounded states without shipping raw events.

Count-Min Sketches with identical dimensions, hash functions, seeds, and counter semantics merge by element-wise addition. The result represents the concatenation of the streams. HyperLogLog sketches with identical precision and hashing merge by taking the maximum for each register. Both operations are associative and commutative, which permits tree reductions and retry-safe recomputation when duplicate summary application is prevented by the surrounding protocol.

Serialization metadata must include algorithm version, precision or dimensions, hash identity, seed identity, counter width, window, and domain encoding. Checking only byte length is unsafe: two sketches can have matching shapes but incompatible hash functions. Reject incompatible merges rather than silently manufacturing a plausible number.

Merging is not necessarily idempotent delivery. Adding one Count-Min Sketch twice doubles its contribution. HyperLogLog maxima are idempotent, but duplicate work can still conceal inconsistent windows. Give each partition summary a stable identity and track aggregate membership.

Reservoirs need more care because naive union followed by uniform truncation gives partitions equal influence regardless of their original sizes. Either use a proven weighted merge based on each partition’s observed count or assign every item a random priority and retain the globally best $k$ priorities. Mergeability is an algorithm choice, not a flag added after deployment.

Defend Against Adversarial and Pathological Inputs #

Probabilistic guarantees assume something about randomness. If an attacker can choose keys after learning weak hash functions, they may force collisions in Count-Min Sketch or distort HyperLogLog registers. Use a keyed, well-distributed hash where inputs are adversarial, keep the key outside client control, and support rotation at summary boundaries. A fast non-cryptographic hash can be appropriate for trusted telemetry, but its collision behavior still needs validation against the actual encoding and key distribution.

Reservoir randomness must avoid biased slot selection. Inject and record a seeded generator for reproducibility; use a threat-appropriate generator for security-sensitive sampling. Those goals may require different implementations.

Operational failures include normalization drift, non-atomic window rollover, counter overflow, unbounded per-customer allocation, and interpreting additive error as a relative percentage. Sparse traffic may be cheaper to keep exactly, while late events need an explicit correction policy.

Hybrid implementations can use exact sparse state at low cardinality and convert to a sketch past a threshold, but the transition must preserve semantics and be one-way or carefully versioned. Compression of empty registers or zero counters saves storage but should not alter query results. Put hard limits on the number of live summaries, serialized size, accepted update weight, and window age.

Verify Guarantees Statistically and Operationally #

Example-by-example equality tests are insufficient for randomized summaries. Tests should separate deterministic invariants from distributional claims. Deterministic tests can assert that a reservoir never exceeds capacity, Count-Min estimates never decrease under positive updates, HyperLogLog registers only increase, and compatible merges equal a summary built over the concatenated input within the algorithm’s exact state semantics.

Use tiny exact oracles. Generate streams small enough to retain, then compare estimated counts and cardinalities with a Map or Set. Exercise empty input, one item, all-identical input, all-distinct input, highly skewed frequencies, partitioned input, maximum update weights, and serialization round trips. Test incompatible merge metadata as an expected rejection.

Distributional tests require repeated trials. For a two-item reservoir over ten labels, use many seeds and compare inclusion rates with a tolerance based on trial count. Exercise multiple Count-Min hash families against the promised failure rate, and test HyperLogLog error across cardinalities around representation transitions rather than blessing one estimate.

Avoid flaky tests by fixing a matrix of seeds and streams, not by fixing one random output forever. A golden serialized state can detect accidental format changes, while property tests check mathematical behavior. Keep those purposes separate so an intentional version migration does not require weakening correctness tests.

Monitor update rate, allocated summaries, rejected merges, saturation, register distribution, window lag, serialized size, and algorithm versions. Where feasible, shadow a bounded sample into an exact oracle and alert on systematic error beyond the contract, not every random deviation.

Choose the Smallest Honest Summary #

The three techniques answer different questions:

Use an exact algorithm when the domain is naturally bounded, the result drives money or authorization, or the approximation budget is smaller than the structure can support. A fixed array indexed by a known small enum beats a sketch: it is simpler, exact, and often smaller. Approximation earns its complexity only when input scale or cardinality makes exact state genuinely infeasible.

When approximation is justified, derive memory from $\epsilon$, $\delta$, reservoir capacity, or HLL precision. Version hashing and serialization, define window and late-event behavior, state retry semantics, and describe uncertainty unambiguously.

Streaming algorithms succeed by discarding information deliberately. Reservoir sampling discards records while preserving unbiased inclusion. Count-Min Sketch discards key identity while bounding collision overcount for supplied queries. HyperLogLog discards identities while preserving a statistical cardinality signal. The engineering discipline is to name what was discarded, quantify what remains, and continuously verify that real inputs still satisfy the assumptions behind the guarantee.