Every essay — page 12
What a bound is Counting The floors What the machine does Structures Two parameters The other axis When the algorithm flips a coin What the libraries do When it does not fit One pass, and no room The data that is not a number When the algorithm is a table The index that replaces the text What is taught wrongly Ladders Objects Search
The other axis
Auxiliary space, counted at the point it is taken. "Sorts in place" turns out to cover three behaviours that differ by a factor of n, and one of them runs out of stack.
A bit for every bit
A grid over 3,612 points is 43,344 bits of payload. The smallest any structure can be that distinguishes one permutation of 3,612 things from another is 37,485. There is 16% to play for, and the deferral that asked for a compressed grid assumed there was much more.
An index that cannot locate
Take an FM-index, remove the sampled positions and the bit vector marking them, and refuse every request for a position. What is left still counts, still extends intervals, still runs a whole search — and is a third smaller.
What the chain cost
The chain of previous occurrences is one row number per row — exactly as wide as the suffix array it sits beside, and the largest single part of a document-listing apparatus. It is now absent, and what replaces it is one bit per document.
Two currencies for one separator
Giving every document its own boundary marker costs a fifth of the packed text and three per cent of the run count. Both numbers are right, they are about the same change, and which one a collection pays depends on a structure nobody named.
The array that says where is twice the samples
An index keeps one suffix-array value in every thirty-two, and a bit vector over all n rows saying which. The vector is sixteen thousand bits and the values it points at are seven thousand — the index of the samples is twice the samples.
The apparatus, three times smaller again
Eight hundred and thirty-nine thousand bits became two hundred and eighty-five thousand, and now a hundred and twenty thousand. The listing apparatus is fourteen per cent of what it was and holds one array, which is the only part of it that was ever information.
The ladder, and the rung that spends
Two hundred and fifty thousand bits, then two hundred and twenty-six, then two hundred and eleven. The fourth rung takes the whole saving and buys a four-times denser sampling with it, landing at ninety-six per cent of where it started and locating several times faster.
Half an index is three permutations
A phrase index stores a length, a source and a literal per phrase — and three orderings of its boundaries, at forty-five per cent of the structure. One of the three is the inverse of another, and nothing needs both at once.
Sparse on average, dense where it gathers
The r-index keeps one suffix-array value for every run of its transform and prices the set as Elias–Fano: on 32 exact copies of 2,048 characters that is 666 values among 65,537 positions at 9.04 bits a value, as though they were spread evenly. They are not — 663 sit in one copy. Cut into chunks of 32 values, each held by whichever of a bitmap, its own Elias–Fano or a run is cheapest, the same set costs 4.48 bits a value, under the 8.05 that any representation of an arbitrary set of that size must spend on some set. At a divergence of 0.0005 the saving is a fifth, and from one character in five hundred it is nothing but the select directory, which the chunks replace with reading. On the scattered marks of an ordinary index the partition saves only that directory too.
Cuts that follow the gathering
Cutting an r-index's run-start values into chunks of a fixed count left chunk edges inside the places the values gather. Choosing the cuts as a shortest path through the sorted values was predicted to save a further tenth on exact copies by cutting once at each edge of the gathering. It cuts there, and saves more than a quarter: two chunks, one of them a bitmap of 664 values that a select must scan from its start. Capped at the chunk's old size, the optimum keeps the reads and saves 9% on exact copies and 15% at a divergence of 0.0005. On moderately drifted copies the uncapped optimum is smaller and cheap to read at once.
A select that starts near its answer
The cheapest partition of an r-index's run-start values held exact copies in two chunks, one a bitmap of 664 values that every select scanned from its start: 1,065 bits read a select. Capping the chunks bought the reads back by giving up the saving. A select sample every 64 values inside each chunk, its bits charged in the same shortest path, was predicted to bring the uncapped optimum under 150 bits a select for under 3.5 bits a value. It reads 111 for 3.45, where the cap that reads as little costs 3.68. And the middle divergences, predicted to be untouched because their chunks were short, lose two fifths of their reads to the same samples.
A sample that has to be found
A select sample every 64 values inside the cheapest partition of an r-index's run-start values cut a select's reads from 1,065 bits to 111 on exact copies. Samples by count bound how many values a select passes, not how many bits it reads, so samples every 128 bits of a chunk's vector were predicted to read a third less on the sparse, drifted sets at the same cost. They bound the scan as promised, but a rank sample does not say which sample a select needs, and finding it by binary search costs a select up to a third of what it reads. The two kinds of sample end up on one frontier, and the rank samples' advantage is that they come in finer steps.
A second level that pays in one band
A select on a chunked bit vector can be helped two ways: a select sample every t values says where to start but not how far to scan, and a rank sample every s bits bounds the scan but must be searched for. A directory with both — select samples that name a rank block, rank samples that bound the scan — was predicted to reach under 70 bits read a select for under 3.6 bits a value on an r-index's run starts over exact copies, a point neither kind reaches. It reaches 62 bits read for 3.76 bits a value, which neither kind reaches, and costs 3.73 within 70 bits where the better single kind costs 3.93; but under 3.6 bits a value it reads 84. The select sample names a block two rank samples away, not one. Across eight sets the second level saves more than a twentieth of a bit a value on three, and only between about 65 and 100 bits read a select: outside that band either single kind is as good.
One pass, and no room
The data goes past once and there is not room to keep it. What survives is a summary of a few hundred bits, and the answer it gives is wrong — the whole design is a choice about how wrong, and every structure here buys accuracy with bits at a rate that can be measured.
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.
The partition the analysis did not mention
Space-Saving and Misra-Gries are the same structure under a stream, related by subtracting one number. Sharded eight ways and merged, one of them is wrong by 313 where the other is wrong by 927 — and swapping how the arrivals were assigned to machines reverses which is which.
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.
A window that is a duration
Nobody asks for the error rate over the last four thousand and ninety-six requests. They ask for the last five minutes. The two are the same question exactly when the arrivals are evenly spaced, and on a stream whose rate drifts they disagree about fifty-seven per cent of the counts.
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.
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 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 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 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 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 bits that say when
A windowed cardinality estimator holds 4,592 bits and 2,392 of them are clocks. Every summary in this collection has reported its size from the shape of its own structure, and not one of those numbers has ever been asked what the bits were for — so the resource that half of these structures spend most of their state on has been invisible while being counted.
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.