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 covariance the registers already hold
The split study's 40,960 bits a set — a HyperLogLog of 1,024 to 7,168 registers beside a bottom-k sample — with the subtraction's variance read from 32 groups of its own registers: worst regret for every split under five rules, the register variance against the measured and textbook errors, the correlation the groups show between A's estimate and the union's, each rule's error at every overlap against the oracle, and the same regret when one set is ten times the other.
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.
A list that gives back its places
A 10% estimate of F3 on 60,000 arrivals over 2,048 keys at Zipf exponents from 0 to 2, held as a Count-Sketch of depth five, a list of counted candidates and copies of the sampling estimator: the plain sampler, the best fixed list, a list of 64 cut at the end to candidates holding 3% of its moment, and a list that drops a candidate during the pass whenever it falls below a share of 0.01, 0.03 or 0.1 of the list's total, charged its largest peak. Words against the exponent, the list's length through the first 2,000 arrivals, peak and final length against the exponent, and where the words go at Zipf 1 and Zipf 0.5.
A check as slow as what it checks
A burst detector of two decayed counters at R = 16 with its slope correction capped by a decayed mean of the uncorrected difference over 213 s or 53 s, on Poisson backgrounds of ten arrivals a second that rise by 5% to 40% every 1,000 s and level off: the mean corrected difference around the end of a rise, what the difference shows against what the estimate predicts and each cap allows, small bursts caught after the rise ends, false alarms and the share of the offset subtracted while a rise lasts, and a small burst arriving after a large one.
A variance that had seen one hash
Two sets of 100,000 keys at Jaccard indices from 0.98 to 0.001, 64 draws each, a 40,960-bit budget split in eighths between a HyperLogLog and a bottom-k sample, the intersection estimated by inverse-variance weighting of inclusion–exclusion (variance read from 32 groups of registers) and the sample's share of the union (binomial variance). The sample's variance taken at one shared hash, at half a hash with the estimate unchanged and with it changed, and under floors from a tenth of a hash to two. Worst regret at every split, what a sample of 160 hashes sees at small overlaps, the weight it is given, the floor swept, and every estimate's error in the corner.