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

Estimator bias — where it appears

A systematic difference between an estimator's expectation and the truth, which more runs make more visible rather than smaller. It is the one error that averaging cannot remove, which is why a correction term is part of a structure's specification rather than a refinement of it.

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

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 H0H1H2H3H4model order — symbols of contextbits per symbol0.02.14.2Uniform over 8 symbolsOrder-1 Markov chainWords from a fixed vocabulary32,768 symbols · at H4 the deepest source has 709 contexts, 0 seen oncemodels: orders 0, 1, 2, 3, 42.06 bits found by one symbol of context

The model is the compressor

One stream of 32,768 symbols has an entropy of 3.886 bits per symbol, and 2.243, and 1.186, and 0.991, and 0.909. All five numbers are correct, all five are floors, and nothing about the data changed between them. The only thing that changed is how many preceding symbols the model was allowed to look at — which makes the entropy of a file a property of a decision rather than a property of a file.

text · Bits 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.60.81.01.21.41.61.84φ share 0.908φ share 0.8516φ share 0.8032φ share 0.7564φ share 0.70predicted ÷ measuredshards, mlevel floors, uncorrectedleaf floorslevel floors, correctedk = 32 · hashed · 40,000 arrivalsworst 22% against 73% and 46%

The floor a merge does not settle at

Compute a fold's level floors from the shard histograms and the prediction over-shoots by 1.73. A merged summary's floor is not the floor a summary settles at on the same arrivals — it is 0.90 of it at four shards and 0.70 at sixty-four, straight in log₂ m at a 3% residual, because merging preserves the heavy counters and never runs their eviction cascade.

wrong · Merge

Named alongside it

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

EstimatorMorris's counterRelative errorSketchUnbiased estimatorAdaptive codingCardinalityClosed formConditional entropyConstant factorContext modelCurve fitting

All concepts