State bits — where it appears
Named by 43 essays across 9 fields — each of them below, with the objects they name alongside it.
An index larger than what it indexes
A suffix array over 16,384 characters is 229,376 bits, and it cannot answer a single question without the 81,920 bits of text beside it. Nearly four times the text, to search the text. Every index on this site had been weighed at zero until somebody put one on a scale.
The answer that is allowed to be wrong
Every algorithm on this site so far was checked for correctness before it was measured. A summary of a stream cannot be — the data goes past once and does not fit — so the error becomes a resource, bought with bits, at an exchange rate that is a measurement.
The state a merge is standing in for
A merge of eight summaries of thirty-two counters is wrong by 536 where one summary of thirty-two is wrong by 769, which reads as merging helping. One summary of two hundred and fifty-six counters — exactly what the eight were holding between them — is wrong by nothing at all.
Counting past what the register holds
Morris's counter counts ten million events in five bits by incrementing with probability 2 to the minus c. The estimate is exactly unbiased at every n, its relative error is 71%, and the base is a dial that trades one against the other at a rate of the square root of half of a minus one.
The partition the analysis did not mention
Space-Saving and Misra-Gries are the same structure under a stream, related by subtracting one number. Sharded eight ways and merged, one of them is wrong by 313 where the other is wrong by 927 — and swapping how the arrivals were assigned to machines reverses which is which.
A count that is never under
The Count-Min sketch holds four rows of counters and answers how often a key occurred. Its error is one-sided with no probability attached — the estimate is never below the truth on any stream — and the probabilistic half of its guarantee is only about how far above.
The index that is smaller than the text
The Burrows–Wheeler transform is a permutation, so it changes no symbol frequency and a plain index over it is the same size whether the text has deep structure or none — 6.29 bits a character against 6.16, on texts whose third-order entropies differ fourfold. What the transform changed was the runs, and a structure that charges one bit per bit cannot see a run.
A count read off the leading zeros
Hash every key and watch for the longest run of leading zeros. Seeing k of them is evidence of about two to the k distinct keys — an estimator with a variance so large it is worthless, and the two devices that fix it are the whole of what a cardinality sketch is.
The promise that does not survive the tree
A high-biased quantile summary at ε = 1% answers the 99th percentile of twenty thousand values to within two ranks. Merge thirty-two of them and the answer is seventeen ranks out — inside the merged bound, eight times outside the one anybody was quoted.
A window that is a duration
Nobody asks for the error rate over the last four thousand and ninety-six requests. They ask for the last five minutes. The two are the same question exactly when the arrivals are evenly spaced, and on a stream whose rate drifts they disagree about fifty-seven per cent of the counts.
The error of a difference
Three sketches, each within a per cent or two of its own answer, subtracted into an intersection. At a Jaccard index of 0.82 the answer is 1.3% out. At 0.005 it is 146% out — the same three sketches, the same accuracy, a different question. The error never grew: it stayed a fixed fraction of the union, and the union stopped being the thing being asked about.
The estimate that squares the stream
The length of a stream is a counter and the number of distinct keys is a register bank. The sum of the squared frequencies has nothing obvious to count — and one number, one sign per key, and a squaring get within 4% of it in a fortieth of the space.
The window that is not full
A structure sized for a window of 256 items meets a stream that hands it 1,736 at the worst instant and 79 at the best. Occupancy was a constant in the model the sizing came from, and every per-item bound in that model quietly assumed it.
The clock that cannot see the burst
A stream generator asked for a burst ten times faster than its mean rate, on a clock whose resolution was the mean gap, produced a perfectly even stream — index of dispersion 0.00, for something called bursty. Nothing had gone wrong except that the instrument could not represent what it was being asked to measure.
The error that is on the rank
A summary of 77 tuples answers eight quantiles of a stream of 20,000 values, and every answer is guaranteed to sit within 0.9% of the stream from where it was asked for. The guarantee is deterministic, it holds on every distribution, and it is not about the numbers it returns.
The estimate that is a median of means
An estimator with a 70% spread is not usable and an estimator with a stated failure probability is. The construction that turns the first into the second is two lines long, it is where every delta in this field comes from, and its exponential is measured here by counting failures rather than by evaluating a bound.
What a window costs in bits
The approximate structure grows like the square of a logarithm and the exact one grows like the window, so the approximation wins eventually. Eventually is a window of 6,000 at a 2% tolerance — and below it the summary is larger than the thing it is summarising.
The counter with no window in it
A counter that fades by half every H settles, on a steady stream, at exactly the count of a window of 1.44H. That correspondence holds in the mean, on a steady stream, and nowhere else — and it is the reason a decayed counter is not an estimate of a windowed count for any window.
The floor under a summary
An exact one-pass distinct-counter over a universe of u keys needs at least log2 of u-choose-u-over-2 bits of state — the same counting argument as the sorting floor, applied to memory states instead of outcomes. At u = 12 that is 9.85 bits, and an eight-bit candidate is shown to collide by running all 924 subsets.
The pass that was never a parameter
One pass is the streaming model's defining restriction, and this collection has enforced it by making a second read throw. A prohibition cannot be swept. Turn it into a dial and the first thing it says is that a second pass turns eighteen candidate heavy hitters, six of them wrong, into twelve that are exactly right — for 3,680 bits carried across the boundary and no extra space at all.
The summary that has to forget
Every structure in this field so far accumulates. Ask instead for the count over only the last thousand arrivals and no counter will do, because a counter has no record of which of its increments are old — and the repair is a row of buckets whose whole error is the oldest one.
The text that does not have to be kept
The index reproduces its text character for character, in 1,024 mapping steps and zero reads of anything. That is the whole justification for weighing it against the text rather than beside it — and the price is a dial that moves the structure by 3.3 times and the cost of locating one match by 72.
The bits that say when
A windowed cardinality estimator holds 4,592 bits and 2,392 of them are clocks. Every summary in this collection has reported its size from the shape of its own structure, and not one of those numbers has ever been asked what the bits were for — so the resource that half of these structures spend most of their state on has been invisible while being counted.
The fading nobody computes
Twelve thousand arrivals into thirty-two decayed counters cost 382,976 fade multiplications. An implementation that aged every counter on every tick would have cost 3,830,256, and the ratio is exactly the mean gap between arrivals — not a coincidence, and the reason the family is deployable.
The floor under a window
An exact count of the ones in the last W arrivals needs W bits, and the argument is a pigeonhole that can be performed rather than quoted — 1,024 windows, an eight-bit state, the colliding pair produced, and the two answers it cannot tell apart.
The guarantee that is one query wide
A sketch described as accurate to within a per cent is accurate to within a per cent of the whole stream, not of the number asked about. On a skewed stream the same sketch is 4% wrong about its heaviest key and 34,100% wrong about one of its rarest, and both figures satisfy the bound.
What a second pass buys
Exact selection of a median from thirty-two thousand values needs the whole stream in one pass — a million bits — and eleven thousand in two. By nine passes it is three hundred and twenty. The state falls as n to the power one over p, which is a law with an exponent worth fitting, and on skewed data the deterministic rule misses it by three orders of magnitude.
A register that became a list
HyperLogLog replaces a key per distinct item with a five-bit register, and over a whole stream that is a saving of a hundred times. Ask it about the last four thousand arrivals instead and the same comparison against the same exact structure comes out at five. The estimator did not get worse. The exact answer got cheap.
The items that survive k counters
Misra-Gries keeps k counters, decrements all of them on a miss, and never returns a count above the truth — with no hashing, no randomness and no failure probability. At equal state it is more accurate than the randomised sketch on the question both are usually asked, at every size measured.
The pass that runs the other way
Exact heavy hitters over the last 4,096 of 40,000 arrivals cost 40,000 reads and a ring of 4,096 keys and stamps read forwards, and 4,096 reads with no stamps read backwards. Every lower bound in the sliding-window model is a bound about an access pattern, and the word doing the work never appears in the statement.
A floor one pass cannot get under
An exact one-pass selector must reach a different memory state for every prefix it might have read, and the pigeonhole that proves it is small enough to perform — nine hundred and twenty-four prefixes through a nine-bit state, the collision produced, the suffix that separates it, and two true medians it cannot both return. Ten bits collide on none, so the bound is exact — and a second pass walks under it by a factor of ninety.
An error measured against the answer
A quantile summary asked for the 99.9th percentile answered 9,694 where the truth was 256, and violated nothing — its promise was a rank error under one per cent of the stream and it delivered a tenth of one per cent. One per cent of the stream is a thousand per cent of the tail, and no amount of extra state changes that.
The cheap tail and the expensive merge
A summary whose tolerance tightens towards the tail keeps seven times the tuples of a plain one on a single pass, and after merging sixty-four shards it keeps three and a half times as many. The error function that buys a useful tail promise is also the one that pays most for never having the values in one place.
The summaries that add
Two sketches built over two streams and merged are, for three of the four structures here, byte for byte the summary the concatenated stream would have produced. For the fourth the guarantee survives and the state does not, and calling both properties mergeability hides the difference that matters.
A promise about the rank is not a promise about the value
A quantile summary asked for the 99th percentile of a log-normal stream returns the largest value it ever saw — 2,169 against a true 318, six times too high — and its rank error is 1.00% against a promised 2%. The guarantee held. It was never about the number.
The tuples a summary does not report
A Greenwald–Khanna summary at ε = 0.01 answers `tuples` with seventy-seven. Watched through the run it holds a hundred and thirty-six. The gap is the compression period, it is 1.70 to 1.93 times across every tolerance measured, and it is the number a deployment has to allocate.
A sketch that is allowed to be under
Count-Min's estimate is never below the truth, and it pays for that with an error proportional to the whole stream. Give every key a sign and take a median instead, and the same table is 2.7 times more accurate on the keys anybody asks about — and wrong in both directions.
The tuples a merge does not give back
A merge of thirty-two quantile summaries keeps seven times the tuples of one summary over the same values, and sixty-four keeps ten and a half. Fitted across the sweep the count goes as the shard number to the power 0.56, which answers what it converges to — it does not.
The count that outlives its arrivals
A Misra-Gries counter holding six thousand is not a record of six thousand arrivals. It is a number that has been added to and taken from, and nothing in the structure says when any of it happened — so when the key stops arriving the counter stays, and goes on reporting a key with nothing in the window as the heaviest thing in it.
The counter that takes the smallest slot
Space-Saving keeps two numbers per key and they bracket the truth from both sides. On the twenty heaviest keys of a stream its mean error is a tenth of one arrival, against a hundred and ten for Misra-Gries at the same bits — and on the keys ranked past a hundred the ordering reverses.
A decay measured from where it started
An exponentially decayed counter is one number because its weights fade by elapsed time alone. Forward decay keeps a polynomial weight in one number too, by measuring each arrival from a fixed landmark. Its memory is then a share of the time since that landmark: at β = 2 an arrival counts half at 29% of that time. Anchored at the start of a stream, it takes 5.3 seconds to register a fourfold rise twenty seconds in and 83 seconds when the rise comes at five minutes.
The shape that moves the bill
Thirty-two quantile summaries combined pairwise keep 3,637 tuples and the same thirty-two folded in one at a time keep 2,616, for answers that differ by nothing at all. The counter tables measured for the same thing do the opposite — their order moves the answer and leaves the space alone.
The shape one structure will not fold
Folding thirty-two shards largest-pair-first keeps 2,556 quantile tuples against a balanced tree's 3,211 — a fifth of the space saved. The same fold on the counter tables beside them leaves 403 counts of error against the tree's 148. A deployment holding both cannot fold once and be right twice.
Named alongside it
The objects these essays reach for when they reach for this one.
GuaranteeTrade offEstimatorHonest limitMeasurementSketchStreaming modelMergeable summaryRelative errorHeavy hitterMisra–GriesSliding window