Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Streaming algorithm — where it appears

An algorithm that reads its input once, in order, keeping far less than the input and answering from what it kept. Everything it might later be asked has to be decided before the data arrives, which is why a summary answers one question well and every other one not at all.

Named by 12 essays across 4 fields — each of them below, with the objects they name alongside it.

1,00010,0000.1bits of state heldrelative errorHyperLogLog (-0.49)LogLog (-0.44)bottom-k (-0.38)50,000 distinct keys · 14 runs per point · truth counted exactlybest: 2.00% at 10,240 bits

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.

streaming · Sketch 0.1bits the register neededrelative errora = 2a = 1.5a = 1.2a = 1.1a = 1.05a = 1.02√((a−1)/2), predicted200 runs per base · n = 20,000 · exact counter needs 15 bits72.6% at 5 bits

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.

streaming · Sketch k/n = 0.1250.0810.1250.169position in the streamshare of runs in which it was sampledAlgorithm R, n = 32, k = 4, 40,000 runsworst departure 3.3% · noise 1.4%

One pass, k slots, and two randomness budgets

Reservoir sampling takes a uniform sample of k items from a stream of unknown length in one pass and k slots. The textbook version and a second version draw from exactly the same distribution, and at 65,536 items one of them spends 1,356,399 random bits and the other spends 9,380.

randomness · Randomness 01325leading-zero rank keptregister, 0 to 255estimate 7,107truth 7,368error -3.54%0 still empty256 registers × 5 bits = 1,280 bitspredicted ±6.50%

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.

streaming · Cardinality +1−1keys, most frequent firstΣ s(x)·f(x) = 9,034squared: 81,613,156true F2: 36,931,352121.0% outa polynomial of degree 4 · cash-register model · counts exactone register, 32 bits

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.

streaming · Moment answered 19.90%25%50%75%100%0.36420.52,170value, logarithmicfraction of the stream at or belowrank ±2%value 19.3–21.9answered 2.9% out20,000 values · log-normal, σ = 1.2 — a latency distribution · Greenwald–Khanna, ε = 0.02rank 1.02% · value 2.9%

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.

streaming · Rank 011228101214161820universe size ubits of statea u-bit bitmaplog₂ C(u, u/2)⌈log₂(u+1)⌉, a counterat u = 12: 924 subsets, 8 bitstwo collide → answers 6 and 7floor computed exactly · collision found by exhaustion at u = 12floor 9.85 bits

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.

floors · Cardinality 3,600 — the window opens4,000 — now32161616884the window edge215 in buckets−16 for the oldest= 200true 2000.3% outsliding-window model · ε = 0.2, k = 5 · 1,764 merges406 bits against 400

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.

streaming · Window 1,00010³window length W, in arrivalsbits of state heldW bits, exactε = 0.2ε = 0.1ε = 0.05sliding-window model · 40,000 arrivals · state from the shape of the structure2,808 bits at W = 8,000

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.

floors · Window Count-Min 4×64exact184 under16 overrms 42Count-Sketch 4×64-174-8708717499 under101 overrms 13general turnstile · insertions and deletions, counts may go negative · counts exact8,192 bits each

When the stream takes it back

Count-Min's estimate is never below the truth. That is a theorem about a stream where every update adds — and allow deletions that can take a count below zero and it comes back under on 93% of queries, with nothing in the number to say so.

wrong · Sketch 0.313103000.250.50.7511.251.52Zipf exponent s of the stream — 0 is flatvariance of one copy ÷ moment²sampling, F4sampling, F3sampling, F2signs, F22,048 keys, 60,000 items, exactdashed: tug-of-war

The moments past the second

Past the second moment no sign trick works, and the estimator that does — pick one position of the stream, count how often its key comes again, report m(r^k − (r − 1)^k) — is unbiased for every moment on every stream. Its variance can be computed exactly rather than sampled, and on real streams it is nowhere near its guarantee: 103 copies give F3 to ten per cent on a flat stream of 2,048 keys, and 2,630 on a moderately skewed one. The guarantee asks for 48,381, and it is not loose. One heavy key among 2,047 keys seen once needs 11,799.

streaming · Moment 00.250.50.7511.5210010³Zipf exponent of the streamwords for 10% on F3sample every positionheavy keys first60,000 arrivals, 2,048 keysa word: a key or a count

The keys worth counting before sampling

The sampling estimator for the third frequency moment spends most of its copies on keys that barely contribute to the answer. Finding the heavy keys first with a Count-Sketch, counting them, and sampling only the rest cuts the state for ten per cent from 5,260 words to about 1,500 on a moderately skewed stream, and from 23,598 to under a thousand on the stream built to be worst for the sampler. It costs five times more than it saves on a flat stream, where there is no heavy key to find. What decides it is how the frequencies are shaped, not how long the stream is, and the frequencies must be counted, not read off the sketch, because the sketch's error on a heavy key is cubed.

streaming · Moment

Named alongside it

The objects these essays reach for when they reach for this one.

State bitsRelative errorSketchEstimatorGuaranteeOne passStream modelUnbiased estimatorVarianceHonest limitSamplingCardinality

All concepts