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

The thread: A guarantee names its model

Count-Min's estimate is never below the truth — in a stream where every update adds. Allow a count to go negative and the same structure comes back under on 91% of queries, with nothing in the number to say so.
313roundconc 0.14536hashedconc 1.00309blockedconc 0.14how the arrivals were partitionedworst error over the top keysone summary, k = 32one summary, k = 256the merge of 8Space-Saving · stationary Zipf · 40,000 arrivals8 shards One pass, and no room

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.

 quantilepromisedone summarymerge of 8q = 0.5100.01418q = 0.920.0183q = 0.992.005overq = 0.9990.214overrank error, in items out of 20,000ε = 0.01 · high-biased · 8 shards, round2 of 4 quantiles over the single summary's promise What is taught wrongly

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.

 0%25%50%75%100%11.522.533.545what a matching character is worthreported as the shared region, of the longer sequencea random pair scores zero hereunit cost, alphabet acgtthe region found: 13 characters at the left, 34 at the right When the algorithm is a table

The zero that moves the answer out of the corner

One extra term in the recurrence — a floor at zero — and the answer stops being in the last cell. It becomes a maximum over all 1,040 of them, the traceback's starting point is a search, and the whole mode is meaningless unless a randomly matched pair of characters scores negative on average. That last condition is on the scoring scheme, not on the sequences.

 10010³10³10⁴10⁵10⁶10⁷Vcounted workTopological order, one passDijkstra, binary heapBellman–Ford, all passesV from 64 to 2048, directed, acyclicwork = scans + visits + relaxations + queue comparisons Two parameters

The precondition that removes the queue

Dijkstra maintains a priority queue to discover which vertex is safe to finalise next, and on a directed acyclic graph 65% of its counted work goes into that queue. The order it is discovering is already known. Relaxing in topological order makes exactly one relaxation per arc — 1,536 arcs, 1,536 relaxations — with no queue at all, and negative weights are fine.

 No estimate543 cells expanded · path 58Straight-line estimate325 cells expanded · path 58Estimate doubled71 cells expanded · path 64V = 900, E = 895, every edge costs onethe estimate is a function of the vertex, supplied by the caller Two parameters

The precondition on a function the caller writes

Dijkstra expands 1,582 cells to find a path of 98 across a fifty-square grid. The same loop, with the straight-line distance to the goal added to each key, expands 405 and finds the same 98. The estimate has to be a function the caller supplies, and the guarantee holds only while that function never overestimates — a condition on somebody else's code, not on the graph.

 16326412825610244096window length W, in arrivals (D = W × the mean gap)share of the counts they disagree onevenPoissonburstydrifting1 ms clock · mean gap 10 ticks · 30,000 arrivalseven: 0% at every length One pass, and no room

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.

 +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 One pass, and no room

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.

 W = 256even256–256Poisson225–285bursty256–256drifting79–1,736items held inside the time windowD = 2.56 s · 1 ms clockW would be 256, always What is taught wrongly

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.

 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% One pass, and no room

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.

 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 What a bound is

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.

 decayedwindowed060120secondscount attributed to key 0half-life 4 s · window 5.77 s · burstythe same key, two questions One pass, and no room

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.

 1 coefficient13 members2 coefficients169 members3 coefficients2,197 members4 coefficients28,561 members1 key2 keys3 keys4 keys5 keysexact92% gone99% gone100% gone100% goneexactexact92% gone99% gone100% goneexactexactexact92% gone99% goneexactexactexactexact92% goneevery member walked · GF(13) · no tolerance and no seeddegree 1, 2, 3, 4 When the algorithm flips a coin

The independence an estimator spends

Every sketch's analysis begins by assuming a truly random hash, and nobody comes back to that line. Independence has a degree, the degree is enumerable over a small field, and an estimator's mean and its variance spend different amounts of it.

 above 0.01 of the stream · 13 really areone pass: 18 candidatestwo passes: 13 keys, exactly the heavy ones123456789101112131415161718128 counters · carry 1,376 bits5 of 18 spurious What a bound is

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.

 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 One pass, and no room

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 language's sortMerge sortlog₂(n!)random43,810 / 43,976nearly sorted10,806 / 24,845already sorted4,095 / 24,576reversed4,095 / 24,576few distinct values27,561 / 42,338n = 4,096, counted through the comparatorthe first column is a fact about the engine, not about sorting Counting

The count that came from somewhere else

Every count in these essays is described as exact, reproducible, and identical on every machine. Two of them are not. A spanning-tree measurement quotes 42,385 comparisons spent in a sort, and that sort is the language's own — whose comparison count is specified nowhere, varies by a factor of thirteen across input kinds, and comes within one per cent of the information floor on random input.

 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 floors

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.

 SETHno algorithm for k-SAT beats exhaustive search for every korthogonal vectorsno N^(2-e) algorithmedit distanceno n^(2-e) algorithmperformed heresplit and list, checked on 55,754 formulasquoted, not performed herequoted, not performed heresolid: an implication performed here · dashed: one that is quoteda conditional floor The floors

A floor that holds if something else does

The four lower bounds on this site are proofs. This one is a chain of implications with a conjecture at the top, and neither end of it is proved. The link that can be performed is performed here — checked over 55,754 formulas, 918 of them unsatisfiable — and the link that cannot is quoted and marked as quoted.

 cash register — every key49,952 bitscash register — HyperLogLog2,560 bitswindow — a stamp per live key8,505 bitswindow — HyperLogLog5,494 bits40,000 arrivals · the popular keys drift, so old keys are gone rather than rare · W = 4,0961,561 distinct in the stream · 169 in the window20× against 1.5× One pass, and no room

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.

 read from the start40,000 readsa ring of 4,096 keys and 4,096 stamps184,320 bitsread from the end4,096 reads792 counters, no stamps50,688 bitsitems readsame answer: 1×700, 2×341, 3×224…W = 4,096 · φ = 0.02 · stationary Zipf9.8× fewer reads, same answer The floors

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.

 0.1%1%10%100%0.50.750.90.990.999quantile asked forrank error ÷ (1 − q)Greenwald–Khanna7,080 bitshigh-biased56,064 bitst-digest5,952 bits8 streams per point · ε = 0.01, δ = 100denominator: the tail One pass, and no room

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.

 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 What is taught wrongly

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.

 answered 4,1900%25%50%75%100%11.794,190value, logarithmicfraction of the stream at or belowrank ±2%value 24.9–4,190answered 1553.5% out20,000 values · Pareto, α = 1.2 — a heavy tail · Greenwald–Khanna, ε = 0.02rank 0.10% · value 1553.5% What is taught wrongly

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.

 ·1, 4b1, 3b1, 2b4, 2a4, 2a2, 2a4, 2b4, 2b4, 2b4, 2patterns abbb, baab, bbab · shortest 4d₁, d₂ under each node · a filled node ends a patternthe reversed-pattern trie10 nodes The data that is not a number

The shift somebody published

The exact rules for shifting a multi-pattern window are a definition that quantifies over every pattern at every offset. The 1979 rules are two tables read off the trie's own failure links, they are computed in one pass, and on this pattern set they agree with the definition at every node.

 0.01%0.1%1%10%100%1,0002,0003,0004,0005,0006,0007,0008,000keys insertedabsent keys answered yesone filterm = 19,171, k = 7; dotted: the design sizedashed: the design rate When the algorithm flips a coin

A filter past its design size

A Bloom filter sized for two thousand keys at one per cent answers yes to 15.6% of absent keys at four thousand and 68.1% at eight thousand. Nothing fails and nothing warns. A stack of filters that adds a tighter layer whenever the top one fills holds 2.0% at eight thousand, under a bound it can state in advance — in 2.9 times the bits of one filter sized for eight thousand from the start.

 good suffix, defined757,058good suffix, from links3,824bad character, defined12,666bad character, swept5,168128 patterns · 1,280 characters of patternfour symbols · m = 10198x and 2.5x What a bound is

The case a failure link does not cover

Compute the exact good-suffix rule from the failure links alone and eighteen of twenty-two entries come out too large. The matcher then steps past sixty-six of two thousand and twenty-five occurrences, and every match it does report is a match.

 1,8103,6205,4297,239010,00020,00030,00040,000arrivals so farcount of key 1 in the last 4,096Misra-Gries, no clockblocks of Misra-Griesthe truth, and the ring buffera heavy hitter that stops · sampled every 5006,493 claimed, 0 true Structures

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.

 0.01%0.1%1%10%100%1,0003,0005,0007,0009,00011,00013,00015,000keys insertedabsent keys answered yesone Bloom filtera stack of Bloom filtersfingerprints, none reservedfingerprints, 3 reservedforecast 2,000, target 1.0%; dotted: the forecastdashed: the target rate When the algorithm flips a coin

A filter that grows by moving a bit

A table of fingerprints can double in place, moving one stored bit of every fingerprint into its slot number, and so grow as one structure with one lookup where a stack of Bloom filters adds layers. Its false-positive rate is fixed by the fingerprint's length and not by the table, so with nothing reserved it doubles as the keys double — 0.69% at a forecast of 2,000, 5.7% at eight times that. Reserve three bits at the start and it holds 0.66% at eight times, in 294,912 bits, exactly what a table built for sixteen thousand keys would hold and fewer than the stack's 428,938. The reserve is a forecast of growth, and past it the rate climbs again.

 ordered by degreedegeneracy orderthe degeneracy024681012largest out-degreeuniform pairs, degree 452 above duniform pairs, degree 6136 above duniform pairs, degree 1083 above dpreferential attachment, degree 414 above dpreferential attachment, degree 622 above dpreferential attachment, degree 1058 above d1,024 verticesdashed: the degeneracy Two parameters

A bound right for the wrong reason

Orient every edge of a graph towards its higher-degree endpoint and count triangles among out-neighbours, and the work is O(E·d), where d is the graph's degeneracy. The usual reason given is that the orientation keeps every out-degree at most d. On a graph of 1,024 vertices with degeneracy four, 136 vertices have more than four out-neighbours and one has seven. The bound survives by a different argument, and the orientation that does keep every out-degree at most d does less work.

 11010³cap on the depthphrases9.8% more phrasesevery occurrence consideredthe earliest only4,096 charactersworst at cap 4 What a bound is

The cap an automaton cannot see

A state of a suffix automaton stands for a set of occurrences and hands back one of them. So a capped parse driven by it can ask whether the earliest occurrence is shallow enough and cannot ask whether any occurrence is — which costs up to 9.8% of the phrases, and only at the caps that bind.

 steps cost one to ninesteps cost one01,0002,0003,000cells expanded, mean over the gridsA* from one endalways shortestalways shortesttwo-ended Dijkstraalways shortestalways shortesttwo A*, separate estimateswrong on 12always shortesttwo A*, stop on either keyalways shortestalways shortesttwo A*, averaged potentialalways shortestalways shortest40 grids a bar, 2,500 cellsestimate: straight-line cells Two parameters

Two estimates that must agree

Run A* from both ends of a query at once, each search guided by its own straight-line estimate, and stop by the rule that is correct for two-ended Dijkstra. On 40 weighted grids it expands 1,002 cells on average and returns a longer path than the shortest on 12 of them. Give both searches one potential, half of one estimate minus half of the other, and the same rule is correct again — on all 40 grids, for 1,041 cells. Two estimates that measure different things cannot share a stopping rule until they are made to measure the same thing.

All threads