Estimator — where it appears
Named by 31 essays across 6 fields — each of them below, with the objects they name alongside it.
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.
The state a merge is standing in for
A merge of eight summaries of thirty-two counters is wrong by 536 where one summary of thirty-two is wrong by 769, which reads as merging helping. One summary of two hundred and fifty-six counters — exactly what the eight were holding between them — is wrong by nothing at all.
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.
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.
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.
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.
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.
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.
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.
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.
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.
The matrix a corpus wrote
A substitution matrix is not a property of an alphabet. Fit one to four hundred pairs of sequences that rarely change and the dearest substitution costs five; fit the same model to four hundred pairs that often change and it costs two. Two hundred test pairs aligned under each matrix give different alignments in 115 cases — and a matrix fitted to eight pairs of the first kind moves 79 of them, from sampling alone.
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.
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.
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.
The estimate a plan rests on
A planner chooses between an index and a scan on how many rows it thinks will match, and the number it has is wrong by a factor. Guess sixty-four times too many on a narrow query and the scan it picks costs 13.5 times the index. Guess sixty-four times too few on a wide one and the index costs at most 4.01 times the scan — a ceiling that can be named before any query runs.
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.
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.
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.
The join order is a guess
Three tables, two orders, and an estimate of the first intermediate result that assumes the join column is uniform. When the column is skewed the estimate is out by seventy-two times, and the plan chosen on it costs 1.49 times the better one — which sounds tolerable until the shared output is taken away, and the part of the cost the order actually decided turns out to be 43.9 times worse.
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.
The floor a histogram already knows
A summary of thirty-two counters settles at a smallest counter of 119, and the number can be computed from the shard's key frequencies before a single counter is allocated. The obvious way to compute it is wrong by a factor of two, and the reason is that the heavy counters carry no error at all.
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.
The ties a rounded matrix makes
Measure how far each optimal alignment is from a tie — the smallest change to any one cost that makes another alignment win — and it predicts which alignments a refitted substitution matrix will move. A resample of the same corpus moves 30 of the 63 test alignments that sit on a tie and 3 of the other 137. A matrix fitted to a different divergence moves alignments far from a tie as well, and the prediction weakens to a chance of 0.62. And a third of the alignments were on a tie only because the matrix was rounded to whole bits — fitted without rounding, 15 of 200 are, and every prediction improves.
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.
What insurance against an estimate costs
A planner that trusts its row estimate expects to pay 1.057 times the better plan and risks 7.76. One that insures itself by halving its estimate before it decides expects 1.057 and risks 4.10 — the insurance is free. At a read ratio of sixteen the same insurance costs six per cent in expectation and makes the worst case worse. Whether a conservative planner is paying a sensible premium depends on two numbers the planner can measure and usually does not — its device's read ratio and the direction its own errors run.
The lattice that decides the ties
Rounding a fitted substitution matrix to whole bits puts 63 of 200 alignments on a tie where the exact fit puts 15. Rounding to half bits — a finer grain, and the obvious repair — puts 79. What tracks the ties is not how fine the lattice is but how many of the six fitted costs it keeps apart: whole and half bits both leave three, an eighth of a bit leaves all six, and matches the exact fit exactly.
The bill a partition only divides
The two predicted damages for any key sum to the same number under every partition — 967 arrivals here, whatever the arrangement. Round-robin hands nearly all of it to Misra-Gries and hashing hands most of it to Space-Saving, and neither of them is paying more than the other in total.
A decay measured from where it started
An exponentially decayed counter is one number because its weights fade by elapsed time alone. Forward decay keeps a polynomial weight in one number too, by measuring each arrival from a fixed landmark. Its memory is then a share of the time since that landmark: at β = 2 an arrival counts half at 29% of that time. Anchored at the start of a stream, it takes 5.3 seconds to register a fourfold rise twenty seconds in and 83 seconds when the rise comes at five minutes.
The histogram that cannot see the order
A prediction accurate to one per cent on three streams is seven times out on the fourth, and the input that fails is the one every capacity plan is built from. A statistic computed from the same input says in advance which case is in hand — and misses one of the two ways it can go wrong.
The warning that is silent for the right reason
The statistic shipped to warn that a merge prediction is about to fail reads 0.160 on a stationary stream, 0.172 on a bursty one and 0.909 on a drifting one. It was asked to be looked at again because it does not catch a burst. It does not, and the reason is that on a burst there is nothing to catch.
Named alongside it
The objects these essays reach for when they reach for this one.
State bitsSketchRelative errorGuaranteeHeavy hitterZipf distributionHonest limitMergeable summaryMisra–GriesOne passTrade offUnbiased estimator