False-positive — where it appears
Named by 10 essays across 4 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 pass that was never a parameter
One pass is the streaming model's defining restriction, and the usual way to enforce it is to make 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.
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 runs a range query can skip
A Bloom filter over key prefixes can tell a range query that a run holds nothing it wants, which a filter over keys cannot. On a four-level store of a million keys, a range expected to hold one key costs 4.76 transfers with no such filter and 2.41 with one built on 20-bit prefixes. The best length moves two bits for every tenfold longer range. By a hundred keys the most any range filter could save is a fifth of a transfer, because only the smallest level is ever empty. And the same memory spent on 20-bit prefixes makes a lookup for an absent key three times dearer.
The small levels' share of a range filter
Prefix filters on a four-level store were proposed a prefix length each, on the reasoning that one length is a compromise between levels whose densities differ 43-fold. Each level does want its own length, 18 to 22 bits, and that recovers a quarter of the gap to a perfect range filter. The gap is mostly not about length. Three fifths of it is false positives. Moving filter bits from the largest level to the small ones — 12, 12, 8 and 3 bits a key instead of 5 each — recovers more than half of it at the same memory, and matches one shared length given twice the memory.
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.
The resolution a range filter can afford
A prefix filter on each level of a log-structured store answers a range by asking one question for every prefix the range touches, and each can be wrong. A filter holding prefixes at every length from 16 to 24 bits could ask each range at the resolution it needs, and was proposed as the repair. At the store's five bits a key it costs 5.69 transfers a range query where one length a level costs 4.32, because a short range is asked only at the finest length, and that filter now holds a fraction of the memory. Asked at every length it recovers most of that, and seems to overtake the single length at twelve bits a key — but only a single length chosen for five bits. Chosen again for each memory, one length a level beats every multi-resolution design at every memory measured, because the resolution a level can afford is itself set by its memory.
One length for the gaps and the clusters
On uniform keys one prefix length a level, chosen for its memory, beat a filter holding every length from 12 to 24 bits. Clustering the keys was predicted to reverse that, because coarse prefixes between clusters are empty and a coarse filter can then say no to a long range in one question. Clustering alone does not: whether ranges fall in the gaps or at the keys, one length re-chosen for that workload still wins, since it moves coarse for the gaps and fine for the keys. The multi-resolution filter wins only where a clustered store is asked both — by 0.17 transfers a query at ten bits a key on sixteen clusters — and it wins on short ranges inside the clusters, not on long ones between them.
Two lengths that do the work of eleven
On keys that cluster, asked both between the clusters and at them, a prefix filter holding every length from 12 to 24 bits beat one length a level by 0.17 transfers a range query, and a pair of lengths — one coarse, one fine — was proposed to recover nearly all of that. It recovers more than all of it: 0.23 transfers at ten bits a key, and at four bits, where the eleven lengths lose to one, the pair still saves 0.18. The coarse filter takes under 2% of a level's memory, and the eleven-length filter was leaving its finest length as little as 14% and cannot give it more without starving the lengths its descent passes through. The store predicted to defeat a pair, with gaps at two scales, does not. The saving is bought in questions: the pair asks its filters more often than the eleven lengths do.
Named alongside it
The objects these essays reach for when they reach for this one.
Block transferBloom filterDesign parameterLsm treeMeasurementRange queryRead amplificationApproximate matchingEdit distanceFilteringPer levelSeed-and-extend