Output-sensitive — where it appears
Named by 25 essays across 10 fields — each of them below, with the objects they name alongside it.
A band as wide as the answer
If two strings are close, the optimal route stays near the diagonal and nine cells in ten cannot be on it. A band of three finds the right answer on a pair 300 characters long — and a band of thirty-two is needed before anything can prove it.
The cells that were never worth having
Two three-hundred-character strings over twenty-six letters give a table of 90,601 cells, and 3,421 of them are pairs of positions whose characters agree. Only those can lengthen anything. A method that enumerates exactly those computes a twenty-sixth of the table — and on a two-letter alphabet it computes half of it and is worse than the table it replaced.
The bound the search finds for itself
A spelling checker that computes the full edit-distance table against every word in a 2,424-word vocabulary fills 156,714 cells for each misspelt query. Bound each table by the best distance found so far, and abandon it the moment a whole row exceeds that bound, and the same search fills 40,273 and finds the same words. Meet the candidates nearest in length first and it fills 26,203, starting a table for exactly the words a search that knew the answer in advance would start. The last factor of 1.7 is the price of not knowing, and it is largest when the misspelling is smallest.
The columns the candidates share
Three thousand tables against one query, and most of them begin the same way. Stored as a trie, the 2,424-word vocabulary has 7,710 distinct prefixes holding 17,239 letters, and a search that computes one column per prefix reads 61,449 cells against 156,714 — before it applies any bound at all. Apply the bound at a prefix instead of at a word and it reads 16,958, beating a list search that was told the answer in advance.
The candidates a filter cannot avoid
A phrase index answers a search by intersecting two ranges of boundaries, and it does the intersection by walking the smaller one. On a collection of thirty-two copies that is 4,355 phrase examinations to produce 32 occurrences — 136 examinations each, and rising.
The cost that is the size of the answer
Ten range-minimum queries answer the listing at every point of a sweep where the occurrences run from 30 to 790. They cost 256 to 288 node visits — and the scan they replace costs 30 to 790, so the output-sensitive method loses until about thirty occurrences per document.
What the generated collection was right about
Five strands of conclusions, drawn on collections made by one line with one dial, checked against a corpus nobody made. Most hold. One headline was a property of the generator's alphabet, and one crossing that was guessed at turns out to be met — but only with the structure the strand on range minima built.
Work that falls as the answer grows
Output-sensitive usually means the cost rises with the answer instead of with the input. A descent over a document array costs five operations per document at an answer of seven and two at an answer of thirty-two, because the paths to many leaves share their tops.
The count of the part that was read
Handing back the smallest ten of 65,536 keys in order costs 965,656 comparisons by sorting them and 65,670 by a knockout tournament, against a floor of 65,526. Read to the last element, the same tournament makes exactly merge sort's 965,656 — it is merge sort, charged one element at a time. A sort's count has no term for how much of its answer anyone reads, and the two floors that do have one cannot simply be added.
The structure paid for before the first query
The two grids that make a phrase index's search proportional to its answer are 3,240 bits on an 8,892-bit index — twenty-seven per cent of the whole structure, answering nothing on their own, and 38% of them is rank directory rather than payload — the lower-order term of the published bound, measured.
A list of documents is not a list of occurrences
A pattern occurring 790 times in eight documents has an answer of size eight. Reading every occurrence to find out costs 790 array reads; the question a collection has that a text does not is the one its index does not answer.
Where a crossing moved to
The prediction was that a succinct range minimum would move the document listing's crossing "to a handful". It moves it from 32 occurrences per document to 11 — a factor of three, not an order of magnitude — because a constant-time query is ten lookups rather than one.
Two floors that can be added
Handing back the ten smallest of 65,536 keys has two floors under it and neither is close where they cross — the larger of the two is 63,821 comparisons at k = 4,000 and the best method makes 125,401. They can be added, because a comparison that eliminates a key the caller never sees can never be a comparison that orders two the caller does see. Charged together the floor rises 62%, and the tournament goes from 1.97 times it to 1.21.
A rectangle over a permutation
Two orderings of one set of boundaries are two permutations, so a phrase index's intersection is a rectangle over a permutation grid — the one point set a wavelet tree stores exactly, at one bit per point per level and no coordinates at all.
The comparisons that name the answer
Returning the 4,000 smallest of 65,536 keys in order needs 61,536 comparisons to eliminate the rest and 42,100 to order the ones returned. That was the floor, 103,636, and a tournament made 125,388. What the floor never charged is saying which 4,000 come back. Charge that, and the floor is 125,341. On the same input the tournament is 47 comparisons above it, and for every k up to a hundred it is exactly on it.
The shape a range question is about
A range minimum is a question about a tree, and the tree is determined by the array. Twelve values, eleven parent links, and the answer to every one of the seventy-eight ranges is a lowest common ancestor — with the values themselves no longer needed.
The crossing that never arrives
Output-sensitive document listing exists because a pattern can occur four thousand times in eight documents. On a real collection of two thousand short documents it occurs 1.04 times per document, and the whole apparatus buys nothing at all.
The cell nobody filled
Every structure here was measured either on one long repetitive text or on prose cut into short documents. The collection that is both is a two-by-two with one empty corner, and what is in it is not the product of its margins.
The operations a candidate count leaves out
The grid examines 33 candidates where the scan examines 4,355 — a factor of 132. Counted in the operations each of them performs, the same query is 2,471 against 4,355, and the factor is 1.8.
The array the walk never reads
Document listing compares a chain entry against the start of a range. The comparison is true exactly when the document has not been reported yet — which the walk already knows, because it just wrote it down.
A document already in the answer
The same walk, with the chain's test replaced by a lookup in the answer so far. It reports the same documents at the same cost, and two exchanged lines make it lose nine of seventeen without failing.
The tree answers the question
The distinct documents in a range of rows are the distinct symbols of the document array in that range. A wavelet tree enumerates those in one descent, so the range minimum, the chain, the bitmap and the recursion all go at once.
The apparatus that is smaller than its index
Answering "which documents hold this" at a price proportional to the answer used to cost 2.70 times the index it sits beside. Two changes later it costs 0.84, and the largest thing left is an array that says which document each row belongs to.
One copy per document is one occurrence per document
The output-sensitive listing apparatus wins when a pattern occurs far more often than it occurs in documents. A collection of versions was supposed to be that case, and it is the one collection where the two numbers are equal by construction.
The last array in the apparatus
The document-listing apparatus began as three arrays beside a suffix array. Two of them turned out to be machinery for reading the third, and both have gone. What is left is the document array, and it is the only one of the three that was information.
Named alongside it
The objects these essays reach for when they reach for this one.
Document listingRange minimumIndex sizeDocument arrayLower boundMeasurementTrade offCorpusDocument collectionSuffix arrayWavelet treeConstant factor