Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

False-positive — where it appears

Something a filter or a summary reports that is not there. Several structures here buy their size entirely with them, so a rate quoted without one is a cost reported without its accuracy.

Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.

pattern of 24, 3 errors allowedpositions in the text20,000candidates proposed140candidates verified140occurrences7pattern 24 · 3 errors · 28,700 cells against 480,000selectivity 5.0%

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.

text · Distance above 0.01 of the stream · 13 really areone pass: 18 candidatestwo passes: 13 keys, exactly the heavy ones123456789101112131415161718128 counters · carry 1,376 bits5 of 18 spurious

The pass that was never a parameter

One pass is the streaming model's defining restriction, and this collection has enforced it by making a second read throw. A prohibition cannot be swept. Turn it into a dial and the first thing it says is that a second pass turns eighteen candidate heavy hitters, six of them wrong, into twelve that are exactly right — for 3,680 bits carried across the boundary and no extra space at all.

bounds · Pass k = 0k = 1k = 2k = 3k = 4k = 5k = 6q = 223211917151311q = 3221916131074q = 4211713951-3q = 520151050-5-10q = 6191371-5-11-17q = 81791-7-15-23-31a shaded cell is a threshold of zero or less: every window proposedt = m + 1 − q(k+1) · m = 2411 collapsed cells

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.

text · Distance 100.0010.010.1fraction of the text proposedlog_4 n = 7.101234,56,7seed length, characters · errors allowed abovepattern 24 · text 20,000 · four symbolsrings: the closed form

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.

wrong · Distance 0.010.11errors allowed, kshare of windows proposed01234q = 3q = 4q = 5a shaded dot is a collapsed thresholdm = 24 · n = 4,000 · 6 planted1 collapsed rows

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.

wrong · Distance

Named alongside it

The objects these essays reach for when they reach for this one.

MeasurementApproximate matchingEdit distanceFilteringSeed-and-extendHonest limitSelectivityVerificationCounting filterPigeonholeQ gramThreshold

All concepts