Streaming algorithms compute useful answers from data that arrive sequentially while retaining much less information than the complete input. They make it possible to count, sample, find frequent items and estimate distributions when keeping every observation is too expensive. The central question is precise: which future questions can a small stored state still answer correctly, or within a declared error bound?
The gold standard is a summary with a clear query, a stated update model, an honest memory budget and a guarantee that survives the way the summary is actually used. A fast dashboard is not enough. Its numbers must mean what the reader thinks they mean, including whether they describe events or people, all history or a recent window, and exact values or estimates.
This guide belongs to the Gold Standard collection and connects to the How X Works hub. Its neighbouring subject, Online Algorithms, studies decisions made before future inputs are known. Here the emphasis is the information retained after earlier inputs have passed. An algorithm can face both constraints, but neither implies the other.
For the broader foundations of correctness, invariants and resource analysis, start with Algorithm Design. Streaming adds a particular discipline: justify every piece of state that remains after an observation is discarded.
Choose your streaming algorithms route
Chapters 1–3: Define the retained state
Chapters 4–6: Sample and count
Chapters 7–9: Budget and interpret error
Chapters 10–12: Merge and test limits
Chapter index
Define the retained state · Chapters 1–3
1. Start with the question the memory must answer
Sample and count · Chapters 4–6
4. Sample fairly without knowing when the stream ends
Budget and interpret error · Chapters 7–9
7. Turn an error promise into a concrete resource budget
8. Count distinct identities without confusing them with events
Merge and test limits · Chapters 10–12
10. Merge compatible summaries without changing the population
Diagnose and learn · Chapters 13–14
CHAPTER 1 OF 14 · Define the retained state
1. Start with the question the memory must answer
A stream is an access pattern
Imagine a machine receiving one sensor reading each second. After a year it has seen millions of observations. If the only question is the total number received, a counter is enough. If the question is the exact list in arrival order, that counter is hopeless. Nothing about its speed repairs the missing information.
A streaming problem therefore begins with a query rather than a favourite data structure. Examples include the average reading, a uniformly sampled event, every label occurring above a threshold, a particular label’s frequency, the number of distinct labels, or a percentile. These requests require different retained information. An average does not reveal a median; a distinct count does not reveal the identities that were counted.
Let N denote the number of events processed and U the possible set of labels. A memory budget should specify whether it counts bits, machine words, retained records or bytes in a real implementation. One integer counter is a constant number of words under a conventional bounded-word model, but representing an arbitrary count up to N needs about log₂N bits. The phrase constant memory must not conceal unlimited integers.
Processing every event does not mean keeping every event
A sketch can inspect every arrival while retaining only a compact state. A sample instead retains selected observations. Both can support streaming computation, but they discard information in different ways. The specialist guide to probabilistic sketches develops this distinction across membership, frequency and cardinality queries.
For a practical specification, write a sentence such as: “After each insertion, estimate the total occurrences of a supplied label since midnight using no more than a stated number of bytes.” Then add the acceptable error, confidence, query frequency and reset rule. This is already more useful than saying “analyse real-time data.” It defines what success would look like and which information may safely disappear.
The examples below are teaching cases with explicitly chosen data, not measurements of a deployed service. Their purpose is to expose the reasoning so that the same checks can be repeated on another stream.
CHAPTER 2 OF 14 · Define the retained state
2. Declare insertions, deletions, passes and windows
Four changes that produce different problems
In an insertion-only stream, events add non-negative mass. In a turnstile stream, updates may add or subtract from a frequency vector. A strict turnstile setting additionally keeps every resulting coordinate non-negative. A general turnstile setting may allow negative coordinates. These distinctions matter because collision noise that is always positive behaves differently from collision noise that can be negative.
A one-pass algorithm cannot return to earlier records. A two-pass algorithm may use the first scan to discover candidates and the second to verify them. Those are different resource contracts, even if both scans use little working memory. Retaining a full file somewhere else may make a second scan possible, but that storage has not disappeared from the system.
A lifetime query includes every accepted event since the summary began. A sliding-window query includes only a recent interval or the last W events. Expiring old observations is an additional operation. An insertion-only summary does not acquire an expiration mechanism merely because the interface labels its output “last hour.”
Arrival time and event time
Suppose two readings were measured at 09:59 and 10:01, but both arrive at 10:02. An arrival-time window and an event-time window may put them in different reporting periods. Before choosing an algorithm, decide which clock defines the question and what happens when a late reading appears after a result was reported.
The mathematical stream is usually an ordered sequence of accepted updates. A deployed system also needs rules for duplicated deliveries, invalid records, corrections and restarts. If a repeated delivery is counted twice, an exact counter may be perfectly correct for the accepted sequence and wrong for the intended event population. That is an input-contract failure, not approximation error.
An effective design record names the key, the weight, the time convention, the allowed signs, the number of passes and the query scope. Revisit that record whenever requirements change. Many disappointing implementations fail at this boundary rather than inside the algorithm. The correct formula applied to the wrong stream answers the wrong question with impressive consistency.
CHAPTER 3 OF 14 · Define the retained state
3. Keep exact statistics when a small state is sufficient
A mean needs a count and a total
Consider the four readings 4, 7, 7 and 10. After each arrival, the pair (count, total) is (1,4), (2,11), (3,18), then (4,28). The final mean is 28/4 = 7. There is no need to keep all four values if the only future query is this mean and the arithmetic is exact.
The same state also makes merging transparent. If another partition contains two readings with total 20, combine counts and totals: six readings, total 48, mean 8. Averaging the partition means without weights would give (7+10)/2 = 8.5, which is wrong because the partitions have different sizes. The retained counts tell us how much each local mean represents.
Derive an incremental spread calculation
For variance, a useful running state is n, the mean m and M2, the sum of squared deviations from the current mean. When x arrives, set n′ = n+1, d = x−m, m′ = m+d/n′, and M2′ = M2+d(x−m′). Initialise the first observation with its own value as the mean and M2 = 0. In exact arithmetic, this follows by expanding the old deviations around the new mean; their old sum is zero, so the cross terms cancel.
For 4 and 7, the updated mean is 5.5 and M2 is 3×1.5 = 4.5. Adding the next 7 gives mean 6 and M2 = 4.5+1.5×1 = 6. Adding 10 gives mean 7 and M2 = 6+4×3 = 18. The population variance is 18/4 = 4.5. The sample-variance expression is 18/3 = 6 when that statistical interpretation is appropriate; the denominator is a modelling choice, not a formatting preference.
Exact mathematics still meets finite machines
Integer totals can overflow; floating-point additions can round. Incremental calculations avoid some unstable subtraction patterns but do not provide unlimited numerical accuracy. Test large offsets with small differences and specify the accepted numeric range.
Do not choose approximation simply because the data arrive continuously. First ask whether the required statistic already has a small sufficient computational state. Equally, do not infer that all distribution questions can be answered from a count, mean and variance. Different streams can share those summaries while having different tails and different histories.
CHAPTER 4 OF 14 · Sample and count
4. Sample fairly without knowing when the stream ends
Reservoir sampling keeps positions fairly
For a reservoir of k records, retain the first k arrivals. At arrival t greater than k, draw a uniform integer j from 1 through t. If j is at most k, replace reservoir slot j with the new record; otherwise leave the reservoir unchanged. This is the simple Algorithm R discussed in Vitter’s reservoir-sampling paper.
Here is an original trace with k = 2 and arrivals A, B, C, D, E. Start with [A,B]. At t = 3, suppose j = 2: the state becomes [A,C]. At t = 4, suppose j = 4: keep [A,C]. At t = 5, suppose j = 1: finish with [E,C]. These specified draws illustrate one possible execution; they are not a recipe for generating randomness.
Check the probability directly
For a one-slot reservoir, keep the first record and replace it at step t with probability 1/t. The first record survives to step five with probability (1/2)(2/3)(3/4)(4/5) = 1/5. The third record is selected with probability 1/3 and then survives with probability (3/4)(4/5), also giving 1/5. The fifth record enters with probability 1/5. The telescoping products explain why early records are not favoured despite being present for longer.
For k slots, a record already retained is replaced at step t with probability 1/t: exactly one of the t possible draws targets its slot. Its retention probability changes from k/(t−1) to [k/(t−1)]×[(t−1)/t] = k/t. The new record enters with probability k/t as well. The algorithm maintains a uniform sample without replacement of the arrival positions; equal marginal inclusion is a useful check, while uniformity of whole subsets is the stronger invariant.
Sampling events is not sampling distinct identities
If one device sends 100 observations and another sends one, the first device has far more opportunities to appear. That is correct for a sample of observations and unsuitable for a request giving each device equal inclusion probability. Decide the sampling unit before interpreting the result. Also remember that a finite random sample can miss rare events. Fairness of selection does not promise that every important category will be represented in one realised sample.
CHAPTER 5 OF 14 · Sample and count
5. Find frequent candidates through controlled cancellation
Misra–Gries retains possible heavy hitters
Suppose the goal is to find labels occurring more than N/k times in an insertion-only stream. Maintain at most k−1 labelled counters. Increment an existing label when it arrives. If the label is absent and a slot is free, insert it with count one. Otherwise decrement every stored counter, remove zeros, and do not insert the arriving label during that step. This cancellation method is associated with Misra and Gries’s repeated-elements work.
Use k = 3, so there are two slots. For the stream A, B, A, C, A, B, A, D, A, the states after the first three events are {A:1}, {A:1,B:1}, {A:2,B:1}. C triggers a decrement, leaving {A:1}. The next A gives {A:2}; B gives {A:2,B:1}; A gives {A:3,B:1}; D triggers another decrement, leaving {A:2}; the final A gives {A:3}.
The true counts are A:5, B:2, C:1 and D:1. The retained counter for A is three, not five. The algorithm has preserved a candidate with a bounded underestimate, not an exact frequency table.
Prove what the cancellations can remove
Each full decrement can be interpreted as cancelling a group of k different labels: one represented occurrence from each of the k−1 counters and the arriving untracked label. Such groups use disjoint occurrences, so there are at most floor(N/k) cancellations. A particular label loses at most one occurrence per group. If its true count exceeds N/k, it cannot disappear completely.
In our example there are two cancellation groups. With final counter three, A’s true count lies between three and five; it is five. The empty counter for B is compatible with its true count two. This provides an immediate diagnostic: counters are lower estimates, and absence does not imply that a label never occurred.
A second pass can count the retained candidates exactly and eliminate false positives around the threshold. Without replay, retain the uncertainty honestly or use a method designed for the required one-pass reporting contract. Do not quietly add a second scan to a claim of one-pass exact heavy-hitter identification.
CHAPTER 6 OF 14 · Sample and count
6. Estimate supplied-key frequencies with Count-Min
Collisions buy smaller storage
A basic Count-Min Sketch keeps d rows of w counters and one hash mapping per row. An insertion of label x adds its weight to cell hᵣ(x) in every row r. To estimate x, take the minimum of those d cells. For non-negative final frequencies, every selected cell contains x’s own count plus non-negative contributions from colliding labels, so the minimum cannot underestimate x, assuming exact counter arithmetic.
For an original small example, use two rows and three columns, numbered 0, 1, 2. Let A map to (0,0), B to (0,1), C to (2,0), and D to (1,2). Process frequencies A:4, B:3, C:2, D:1. Row one becomes [7,1,2] and row two becomes [6,3,1]. The estimate for A is min(7,6) = 6, although A occurred four times. B, C and D happen to be exact: three, two and one.
Neither row gives A a clean cell. Taking the minimum reduces contamination but cannot promise to remove it. The example uses deliberately specified mappings to make the mechanism visible; those mappings do not establish a probabilistic guarantee.
Read the standard guarantee correctly
For the standard construction, suitable pairwise-independent hashing within rows and independent row choices yield, for a fixed query and frequency vector, an estimate no larger than f(x)+εN with probability at least 1−δ, using w = ceiling(e/ε) and d = ceiling(ln(1/δ)). Here N is total non-negative frequency mass, not the number of distinct labels. See Cormode and Muthukrishnan’s Count-Min paper.
The eduKate Count-Min specialist article follows the cells and error units in more detail. Keep the distinction between querying a known label and discovering unknown frequent labels: the plain counter matrix does not list the keys that created it. Discovery needs a candidate mechanism or another appropriate structure.
Count-Min and Misra–Gries therefore solve related but different jobs. One supplies upper frequency estimates for queried identities; the other retains a bounded collection of candidate identities with lower counters. Neither should be described simply as “the top-items algorithm” without saying what is returned and how it is verified.
CHAPTER 7 OF 14 · Budget and interpret error
7. Turn an error promise into a concrete resource budget
Work through the numbers
Suppose an insertion-only monitor expects N = 2,000,000 unit events. Choose ε = 0.002 and δ = 0.01 for one fixed frequency query. Then w = ceiling(e/0.002) = 1,360 and d = ceiling(ln100) = 5. The table has 6,800 counters. With eight bytes per counter, its raw counter storage is 54,400 bytes, or 53.125 KiB. Hash state, object headers and allocation overhead are additional.
The additive error budget is εN = 4,000 events. If a label’s true frequency is 100,000, that budget is 4% of its frequency. For a label with frequency 20, the same budget is 200 times its frequency. Saying “0.2% accurate” without identifying the denominator would badly mislead the second reader.
If the application flags counts at least 50,000, an estimate of 53,000 supports a true-count interval from 49,000 through 53,000 on the successful-bound event. The threshold lies inside that interval, so the estimate alone cannot settle the classification. An estimate below 50,000, by contrast, rules out a true count at least 50,000 under the no-underestimation invariant. Direction matters as much as error size.
Multiple questions spend confidence differently
A one-query failure probability does not automatically apply to an entire dashboard. For 100 predetermined queries, a union-bound allocation of δ = 0.0001 per query bounds the probability of any failure by 0.01. With the same ε, ten rows suffice because ceiling(ln10,000) = 10. Raw counters then require 108,800 bytes. Independence between those query-failure events is not needed for this union bound.
The individual guarantees must still apply. Queries or inputs chosen adaptively after observing sketch outputs can require stronger analysis; repeating a formula does not establish robustness against such adaptation. Similarly, a confidence bound for one instant is not automatically a guarantee across every time step forever.
These calculations are planning arithmetic, not a performance benchmark. Measure update cost, query latency and actual allocated memory in the chosen implementation. A mathematically smaller summary can still be slower than a straightforward exact dictionary on a small workload. Resource trade-offs should be evaluated at the scale and query pattern that actually matter.
CHAPTER 8 OF 14 · Budget and interpret error
8. Count distinct identities without confusing them with events
Repetition changes the sampling problem
Compare two streams of 1,000 events. One consists entirely of A. Another consists of 991 copies of A and nine different additional labels. Their distinct counts are one and ten. A single uniform event sample sees A with probabilities one and 0.991 respectively. Even a correctly implemented event sample may reveal almost nothing about the rare distinct identities.
This explains why estimating distinct count by multiplying the sample’s distinct count by a sampling factor is not generally reliable. Common identities are likely to enter the sample repeatedly, while rare identities can remain unseen. The relationship between event frequency and distinct membership is essential, not a small correction.
Distinct-count sketches instead use consistent hashing of identities so that repeated observations of the same identity do not behave like new independent identities. Different constructions retain different hash-derived evidence. The Princeton notes on distinct elements and frequency moments develop a minimum-hash approach and explain why ordinary event sampling is insufficient.
The identity definition is part of the result
Suppose a school project counts distinct sensor labels. Are “Room-1”, “room-1” and “Room-1 ” the same label? If one program trims spaces and another does not, their sketches are estimating different sets even when every arithmetic operation is correct. Define the canonical encoding before hashing and keep that definition stable across producers.
The same issue appears when one person has multiple identifiers or several people share an identifier. A perfect distinct-identifier count is not automatically a count of people. The algorithm cannot repair an identity model that does not match the question.
A tiny exact set makes a good development oracle. Construct streams with all unique labels, one repeated label, mixtures of common and rare labels, and alternative encodings of the same intended entity. Compare the sketch with the exact answer under the same identity rule. Record the tested parameter settings rather than borrowing an error percentage from a different implementation.
Compactness is also not a privacy proof. Retaining fewer explicit records can reduce some exposure, but a hash-derived summary may still reveal information through its outputs or combinations with other data. Claims about privacy need their own threat model and mechanism. They cannot be inferred from memory savings alone.
CHAPTER 9 OF 14 · Budget and interpret error
9. Separate percentile position from numerical distance
Rank error measures order
A quantile asks for a value at a chosen position in sorted data. A streaming quantile summary tries to answer without storing the full sorted list. Its guarantee may concern the returned value’s rank rather than the numerical distance between that value and the exact quantile. Those are different units.
Consider ten ordered measurements: 1, 2, 3, 4, 5, 1,000, 1,001, 1,002, 1,003, 1,004. Use a nearest-rank convention, so the 50th percentile is the fifth observation, namely five. A one-position upward error returns 1,000. The rank error is one observation out of ten; the value difference is 995. With no restriction on gaps between observations, small rank error gives no universal small value-error promise.
This is a teaching example about units, not an execution trace of a particular quantile algorithm. Its conclusion follows directly from the ordered values. Changing the units of measurement multiplies the numerical gap but leaves the ranks unchanged.
Choose the contract before the family
The Greenwald–Khanna specialist introduces deterministic rank summaries. The t-digest specialist explains a different approach that concentrates practical resolution near distribution tails. Their promises should not be swapped simply because both return percentiles.
Apache DataSketches’ quantile overview distinguishes families with mathematical rank bounds from its empirical t-digest implementation. Check the actual library and version: a theoretical algorithm, a practical implementation and a reported benchmark are three separate pieces of evidence.
Ties deserve attention too. If many observations equal the same value, that value occupies a range of sorted positions. Decide whether a rank query counts values strictly below or at most equal to the query, and use the same convention in the exact oracle. Otherwise two legitimate conventions can look like an algorithmic defect.
For a threshold decision, ask whether the uncertainty crosses the threshold in the units that matter. A percentile estimate displayed with many decimal places does not solve that problem. If a hard boundary requires stronger evidence, preserve a route to an exact or independently validated calculation.
CHAPTER 10 OF 14 · Merge and test limits
10. Merge compatible summaries without changing the population
Addition works when the representation agrees
For ordinary linear Count-Min updates, two tables with identical dimensions, hash functions, seeds, key encoding and counter interpretation can be added cell by cell. The result is the table that would have been produced by processing the concatenation of their update streams. The counters have preserved an algebraic operation even though the original sequence is gone.
Return to the two-row example. Partition one has A:3 and B:1, producing rows [4,0,0] and [3,1,0]. Partition two has A:1, B:2, C:2, D:1, producing [3,1,2] and [3,2,1]. Adding the rows gives [7,1,2] and [6,3,1], exactly the earlier combined table. This is a check of linearity, not evidence that A’s query becomes exact after merging.
Do not merge the answers when you need the states
Local percentile values cannot generally be averaged into a global percentile. Consider partition one [1,2,3] with median two and partition two [100,101,102,103,104] with median 102. Averaging their medians gives 52. The combined sorted sequence has eight values; under the usual average-of-two-middle-values median convention, its median is (100+101)/2 = 100.5. Weighting local medians by partition sizes does not generally repair this either.
A mergeable quantile summary carries more distribution information than a single local median. Use the supported merge operation with compatible settings and its stated error behaviour. Do not assume every summary is mergeable, or that merging preserves the same error under every arbitrary compression sequence.
Overlap and replay are separate problems
Adding two frequency sketches adds their represented events, including duplicates. If both partitions include the same delivery, the merged result counts it twice. Adding a checkpoint twice also doubles its contribution. Algebraic associativity is not idempotence.
Store enough operational metadata to identify the represented partitions or intervals and to prevent unintended replay. A recovery test should compare uninterrupted processing with checkpoint, restart and continuation. If the application intentionally counts repeated events, preserve them; if it intends one count per logical event, ensure that intention is enforced before or around the summary. The sketch cannot deduplicate an identity it was never designed to remember.
CHAPTER 11 OF 14 · Merge and test limits
11. Understand what tiny memory cannot reconstruct
A simple exact distinct-count lower bound
Consider a deterministic one-pass algorithm that must give the exact distinct count after any continuation of a stream over a universe of U labels. Feed it one copy of every label in a subset S, in a fixed canonical order. There are 2^U possible subsets. If the state has fewer than U bits, it has fewer than 2^U possible configurations, so two different subsets must reach the same state.
If those subsets have different sizes, the algorithm already cannot report both correct counts from the same state. If they have equal sizes, choose a label x that belongs to one subset but not the other. Append x to both streams. In one case the distinct count stays unchanged; in the other it increases by one. Identical states receiving identical next input cannot produce those different exact answers.
Thus this deterministic exact problem needs at least U bits of distinguishable state in the worst case, including everything that can influence future answers. The argument is not a universal lower bound for every streaming task. It depends on exact distinct counting, arbitrary subsets and future updates, determinism and the specified universe model.
Approximation changes the question
The point is not that compact computation is impossible. Counting total arrivals is easy with a counter; exact sums also admit compact state under bounded numeric assumptions. The obstacle is retaining distinctions between many possible histories when the promised future query can expose any of them.
Approximation, randomisation, extra passes, restricted input families and different query requirements can change what is achievable. Each relaxation must be explicit. A low-memory approximate method is not contradicting an exact lower bound; it is solving a different contract.
The same reasoning helps diagnose feature requests. If only a frequency sketch has been stored, a request for the exact timestamp of the first occurrence cannot be answered from that summary. Increasing query time cannot recover information that was discarded. The repair is a richer retained representation or a separate authoritative record, not a more confident label on the output.
Before deleting source data, list the future questions that must remain answerable. Streaming algorithms make selective memory powerful. They also make the consequences of selective memory permanent unless another source has been retained.
CHAPTER 12 OF 14 · Merge and test limits
12. Test transfer when the requirements change
Change one: the monitor now means the last five minutes
Suppose the lifetime stream has 900 old A events followed by ten new B events. A lifetime frequency summary correctly reports A as dominant. In a window containing only the ten recent events, B is the only label. There is no contradiction: the two questions use different populations.
One approach is to keep summaries for time buckets and combine the buckets relevant to a query. But a window boundary can cut through a bucket. Including that entire bucket admits older events; excluding it loses newer ones. Bucket duration, event rate and the handling of partial buckets determine an additional window error. It must not be hidden inside a sketch’s separate approximation guarantee.
If exact per-event expiry is required, the design needs enough information to remove the right outgoing contributions or a specialised window algorithm with an appropriate promise. A uniform lifetime reservoir is likewise not automatically a uniform sample of the recent window.
Change two: updates can subtract
Consider the small Count-Min example, then remove one occurrence of C. Because C’s remaining frequency is non-negative, the same linear table update preserves the interpretation of cells as sums of current non-negative frequencies. The minimum query still cannot fall below A’s true count. Legal deletions in a strict turnstile setting do not automatically destroy that invariant.
Now allow a genuinely negative coordinate: suppose A has frequency one and a colliding B has frequency minus five in one row. That cell can be minus four, below A’s true count. Taking the minimum no longer provides the earlier upper-estimate property. The relevant distinction is the permitted resulting frequency vector, not merely the presence of a minus sign in an update.
Change three: the downstream decision changes
An estimate that is adequate for choosing which labels to inspect may be inadequate for reporting an exact bill or identifying a particular event. Reassess the error direction, scale and evidence requirement when the use changes. Faster processing and larger memory do not by themselves repair a mismatch between the query and retained information.
These exercises implement the learning principle in The Gold Standard of Education: understanding is demonstrated when a person can identify which assumption changed and adjust the method accordingly. A successful transfer explanation names the broken step, then supplies a defensible replacement.
CHAPTER 13 OF 14 · Diagnose and learn
13. Diagnose failures and answer the questions that matter
Why is an estimate below the exact count?
For a basic Count-Min query over non-negative frequencies, that is evidence to inspect the implementation or contract. Check counter overflow, mismatched hash seeds, inconsistent key encodings, lost updates, resets, negative coordinates and whether a different sketch variant is being used. First verify that the exact comparison covers the identical events and interval. An oracle for yesterday is not a reference for today.
Why does the sample miss the rare category?
A uniform sample offers probabilistic inclusion, not guaranteed coverage. In a one-slot sample from 1,000 events with nine rare-category events, the chance of selecting a rare event is only 9/1,000. Increasing the sample size can help, but if guaranteed subgroup representation is required, that is a different sampling design. Also check whether the requested unit was a person, device, session or event.
Why do distributed results change after restart?
Compare the accepted event identifiers and represented intervals before changing the algorithm. A checkpoint may have been applied twice, a batch skipped, or a hash seed regenerated. Then compare numeric state and metadata. Randomised methods also need reproducible test seeds; reproducibility of a test is separate from choosing randomness appropriate for deployment.
Does streaming mean approximate, online or real time?
No single one of those words implies the others. Exact counters are streaming. A streaming algorithm may report only after the input ends. An online decision method may store a large history. A real-time requirement adds a deadline that must be assessed against worst-case processing and system behaviour. Name each constraint separately.
Can a sketch replace the original evidence?
Only for questions its retained information supports. Frequency, order, identity, provenance and timestamps are different properties. A compact summary that is excellent for monitoring may be unsuitable for reconstructing an incident. Decide the retention requirements alongside the summary design rather than after the original events are gone.
What should a useful diagnostic report contain?
State the input model, exact query, parameter values, number of processed events, memory measurement, error units and comparison method. Include a small failing stream if a mismatch occurs. Classify the result as an implementation defect, violated assumption, ordinary allowed approximation or wrong population definition. These categories lead to different repairs; treating every mismatch as “random noise” prevents learning.
CHAPTER 14 OF 14 · Diagnose and learn
14. Build a four-week project that can be checked
Week one: make a transparent exact baseline
Generate small labelled streams with known counts, means, medians and distinct sets. Keep the complete input for this learning project so every result can be checked. Implement exact dictionaries and sorting before compact summaries. Include an empty stream, a single event, all-identical data and all-distinct data, and define what each query returns when its mathematical quantity is undefined.
Use the readings 4,7,7,10 to verify count, total, mean and spread. Use unequal partitions to expose incorrect averaging. Record the state after each event, then explain why the state contains enough information for each promised query. This stage builds a reliable reference rather than optimising prematurely.
Week two: trace cancellation and random selection
Implement the two-slot heavy-hitter example and reproduce each cancellation. Compare every retained counter with exact frequencies and the cancellation bound. For reservoir sampling, enumerate all random-draw possibilities on very short streams or run many seeded trials and examine inclusion rates. An experiment can detect obvious bias; it complements rather than replaces the probability argument.
Change the sampling unit from events to distinct labels and explain why the original algorithm no longer solves the stated request. This is a useful learning outcome even before implementing an alternative.
Week three: budget error and test merging
Build the deliberately colliding two-row sketch and recover [7,1,2] and [6,3,1]. Then use a properly specified hash construction or a documented implementation for larger experiments. Plot or tabulate absolute overcount against total stream mass, rather than presenting only relative error for frequent keys. Include rare labels, which expose the limits of an additive bound.
Split a stream into partitions, merge compatible states and compare with direct processing. Repeat with an intentionally changed seed and require the merge to be rejected. Add restart and duplicate-batch tests. These exercises connect the mathematics to the operational conditions under which the result remains meaningful.
Week four: change the contract and explain the repair
Introduce a recent window, late events or signed updates, one change at a time. Write down whether the original invariant survives. For quantiles, compare ranks and values on the gapped ten-value example. The final deliverable should be a small reproducible demonstration, its exact baseline and a short explanation of what cannot be recovered from the retained state.
For further study, use Vitter’s reservoir paper for sampling, Misra and Gries for repeated elements, Cormode and Muthukrishnan for Count-Min, Princeton’s distinct-elements notes for cardinality, and Apache DataSketches for the distinctions between implemented quantile families.
The practical achievement is a clear explanation of what the memory preserves, why an update is valid, what a returned number guarantees and which changed requirement would force a different design. That capability makes streaming algorithms useful in monitoring, data engineering and scientific computation long after the first small example has been solved.