Seed-and-extend — where it appears
Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.
The filter that feeds the table
A self-index answers exact queries and nothing else. Approximate matching needs a table with twenty thousand columns in it. The pigeonhole joins them — cut the pattern into k+1 pieces and at least one occurs exactly, and the index that cannot answer the question decides where to ask it.
The q-grams an error cannot destroy
A pattern of twenty-four characters holds twenty-one four-grams. Two errors can destroy at most eight of them, so any occurrence with two errors still shares thirteen — and a filter that keeps only the windows sharing thirteen proposes 104 of 3,977 and computes 16,744 table cells instead of 96,000.
The filter that proposes everything
Seed-and-extend saves two thousand times the work at zero errors and costs more than doing nothing at four. Between them the selectivity falls through the floor, and where it falls is set by two numbers that can be computed before the filter is run — one of which does not contain the length of the text at all.
The threshold that reaches zero
At q = 5 and four errors on a twenty-four-character pattern the filter demands zero shared q-grams, proposes all 2,977 windows, and computes 986,266 table cells where filling the whole table would have cost 96,000. The failure is arithmetic and is knowable before a character is read.
Three savings in three currencies
The same six occurrences, found four ways. The table computes 60,000 cells and reads 60,000 characters. The counting filter computes 6,251 cells and reads 13,022 characters. The seed filter computes 3,325 and reads 550. The index walk computes none, reads none, and performs 18,645 ranks.
Named alongside it
The objects these essays reach for when they reach for this one.
Approximate matchingEdit distanceFilteringMeasurementFalse-positiveSelectivityVerificationCounting filterQ gramFM-indexHonest limitPigeonhole