HyperLogLog — where it appears
Named by 10 essays across 3 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.
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.
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.
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.
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.
A 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.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
CardinalitySketchState bitsBottom-kEstimatorRelative errorInclusion exclusionJaccard indexVarianceError propagationHash functionMergeable summary