When the algorithm flips a coin
A structure made of coin flips
What a skip list is, why its shape is decided before a single key is compared, and what changes when the structure of a data structure stops being a function of the data.
The height is a distribution, and the coin is a parameter
Why a skip list's height is a random variable rather than a bound, what changes when the promotion probability moves from a half to a quarter, and the three-way trade between comparisons, pointers and random bits that the choice of coin decides.
One pass, k slots, and two randomness budgets
How a uniform sample is drawn from a stream nobody has counted, what an off-by-one does to it that no correctness test would catch, and why two algorithms with identical output can differ by a factor of 145 in a resource nothing else measures.
A filter that is allowed to be wrong
What a Bloom filter is, why its false-positive rate is a measurable quantity with a closed form, and what changes when a data structure is permitted to be wrong in one direction only.
A hash is a family, not a function
Why a hash function chosen once at compile time has an input that destroys it, what universality actually guarantees, and how a family turns a claim about the data into a claim about the algorithm.
The second choice
The power of two choices, measured — how the maximum load stops growing while the mean does not move, and what the second probe costs on every lookup thereafter.
An insertion that can fail
Cuckoo hashing measured — the displacement chain, the load at which it stops terminating, and how the threshold sharpens as the table grows.
A match decided by a number
The rolling hash, why its cost has a closed form, why the closed form is an expectation rather than a guarantee, and the arithmetic that decides whether an adversary can build a collision at all.
The evidence a filter cannot remove
What deletion costs three approximate-membership structures, measured — the false negatives a cleared Bloom filter produces, the space the repairs cost, and the precondition one of them adds.
The estimate that is a median of means
Why averaging buys accuracy and only a median buys confidence, what the two purchases cost separately, and how a failure rate is measured rather than quoted.
The independence an estimator spends
k-wise independence as a measured resource — enumerated exactly over GF(13), sampled where it cannot be, and the estimator whose error stops falling when the family is too weak.
The intersection two filters cannot report
The bitwise AND of two Bloom filters against a filter built directly on the intersection. The AND keeps every shared key, but its false positives for keys in one set only are set by the other filter's load rather than the intersection's size, and a size read off its bits overstates the intersection badly while inclusion–exclusion over the union does not.
More hashes or wider buckets
The cuckoo construction's failure rate against load for several shapes — two, three and four hash functions, and buckets of one, two and four slots. Each shape has a threshold rather than a slope, the measured thresholds sit on the published ones, and the shapes differ in what a lookup reads rather than in how many keys they hold.
The tie that breaks left
The power of two choices with random tie-breaking against the asymmetric version — the table split into groups, one choice in each, ties sent to the leftmost group. Deterministic, unfair tie-breaking thins the tail by half and lowers the maximum, and the effect grows with the number of choices.
A filter past its design size
One Bloom filter filled past the number of keys it was sized for, and a scalable stack of tightening filters that is not. The single filter degrades smoothly and without limit, exactly as its formula says; the stack keeps a stated bound on its rate however far it grows, and pays for the guarantee in bits.
Choices that are not independent
Balanced allocation with d choices generated by double hashing from two hash values, against d independent hashes, on the same keys. The tails agree to within what two independent runs disagree by, for two, three and four choices — the dependence that matters is choices coinciding, and an odd step removes it.
A filter that grows by moving a bit
A quotient-style fingerprint table that doubles in place, with 0 to 5 bits of its fingerprints reserved for growth, against a single Bloom filter and a stack of tightening Bloom filters, given the same keys up to 32 times a forecast. Reserving log₂ of the growth holds the target rate and costs at the end exactly what a correctly sized table costs; the stack holds its bound at any growth and pays for it in bits that grow faster than the keys.
Two hash values and the keys they copy
Bloom filters of 64 to 4,096 bits with k from 3 to 13, their positions made by independent hashes, by h₁ + i·h₂, with the step forced odd, and with a cubic term added. The excess false positives come from queries that copy a stored key's progression, whole or shifted, and a count of those copies predicts them; a cubic term removes most of the copies and nearly all of the penalty.
The bits given to the wrong keys
Lengthening fingerprints as a resizable filter grows, measured against reserving bits in advance and against a stack of tightening Bloom filters, in rate, in bits and in how far each design can be grown before it cannot store a key at all.
Positions confined to one line
Blocked Bloom filters measured against whole-filter ones — the rate a block costs on its own at each block size and each density, the cache lines a lookup reads either way, and whether the two-hash-value construction and its cubic repair behave inside a block as they do across a filter.
Two blocks and the chances they add
A blocked Bloom filter whose keys choose the emptier of two blocks, measured against one block, one block twice as wide and the whole filter at 8 to 24 bits a key: the spread of keys a block, the false-positive rate, the cache lines an absent and a stored key's lookup reads, and every design at 20 bits a key set against the lines it costs.
A block the lookup can work out
A blocked Bloom filter whose first block carries a threshold on an ordering hash, so a lookup reads one threshold and one block rather than two blocks: the false-positive rate against one-choice and two-choice designs from 8 to 24 bits a key, the load spread each achieves, how wide the threshold has to be, and where the capacity that fills it should sit.
The day a filter cannot grow
A fingerprint table forecast for 2,000 keys at 1% and grown to 2,000,000, measured four ways: rebuilt from the store on its own rate, rebuilt only when it can no longer double, a single table with ten bits reserved for the whole growth, and a stack of tightening Bloom filters. The rate each holds, the bits each spends as the growth proceeds, the keys the rebuilds read back, what the reserve's extra bits are worth per key read if the growth stops early, and the ledger at two million keys.
A penalty set by the block
Blocked Bloom filters at sixteen bits a key — one block, the emptier of two, and one chosen by a threshold — measured over a 64-fold range of filter sizes and a 16-fold range of block widths, with the one-block rate computed exactly as Bloom's formula averaged over a Poisson load: why the size does not matter, how the busiest block grows without moving the rate, what the width does, and the line count at which a threshold and a wider block give the same rate.
The bits a second threshold costs
Blocked Bloom filters of 8,192 keys at sixteen bits a key, at block widths from 256 to 2,048 bits: one block a key, a threshold on the first block, thresholds on both of a key's blocks with a third block for keys both refuse, and one block four times as wide — false-positive rates on two million absent keys a point, the spread of block loads, the rate split into what the tables cost in load and what the spread costs, the rate against the bits a threshold is stored in, and the loads themselves.
A threshold knows only its own block
Blocked Bloom filters of 8,192 keys at 16 bits a key with one four-bit threshold shared by each group of 1 to 16 adjacent blocks, the table paid for in blocks, at 256- and 512-bit widths: the false-positive rate against group size beside one block and one block twice as wide, the rate split into its no-spread floor and the spread, where each block's own threshold closes, the share of keys placed in their first block, and two ways to close a shared threshold.
Two hashes that shared their low bits
The one-threshold blocked Bloom filter at 16 bits a key built twice from the same keys, seeds and queries — its block and ordering hashes reduced by a modulo, as the published filters were, and by their top bits: which combinations of ordering value and block the keys reach, the rate over eight seeds at four block widths, the rate against the block count, the threshold's width re-measured over four seeds, and the emptier-of-two filter, which the same dependence leaves untouched.
A code that has to fit its worst line
The one-threshold blocked Bloom filter at 16 bits a key, hashes read from their top bits, about two thousand blocks at widths of 64 to 512 bits, with its threshold table stored four bits each, three bits each, as a Huffman code from the filter's own closing distribution packed end to end with an index, and packed a fixed count to a cache line with and without in-line offsets, every table paid for in blocks: where thresholds close and each value's code word, the bits a block each layout takes, what a lookup reads and decodes, the false-positive rate over four seeds, and the table's share of the filter.
A bit for whether it closed
The one-threshold blocked Bloom filter at 16 bits a key, hashes read from their top bits, about two thousand blocks at widths of 64 to 512 bits, with its threshold table stored as a bit vector of which blocks closed plus a value for each closed block, found by rank — packed a line at a time and end to end — beside plain four- and three-bit tables and a line-packed Huffman code, four seeds a point: bits a block, the line-packed split against its mean, lines read and work done a lookup, false-positive rates by seed, and the saving against block width.
The worst of more lines
The one-threshold blocked Bloom filter at 16 bits a key, 64-bit blocks unless stated, with its threshold table split into a bit a block and a four-bit value for each closed block, packed a fixed number of blocks to a 512-bit line, the line sized for the most closed blocks any line draws or for the mean plus 0 to 2 standard deviations with the excess moved to a shared overflow found through an offset in each line, at about two thousand, sixteen thousand and a hundred and twenty thousand blocks: table bits a block against the filter's size; bits against the extra lines a lookup reads; the share of closed lookups reading the overflow; where a block's bits go; bits against block width beside plain three- and four-bit tables; and false-positive rates by seed.
An offset that only has to reach its neighbours
The one-threshold blocked filter at 16 bits a key with its threshold table split into a bit a block and a four-bit value for each closed block, packed into 512-bit lines sized for the mean number of closed blocks plus z standard deviations, a line's excess values moved to a shared overflow, the line carrying an offset sized to address a table of moved values, an offset sized to the overflow the table has, or an offset into its group's part with each group's position in an array of its own. Bits a block against the table's size, bits against lines a lookup at every z, every group size, the share of lookups whose value moved, and where a block's bits go.
A reserve sized for the spill
The one-threshold-a-block filter's split threshold table at 524,288 keys, 64-bit blocks and four-bit values, its lines sized for the mean number of closed blocks and grouped 64 at a time with a reserve of value slots a group, sized as a number of standard deviations of the group's total or for the group's expected spill: bits a block against lines a lookup for the pooled tables and the ungrouped line with its offset fitted to its overflow, how full the reserves are and how many lookups go past them, every reserve size at room for the mean, and three group sizes.
The room the lines lend
The one-threshold-a-block filter's split threshold table at 524,288 keys, 64-bit blocks and four-bit values, with no reserve: each line sized at room for the mean plus 0 to 1.5 standard deviations, and the values beyond a line's room carried forward into the empty slots of the lines after it, each line holding a count of the values still waiting: bits a block against lines a lookup beside the fitted ungrouped line and the group reserve sized for the spill, how far a carried value travels and how many lookups are carried at every room, and how far under both curves the carried table lands.
A walk that stops at two lines
A split threshold filter of 524,288 keys in 64-bit blocks with four-bit threshold values, its table's lines sized at the mean plus 0, a quarter or a half of a deviation of closed blocks, each line's surplus carried forward into the next lines' free slots for at most one, two or four lines and sent past that to a shared overflow. Bits a block against lines a lookup beside the uncapped walk, the spill-sized reserve and the ungrouped overflow line, the share of carried values sent to overflow, and every design read at equal lines a lookup.