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

Sketch — where it appears

A fixed-size summary of a stream, built in one pass, answering a question chosen in advance approximately and every other question not at all. Its accuracy is bought with bits at a stated rate, so the design question is never whether it is wrong but how wrong and about what.

Named by 20 essays across 6 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 hash rowh1h2h3h4h1 → cell 30: 10,433h2 → cell 29: 10,624h3 → cell 19: 10,575h4 → cell 4: 10,895key 0 occurred 9,579 times · the minimum of the four is 10,433 · over by 854the additive bound at this width is e/w × N = 5,0974×32 counters · 4,096 bits · Zipf s = 1.1exact would take 162,288 bits

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.

streaming · Sketch 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 exact-11.2%-3.3%0.0%3.3%11.2%rmse 3.61%worst 9.71%23 of 60outside the band5,120 bits · 60 seeds · relative error of one runpredicted ±3.25%

The correction that makes it work

HyperLogLog and LogLog read the same registers and differ only in how they average them. The harmonic mean is worth 30% of the error for nothing, and below two and a half registers' worth of keys the estimator both are built on is 137% high and has to be abandoned.

streaming · Cardinality 0.010.10.11Jaccard index of the two setsrelative error of the intersectionas wrong as the answerinclusion–exclusionthe minimum valuesHyperLogLog p = 12, 20,480 bits · bottom-4,096, 131,072 bitstruth from a hash map over 200,000 keys

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.

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 01/82/83/84/85/86/87/811×1.5×2×3×5×10×share of the bits given to the HyperLogLogworst error over all overlaps ÷ the best possible1.81×switch at a crossingmeasured in advanceswitch on the textbookvariancesweight by the textbookvariances40,960 bits a set, 64 seeds, J from 0.98 to 0.001ringed: the minimax split

A budget split before the question arrives

Forty thousand bits a set, divided between a HyperLogLog and a sample of the smallest hashes before anyone knows which intersections will be asked for. Given all to either structure, the worst query is 2.7 or 12.8 times as far out as the best possible. Split in half, it is 1.8 — but only if the choice between the two estimates is made from a crossing measured in advance. The textbook error formulas make the choice wrongly on every one of 640 draws.

streaming · Cardinality 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 10,0000.1total bits of stateruns outside ±15%1 × 483 × 485 × 487 × 489 × 48240 runs per design · tolerance ±15% · truth 12,00067 → 3 failures

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.

randomness · Sketch 01/82/83/84/85/86/87/812×3×5×10×share of the budget given to the HyperLogLogworst regretswitch, textbook varianceweight, textbook varianceswitch at a measuredcrossingswitch, variance fromregistersweight, variance fromregisterstwo sets of 100,00032 groups of registers

The covariance the registers already hold

A budget split between a HyperLogLog and a sample of the smallest hashes chose its intersection estimate wrongly on every draw, because the textbook variance for a subtraction of three sketches drops their covariance. A crossing measured on calibration seeds repaired the choice at a worst regret of 1.81. Read instead from the registers themselves — thirty-two groups of them, each a small sketch of both sets and their union — the variance makes the per-draw switch match the crossing exactly, and makes the weighted mixture the best rule measured: 1.70 at the even split, and 1.42 against 1.85 when one set is ten times the other, with no calibration at all.

streaming · Cardinality 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 1101001,0000.111010010³true count of the keyrelative errorheaviest keyrarest key4×64 counters · 8,192 bits · Zipf s = 1.1 · 3,528 distinct keys at 702 positions4.11% to 34100%

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.

wrong · Sketch queries answered yesabsent key, the AND0.190%absent key, built on the intersection0.025%in one set only, the AND1.800%in one set only, built on it0.000%bits set: A 6,351, B 6,294, AND 3,232, direct 1,859no common key is ever denied

The intersection two filters cannot report

Two Bloom filters over sets that share five hundred keys, ANDed bit by bit. The result never denies a shared key, and it looks like a filter of the intersection. It is not one — a key in only one of the sets passes it 1.8% of the time where a real filter of the intersection passes none, and reading the intersection's size off its bits gives 900.

randomness · Randomness key 05,416short by 4,163key 1462short by 4,154key 31short by 2,099key 71short by 943key 19401short by 3counter held (bar) against true count (tick)12 counters · 768 bits · no randomnessbound N/(k+1) = 4,615

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.

structures · Sketch HyperLogLog1024/1024 identicalCount-Min256/256 identicalbottom-k128/128 identicalMisra-Gries20/36 identicalfraction of the state that merged to the identical value→ 1,974→ 10,291→ 2,322→ 8,766two streams of 30,000 · 2,007 distinct keys in the union3 of 4 merge exactly

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.

structures · Cardinality 1×2×5×10×20×50×100×200×00.250.50.7511.251.51.752skew of the join columnregret of the decided part, logarithmicuniform estimate4 counters a side16 counters a side64 counters a side256 counters a sideR 4,000, S 40,000, T 2,000 rows · 64-record blocks, 4,096 in memoryMisra–Gries on each side of the join column

The skew a few counters cannot repair

A join order chosen on the textbook estimate costs 243.9 times the better order at a Zipf exponent of two, and two counters a side are enough to fix it. At an exponent of one half the estimate is out by less than a factor of two, the plan it picks costs 1.37 times the better one, and no number of counters up to 256 changes that. The easy case is the extreme one, and the reason the moderate one is hard is a series that stops converging at exactly one half.

applied · Transfer Count-Min 4×64exact0 under200 overrms 303Count-Sketch 4×64-2,774-1,38701,3872,774120 under80 overrms 256cash register · insertions only, Zipf s = 1.1 · counts exact8,192 bits each

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.

structures · Moment 123451234567eighths of the budget in registersworst regret over every overlapregister variance, floor of one hashhalf a hash, estimate toohalf a hash, variance onlytextbook variancelower is better64 draws an overlap

A variance that had seen one hash

A budget of 40,960 bits split between a HyperLogLog and a bottom-k sample answers an intersection best by weighting the two estimates by their variances, except in one corner: a sample of 160 hashes asked about sets sharing one key in a thousand, where the weighting's worst regret was 4.46. The sample was said to see nothing, report a variance of nought and be believed completely. Its variance was never nought — it was taken at one shared hash whenever none was seen — and it was believed too little, not too much. Half a shared hash in the variance gives the sample more weight and cuts the corner's regret to 3.08, not under the 2.5 predicted; half a hash in the estimate too gives 3.74 there, and 1.61 at five eighths of the budget in registers, the lowest worst regret any split and rule has reached. No weighting measured gets the corner under the sample's own 2.30: 160 hashes expecting a sixth of a shared one is a limit, not a formula.

streaming · Cardinality

Named alongside it

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

EstimatorState bitsRelative errorCardinalityHyperLogLogGuaranteeStreaming algorithmVarianceBottom-kCount-Min sketchOne passUnbiased estimator

All concepts