Relative error — where it appears
Named by 18 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.
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 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 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 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.
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.
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 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.
A distribution computed rather than sampled
Quicksort with a random pivot makes a random number of comparisons, and every plate on this site reports one draw from that distribution. The distribution itself can be computed exactly — every pivot, every split, weighed — and on sixty-four elements its mean is 360.706 and its standard deviation 36.741. A hundred real runs average 365.98; two thousand average 360.74. The exact answer says how many runs a sample needs, and it is fewer as the input grows.
The cheap tail and the expensive merge
A summary whose tolerance tightens towards the tail keeps seven times the tuples of a plain one on a single pass, and after merging sixty-four shards it keeps three and a half times as many. The error function that buys a useful tail promise is also the one that pays most for never having the values in one place.
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 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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
EstimatorSketchState bitsTrade offCardinalityGuaranteeStreaming algorithmUnbiased estimatorVarianceBlock transferCardinality estimateHyperLogLog