The thread: The answer is an estimate
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.
One pass, and no roomCounting 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.
One pass, and no roomA 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.
One pass, and no roomA 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.
One pass, and no roomThe 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.
One pass, and no roomThe 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.
One pass, and no roomThe 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.
One pass, and no roomThe 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.
When the algorithm flips a coinThe 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.
One pass, and no roomThe 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 floorsThe 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.
One pass, and no roomThe 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 other axisThe text that does not have to be kept
The index reproduces its text character for character, in 1,024 mapping steps and zero reads of anything. That is the whole justification for weighing it against the text rather than beside it — and the price is a dial that moves the structure by 3.3 times and the cost of locating one match by 72.
What is taught wronglyThe 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.
When it does not fitThe 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.
When the algorithm flips a coinThe 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.
One pass, and no roomA 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.
StructuresThe 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.
StructuresThe 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.
What is taught wronglyWhen 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.
When it does not fitThe 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.
What is taught wronglyA 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.
When it does not fitThe 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.
StructuresA 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.
When it does not fitWhat 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.
When it does not fitWhat a planner pays to find out what to pay
Insurance against a row estimate is set from the error's median and spread, and a running system knows neither — it has to fit them from executed queries. Fitted from one query the divisor costs 1.263 times the better plan against 1.215 for a planner that never insures at all, so learning is worse than not learning until about sixteen queries have run. The tail, though, is bought immediately: one observation already holds the worst case to 24.7 against 36.6.
One pass, and no roomA 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.
When it does not fitA summary's silence is a bound, not a count
When both sides of a join are skewed towards the same values the textbook estimate is 399 times too low and the order it picks costs 244 times the better one; two counters a side repair it. Skew them towards different values and the same estimate becomes 254 times too high — and the counters have nothing to say, because no value is in both summaries. Using their silence instead repairs the middle of the sweep and makes the far end six times worse.