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

Counting filter — where it appears

A filter that keeps the windows sharing at least m + 1 − q(k+1) q-grams with the pattern, and hands those to the expensive stage. It reads every character of the text exactly once and cannot skip, so its saving is in cells computed rather than in characters examined.

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

bits used · answers that were wrongBloom, bits cleared16,384 bits638 said no wrongly · 14 said yes wronglycounting, 4 bits a cell65,536 bits0 said no wrongly · 42 said yes wronglyfingerprints in two slots32,768 bits0 said no wrongly · 153 said yes wronglyand the condition on the caller1,000 deletions of keys never inserted lost 15 that were2,000 keys, 1,000 deleted, 20,000 absent keys querieda false negative is a different kind of wrong from a false positive

The evidence a filter cannot remove

A Bloom filter never says no about a key it holds, and that is its whole guarantee. Clear the bits of a thousand deleted keys and it starts saying no about 638 of the thousand it still holds. A counter in every cell repairs it at four times the space; a fingerprint repairs it at twice, and acquires a condition on the caller that neither of the others has.

randomness · Randomness 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 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 the whole table60,00060,000r · 0rkcounting filter24,84315,369r · 0rkseed filter17,7452,415r · 1,377rkindex walk00r · 177,046rkn = 3,000 · m = 20 · q = 4cells drawn · r = characters read, rk = index rankscells computed6 occurrences

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.

wrong · Distance

Named alongside it

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

Approximate matchingEdit distanceFilteringMeasurementQ gramSeed-and-extendSelectivityVerificationFalse-positiveUnit of costAlphabet sizeApproximate membership

All concepts