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.
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.