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

Stream model — where it appears

The set of things a stream is allowed to do — negative updates, expiring items, one pass — which every accuracy bound in this field is conditional on. Every accuracy bound in this field is conditional on it, and each of its assumptions can be turned into a dial with a measurable consequence.

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

+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 Count-Min8,192 bitsCount-Sketch8,192 bitstug-of-war, F22,560 bitsGreenwald–Khanna0 bitsexponential histogram0 bitscash register+strict turnstile±general turnstile± may go negativesliding window+ expiresdeclareddeclared93% under—declareddeclareddeclared—declareddeclareddeclared—declared——————declared40,000 updates · deletion rate 0.5 · every count exact1,758 of 1,895 under

The model a bound was quoted in

Every accuracy figure in this field's first phase was measured under four unstated assumptions. Remove them one at a time and one structure loses its guarantee on 91% of queries, another's error stops falling when it is given more state, and a third has nothing to do at all.

bounds · Bound 1,00010³window length W, in arrivalsbits of state heldW bits, exactε = 0.5ε = 0.2ε = 0.1ε = 0.05ε = 0.02sliding-window model · 40,000 arrivals · state from the shape of the structure5,670 bits at W = 8,000

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.

space · Window 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

Named alongside it

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

GuaranteeState bitsStreaming algorithmHonest limitSliding windowExpiryExponential histogramOne passRelative errorSketchCancellationEstimator

All concepts