A trie fitted to its queries

The columns the candidates share laid a vocabulary out as a trie and computed one column of the edit-distance table per prefix rather than per word. A bound found during the search then did more than shorten a word’s table: a column whose smallest value passes the bound proves that nothing beneath it can come close, and takes the whole subtree with it. Over the 2,424 distinct words of the collection’s fixed corpus of essays, the walk gave a column to 2,299 of the 7,709 prefixes a query — about 30% — and read 16,958 cells where a table per word read 156,714.

Its closing section noticed that everything about that structure was a property of the vocabulary and nothing a property of the queries. A search that knew which prefixes its queries actually reach could keep those and collapse the ones never reached, fitting the trie to a workload rather than to a dictionary. It asked how much of the visited 30% is the same 30% from query to query, whether collapsing the rest is worth the space, and what happens when the queries are not misspellings of vocabulary words at all — since a spelling checker’s hardest inputs are words its dictionary does not have.

This page answers all three, and the first answer removes the premise of the proposal. A stream does not choose a part of the trie. It chooses something else, and that something is worth much more.

A stream visits the whole trie #

The stream is 2,000 queries, each a word drawn from the vocabulary with one or two random typing errors: a letter inserted, deleted or replaced. A second stream of 600 queries is made the same way from words the vocabulary does not contain — 604 words from a second fixed corpus, of technical writing about programs, that the essays never use, such as instrumented, pretending and duration. Each query is walked through the trie with the bound discovered as the search goes, exactly as the earlier page walked it, and every node the walk gives a column to is recorded. Every answer is checked against the earlier page’s search.

A hundred queries have given a column to 93% of the trie between them, and two thousand to 99.5%. Any single query visits about a third, and consecutive queries share about 40% of what they visit. But the thirds are different thirds, and they cover the structure within a few dozen queries. A trie collapsed to the nodes a thousand queries never visited would collapse 88 nodes of 7,709. That is 1% of the structure, gone for nothing, since a later query can still need any of them.

The reason is in how a bounded walk spends its columns. Near the root every query visits nearly everything: the first letter or two of a query rarely rules out a branch, because a single edit can change the first letter. Deeper down, the walk follows the branches whose prefixes are close to the query’s own, and those depend on the query. A vocabulary of English words is dense at depth three or four, so across a few dozen queries with different spellings, the deep branches every query follows add up to nearly all of them.

The words the vocabulary lacks cover it even faster: a hundred of them visit 99.9% of the trie. A query with no near neighbour has a loose bound for longer and gives columns to more of the structure before it finds one.

Where the visits concentrate #

Visited at least once is not the same as visited often, and the second is what a structure could exploit.

The visits are concentrated, and the concentration generalises from one set of queries to the next. The quarter of the prefixes that the first thousand queries visited most holds 72% of a later query’s visits. That is roughly the 80–20 shape of most workloads, and it survives on queries the ranking never saw. It survives less well on misspellings of words the vocabulary lacks, 58%, because those queries go down branches the vocabulary’s own misspellings rarely do.

What a hot core can buy is not pruning, since the cold three quarters are still visited. It can buy placement: storing the most-visited quarter of the nodes together, so a walk’s columns are computed from nodes that share cache lines. That is the question the count is not the time keeps separating from the cell count, and it is not measured here. What is measured is that a stream does not identify anything that can be thrown away.

What the stream does know #

The structure is the wrong thing to fit, then. But the proposal’s instinct — that a stream of queries tells a search something its vocabulary does not — is right about something else.

The stream knows how far its answers lie. Every misspelt vocabulary word has an answer within two edits, because a word with at most two typing errors is at most two edits from the word it came from. The typo sometimes lands on another word instead, which is why a few are at distance zero. That fact is not visible in the vocabulary and not in the trie; it is a property of the queries, and a stream reveals it after a handful of them.

The bound the search finds for itself put a price on not knowing the answer’s distance: a search told the true distance in advance reads far fewer cells than one that must discover it, because a tight bound prunes from the first column. On the trie the earlier page measured that price at 4.66. A stream offers a way to pay much less of it without being told anything: guess the bound from the answers the stream has already produced, start there, and widen only if nothing is found.

Starting from a bound, and paying when it is wrong #

For misspelt vocabulary words, starting low is worth nearly everything the oracle is worth. From a bound of one — widening to two when nothing is found, which 41% of queries need — the search reads 3,726 cells a query, against 17,621 for discovering the bound and 3,268 for being told the answer. A guess of one edit, widened once when wrong, recovers 96% of the gap to an oracle. Starting at two needs no widening at all and reads 4,865. Each bound above that reads more, because a looser bound prunes less, until at five the search is nearly as expensive as discovering.

For misspellings of words the vocabulary lacks, the same scheme is a disaster. Starting at one costs 102,691 cells a query, nearly three times discovering the bound, and starting at five still costs 90,861. Their answers spread from 0 to 22, and a search that widens one step at a time pays a full bounded walk at every step it takes. A query whose answer is at distance 7 walks the trie at bounds 1, 2, 3, 4, 5, 6 and 7, and each of those walks is a substantial fraction of the discovering walk, which found some word at distance 7 or so early and pruned from there.

So the scheme is right exactly when its guess is right, and the stream that makes the guess is only reliable for the kind of query it has seen. That is the same shape as the placement what the queries know that the map does not fitted to a destination and then watched decay when the traffic moved: what a workload teaches is worth a great deal on that workload and can cost more than nothing when the workload changes.

A bound learned from the stream, on a stream that changes #

A real spelling checker sees both kinds of query mixed, and it cannot know in advance which one it has. The measurement that settles what to do mixes the two streams in stated shares and learns the starting bound as it goes: the median distance of the last 200 answers. Two policies use it. One widens by one until it finds a word. The other tries the learned bound once and, if nothing is within it, gives up on the guess and runs the discovering walk.

Widening from the learned bound is the best policy on a pure stream and the worst once a fifth of the queries are unfamiliar. It reads 3,812 cells a query when every query is a misspelt vocabulary word, less than a quarter of discovering. Each unfamiliar query costs it about three discovering walks, so its average climbs past discovering’s between 15% and 20% unfamiliar queries: 16,990 against 20,097 at 15%, 23,555 against 21,090 at 20%.

The single try never costs more than discovering, at any mixture measured. It reads 10,061 cells on the pure stream — worse than widening, because the median answer there is one edit and 41% of queries need two, and each of those pays the one-edit walk and then a full discovering walk. It reads 13,028 at a fifth unfamiliar, 38% under discovering’s 21,090. Its downside is capped at one bounded walk per query, and a bounded walk at a small bound is cheap.

The two policies are the two ends of a familiar trade. Widening is the bet that the stream’s past is a guide to its next query, taken at full stakes; the single try is the same bet with a floor under it. On a workload that is known to be homogeneous the first wins by a factor of 2.6. On one that is not, the second is the only one that never loses. A refit that changes one landmark reached the same kind of answer about when a learned placement should be trusted, from the counting of cells in a different search.

The learned quantile is a second dial, and it moves the pure stream’s cost more than the mixture’s. Set at the 80th percentile rather than the median, the learned start on misspelt vocabulary words is two, which contains every answer; the single try then never falls back and reads 4,938 cells, close to widening’s 3,812. Misspelt words the vocabulary lacks cost it 39,063 against discovering’s 35,306 — 11% more, the price of one wasted walk at bound two.

A stream that changes its mind #

A mixture that is the same all the way through flatters any learned quantity, because the median of the last two hundred answers is always about the same. A stream that changes kind is the harder test: a thousand misspelt vocabulary words, then the 600 words the vocabulary lacks, then a thousand more familiar ones.

The learned median notices both changes quickly. Fifteen queries after the switch to unfamiliar words it has moved from one to at least two, and it comes back to one 163 queries after the switch back — the time it takes the last two hundred answers to be mostly familiar again. With a window of twenty answers rather than two hundred, it notices the first switch in eleven queries and the second in fifteen.

Noticing is not the same as being right. Over the whole switching stream, widening from the learned bound reads 26,162 cells a query with the short window and 26,228 with the long one, against 21,702 for discovering. The median of the unfamiliar answers is three, but their tail runs past twenty, and widening one step at a time from three still pays for every step to the tail. The single try reads 15,438 and 16,079. Its guess is wrong as often as widening’s, and every wrong guess costs one cheap walk and never a succession of them.

So the window is a minor dial and the policy is the major one. A learned bound follows a stream within a few dozen queries either way. What decides the cost is what a search does in the queries where the guess is wrong, and a policy whose wrong guesses are cheap does not need its guesses to be good. It is the trade what insurance against an estimate costs priced for a query planner: a planner that insures itself against a wrong row estimate gives up a little on the queries where its estimate was right, to cap what it loses on the ones where it was not. Here the premium is the one-edit walk a familiar query wastes when its answer is two edits away — the reason the single try reads 10,061 cells on a pure stream where widening reads 3,812 — and the cover is the succession of walks an unfamiliar query never has to make. Whether the premium is worth paying depends on how often the insured event happens, and at a tenth of the stream it already is.

What was measured and what was not #

One vocabulary and one kind of misspelling. The queries have one or two random errors, drawn uniformly from insertion, deletion and substitution. Real typing errors are not uniform: transposed letters and errors near the keyboard’s neighbours dominate, and a real checker’s answer distances would pile up even more tightly at one. That would make the learned bound more valuable, not less.

The words the vocabulary lacks are a particular sample. They come from a second fixed corpus of technical writing, so they are technical English words, often longer than the essays’ vocabulary. A stream of proper names, foreign words or random strings would spread its answers differently, and every number on the mixed plate depends on that spread.

Cells, not time. Every count is a cell of an edit-distance table, which is the earlier pages’ unit. The two policies do different amounts of bookkeeping per query, and the placement a hot core would allow is a question about cache lines rather than cells. A band as wide as the answer is the other way this table is commonly cut, and its savings are counted in the same unit.

The collapse was not built. The visited-node counts say what a collapsed trie would have saved — 88 nodes after a thousand queries — and that was judged not worth building. A collapse fitted to a much larger vocabulary, where the deep branches are sparse, could find more to remove, and the count here is specific to a vocabulary of a few thousand words.

Still open: the bound as a function of the query #

The learned bound here is one number for the whole stream: the median of recent answers. But the stream says more than that. A query’s own length and letters predict its answer’s distance. A long query with letters in an unusual order is more likely to be a word the vocabulary lacks, and a short query that is one letter off a common prefix is almost certainly a misspelt vocabulary word. The filter that feeds the table decided which candidates reach a table at all from a cheap test on each one, and the same kind of test could decide which bound a query starts from.

The measurement that follows predicts each query’s starting bound from features the search can compute before walking: its length, whether its first three letters are a prefix in the trie, and the distance at which the walk’s first column stops shrinking. It asks how much of the gap between the single try’s 13,028 cells and an oracle’s it closes on the mixed stream. The prediction is that the first-three-letters test alone separates most unfamiliar queries — a misspelling of a vocabulary word usually keeps a real prefix, and a word the vocabulary lacks often does not — so a two-bound policy, a start of one for queries with a known prefix and discovery for the rest, should come within a small factor of widening’s 3,812 on the pure stream and stay under discovering on every mixture.