One pass, and no room
The answer that is allowed to be wrong
What changes when an algorithm is not allowed to keep its input, why the answer stops being exact, and how the trade between bits of state and size of error is measured rather than asserted.
The state a merge is standing in for
Why comparing a merged summary against a single small one is the wrong comparison, what the right one costs, and how much accuracy is given up for never having the whole stream in one place.
Counting past what the register holds
The oldest sketch there is, measured — why the estimate is unbiased, what the register actually costs, and how the base sets the exchange rate between bits and error.
The partition the analysis did not mention
How a stream is split across machines is not in any bound these structures carry, and it moves the merged error by a factor of six in opposite directions for two structures that are otherwise identical.
A count that is never under
How a frequency sketch works, why the minimum rather than the mean, what the additive bound actually promises, and what a published improvement gives away to get a better average.
A count read off the leading zeros
How counting distinct things becomes a question about the most surprising hash, why one register is useless, and what stochastic averaging buys that more hash functions do not.
A window that is a duration
What changes when a sliding window is measured in seconds rather than arrivals — the occupancy stops being a constant, the stamp width stops depending on the rate, and every per-item bound acquires a precondition.
The correction that makes it work
What the harmonic mean buys over the arithmetic one on identical state, why the raw estimator is biased at low cardinality, and what a correction that switches estimators is actually doing.
The error of a difference
An intersection of two 100,000-key sets estimated by inclusion–exclusion over HyperLogLog sketches and by the k smallest hash values, swept over Jaccard indices from 0.82 to 0.005. Subtracting keeps a fixed error as a share of the union and so loses all its relative accuracy; sampling the union does not, and at equal state the two cross at a Jaccard index of about 0.05 — which itself moves with how many bits are spent.
The estimate that squares the stream
The second frequency moment by the tug-of-war estimator, why one register is hopeless and unbiased at the same time, and what averaging and a median each buy.
A budget split before the question arrives
A fixed budget of 40,960 bits a set split in eighths between a HyperLogLog and a bottom-k sample, measured against an oracle that knew the overlap: each split's worst regret over Jaccard indices from 0.98 to 0.001, three rules for choosing the estimate at query time, why the textbook variances choose wrongly, where the crossing sits for each split, how the minimax split moves with the smallest overlap a system must answer, and what changes when one set is ten times the other.
The error that is on the rank
Greenwald–Khanna quantile summaries — the invariant, the measured size against the bound, and why a deterministic structure beats a uniform sample of the same bits on the promise it makes.
The counter with no window in it
What an exponentially decayed counter answers, how it relates to a sliding window and where the relation stops, and why the family with no W in it is the one monitoring systems actually run.
The summary that has to forget
The sliding-window model and the exponential histogram — buckets of powers of two, why the entire uncertainty is one bucket, and a half-count that is wrong when the window is nearly empty.
The bits that say when
The eleventh counter — bits spent on knowing when an item arrived, measured apart from bits spent on knowing what it was, across four structures that answer the same question over a sliding window.
A register that became a list
Counting distinct items over a sliding window — why a maximum cannot be one number when the arrivals expire, what a list of future possible maxima costs, and why approximation buys twenty times less here than it does over a stream.
An error measured against the answer
Relative-error quantile summaries — why an ε on the whole stream is the wrong promise at a tail percentile, what a cap that shrinks with the tail costs, and why a rank error carries no information about the values at all.
The floor a histogram already knows
How the smallest counter a bounded-space summary settles at can be predicted from the arrival frequencies alone, why dividing the tail mass by the width is not the answer, and what the fixed point is worth.
The tuples a merge does not give back
How the state of a merged quantile summary grows with the number of shards, why compression cannot undo a merge, and what the fitted exponent depends on.
The window that is even in the wrong currency
What an arrival-counted window promises about time, measured — and why the unevenness a time window shows in its occupancy is the same unevenness on the other axis.
The period that is not a promise
What the compression period of a quantile summary actually decides, why it is hooked to the error parameter, and what a deployment is choosing when it tunes ε.
A decay measured from where it started
Exponential, backward polynomial and forward polynomial decay compared on the weights they give, the age at which an arrival counts half, and a Poisson stream whose rate rises fourfold: how long each takes to follow the rise as the stream ages, what restarting the landmark does, and where the three sit on the trade between noise and speed.
What a heavier tail actually buys
Exponential, backward polynomial, a fitted sum of three exponentials and a restarted forward counter, matched at five per cent spread and then asked to detect one burst at a fixed false-alarm rate: the detection horizon at six burst sizes, the growth law each shape obeys, the exponent checked against 1/α at four values of α, and what reaching further costs to store.
The moments past the second
The sampling estimator for frequency moments Fₖ past the second, with its variance computed exactly over every position: the telescoping that makes it unbiased, what individual positions report, the variance against the stream's skew, the guarantee k·n^(1−1/k) and the stream that comes within a constant of it, copies needed for ten per cent, and drawn means against the exact spread.
A detector that learns its own quiet
A self-calibrating burst detector on Poisson streams of ten arrivals a second — a fast exponential counter matched to 5% spread, a slow one at R times its half-life, and an exponentially weighted mean square of their difference as the scale — against the fast counter with an oracle threshold from sixty independent streams: the half-detection horizon at four burst sizes, false alarms on a still stream at five values of R, one stream traced through a burst, false alarms under a steady rise in the background, and detection against lag.
The clock a burst cannot outlast
Three schedules for the scale of a self-calibrating burst detector on Poisson streams of ten arrivals a second — release after the alarm has lasted L*, release after the fast-less-slow difference has stayed positive for L*, and resetting the slow counter at that point — measured against the held and learning scales: alarms on linearly rising backgrounds at two ratios of half-lives, the half-detection horizon at four burst sizes, both clocks traced on one stream, alarms against the drift's offset in spreads of the difference, and the rebasing design traced through a steep rise.
The keys worth counting before sampling
A one-pass estimator for F3 that keeps a Count-Sketch and a list of candidate heavy keys beside the sampling estimator's copies, measured on 60,000-arrival streams over 2,048 keys at Zipf exponents from 0 to 2 and on the one-heavy-key stream at 128 to 16,384 keys: the share of F3 the top keys hold, words for 10% against the number of candidates in two ways of reading a candidate's frequency, the parts of the bill against the sketch's width, words against the exponent, and words against the size of the worst stream.
The slope the slow counter already shows
The two-counter burst detector at R = 16 and 64 on Poisson backgrounds rising 5 to 40% every 1,000 seconds, with the rise's predicted offset subtracted from the counters' difference — the slow counter's change over one slow half-life, decayed with half-lives of one, four and sixteen slow half-lives, times (R − 1)H/ln 2 — against the held scale and the positive clock: alarms against the rise's offset in spreads of the difference, one stream's corrected difference, the detection horizon after bursts of 300 to 9,000 arrivals, the estimate's half-life, and how long it takes to catch up.
The rise the correction kept subtracting
The two-counter burst detector at R = 16 on Poisson backgrounds that rise by 20% or 40% every 1,000 seconds and then hold level, with three ways of setting its threshold — a scale held while alarmed, the positive clock, and the held scale with the rise's offset subtracted — every point averaged over 24 to 60 streams: the mean corrected difference around the end of the rise, the alarms each design raises on the level stretch, the share of bursts of 20 and 30 arrivals caught at stated lags after the rise ends, and how long a burst of 300 stays visible.
A share of a list of equals
The third frequency moment of 60,000 arrivals over 2,048 keys at Zipf exponents 0 to 2, estimated to a relative standard deviation of 10% by a Count-Sketch of depth five, a list of candidates counted from entry, and copies of the sampling estimator: words against the exponent for the plain sampler, the best fixed list, and lists of 8 to 64 whose candidates are counted only above 1%, 3% or 10% of the list's own moment; candidates kept; words over the best on each exponent for each list length; each candidate's share of its list on one pass, flat against Zipf 1; words by part; and words against the list's length at Zipf 0.5.