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

The thread: The structure is a coin flip

A skip list's express lanes are not placed where the keys need them; they are placed where the coins fell, before a single key was compared. Build it twice and it is two different objects, so one build is an anecdote and the distribution over builds is the result.
level 1level 2level 3level 4level 5key 21search: 8 comparisons, 3 hops26 keys, p = 0.5, seed 2026081057 coin flips decided the shape When the algorithm flips a coin

A structure made of coin flips

Insert the same 512 keys into a skip list twice, once sorted and once shuffled, from the same seed, and the two structures are identical — the same 11 levels, the same height for every key, the same silhouette. Nothing about the data reached the layout. The 1,064 coin flips did all of it.

 share of nodespredictedlevel 149.68% · 50.00%level 225.29% · 25.00%level 312.52% · 12.50%level 46.24% · 6.25%level 53.08% · 3.13%level 61.64% · 1.56%level 70.79% · 0.78%level 80.34% · 0.39%20,000 nodes, p = 0.5, seed 5150worst departure 0.32 points When the algorithm flips a coin

The height is a distribution, and the coin is a parameter

A skip list over 2,048 keys is described as being about log₂ n levels tall. Across two hundred builds of exactly those keys its height ranged from 9 to 19. The number in the description is the mean of something, and choosing the coin is choosing which something.

 46810120.010.1bits per element (m / n)false-positive ratemeasured(1 − e^(−kn/m))^kfrom the bits set60,000 absent-key queries per point, seed 80800 false negatives at every size When the algorithm flips a coin

A filter that is allowed to be wrong

A Bloom filter holding four thousand keys in five thousand bytes answers membership in four memory probes and gets 1.14% of its negative answers wrong. It never gets a positive one wrong. That asymmetry is the whole design, and the rate it makes errors at is a third quantity beside the operation count and the space.

 root, priority 0.9651.00.0prioritykey24 keys, sorted insertion, seed 20260810height 8 against an ideal of 4 Structures

The priority nobody supplied

Insert 4,096 sorted keys into a binary search tree and it reaches height 4,095, costing 8,386,560 comparisons to build. Give every key a second, random key and keep the tree heap-ordered on that instead, and the same insertion reaches height 26 for 32,750 comparisons. Nothing detected the imbalance, and nothing rebalanced.

 024681,0244,09616,38465,536262,144keys, into as many bucketskeys in the busiest bucketone hashtwo hashes, take the emptierthree hasheslog n / log log nthe average load is 1 at every pointa lookup examines every choice, so two hashes is two probes When the algorithm flips a coin

The second choice

Two hundred and sixty thousand keys into as many buckets. Under one hash the busiest bucket holds eight; under two, with each key going to whichever of its two is emptier, it holds four. The mean is exactly one in both. Nothing is rearranged afterwards, no key is ever moved, and the whole of the improvement is in a decision taken once, at the moment the key arrives.

 0%25%50%75%100%0.30.40.50.60.70.80.850.90.95keys per slotconstructions that failed2 hashes, 1 slot3 hashes, 1 slot2 hashes, 2 slots2 hashes, 4 slots20 constructions a point, 256 bucketsa lookup reads hashes × slots, whatever the keys When the algorithm flips a coin

More hashes or wider buckets

A cuckoo table with two hash functions and one slot per bucket cannot be built past about half full. Give it a third hash function and it builds to 0.92. Keep two hashes and give each bucket two slots and it builds to 0.89; four slots, past 0.95. Every shape keeps the worst-case lookup the plain table was built for, and every shape pays for its threshold in a different place.

 2 halves, ties go left2 choices, ties at randomone choiceload 2 or more14,61015,03717,363load 3 or more2675785,250load 4 or morenone11,236load 5 or morenonenone223load 6 or morenonenone36load 7 or morenonenone2load 8 or morenonenone165,536 keys and buckets, seededbar length is log(1 + count) When the algorithm flips a coin

The tie that breaks left

Two choices per key, the emptier bucket wins, and when the two are equally full a coin decides. Replace the coin with a rule — split the table into halves and always send a tie to the left one — and on a million keys the buckets holding three or more fall from 9,316 to 4,694, and the busiest bucket drops from four to three. The hashing, the probes and the keys are unchanged, and the rule spends no randomness at all.

 0.00%0.05%0.10%0.15%256 bits · one block0.148%256 bits · a threshold on the first0.089%256 bits · thresholds on both0.095%512 bits · one block0.089%512 bits · a threshold on the first0.062%512 bits · thresholds on both0.066%1024 bits · one block0.066%1024 bits · a threshold on the first0.058%1024 bits · thresholds on both0.052%with no spreadwhat the spread adds16 bits a key, 8,192 keysno spread: every block at its mean load When the algorithm flips a coin

The bits a second threshold costs

A blocked Bloom filter whose first block carries a threshold was proposed a second threshold on each key's second block, with a third block for keys both refuse. It does what it was meant to: at 512-bit blocks it removes nearly a third of the load spread the first threshold left. And the rate does not fall — 0.066% against 0.062% — because the second table, paid for in blocks, raises the rate the filter would have with no spread at all by more than the narrower spread saves. The threshold was stored in more bits than it needs: at four to six bits, one threshold beats the eight-bit design by about a tenth on one run, and a second threshold of the best width ties it at 512-bit blocks.

 124816adjacent blocks sharing one thresholdfalse-positive rate0.06%0.08%0.10%0.12%0.14%256-bit blocks512-bit blocks256: one block, no threshold256: one block twice as wide8,192 keys, 16 bits a keyfour-bit thresholds When the algorithm flips a coin

A threshold knows only its own block

A blocked Bloom filter that gives each block a threshold on a hash of the key lets a lookup work out which of two blocks a key went to, and it spends a small table to do it. Sharing one threshold among a group of blocks would shrink the table, and was proposed as the next saving. It is a loss at every group size. With one four-bit threshold a block, 512-bit blocks reach a false-positive rate of 0.061%; shared by a pair, 0.071%; shared by sixteen, 0.100%, worse than no threshold at all. Neighbouring blocks fill at unrelated moments, so a shared threshold closes when the first of its group does, and every key it turns away lands in a second block chosen at random.

 0.0%0.1%0.2%0.3%0.4%0.5%0.6%false-positive rate64-bit blocks1927 blocks128-bit blocks992 blocks256-bit blocks504 blocks512-bit blocks254 blocksreduced by a moduloreduced by its top bitseach dot: one seedupper row of a pair: modulo; lower: top bits When the algorithm flips a coin

Two hashes that shared their low bits

Two pages on blocked Bloom filters with thresholds each recorded an instability they could not explain: a false-positive rate that collapsed on one seed at 256-bit blocks, and a pair of four-bit thresholds measuring 0.169% where its neighbours measured 0.08%. Both came from how a hash was brought into range. Every filter took its block and its ordering value as a modulo of a multiply-shift hash, and the low bits of such a hash depend only on the low bits of the key, so the two values were dependent whenever the block count had a factor of two to spare. At 992 blocks the threshold filter measures anything from 0.185% to 0.645%; read from the hash's top bits, 0.126% to 0.133%.

 22.5033.504block width, bitstable bits a block64128256512four bits eachcoded, a line each, offsetscoded, a line eachcoded, with an indexthe entropyabout two thousand blocks at each widthdashed: the closing distribution's entropy When the algorithm flips a coin

A code that has to fit its worst line

A blocked Bloom filter's four-bit thresholds are far from uniform: two blocks in five never close, and the rest crowd into the upper values, an entropy of 2.4 to 2.8 bits. A table coded from that distribution was predicted to match the four-bit rate on under three bits a block. Packed end to end it does, at 2.65 to 3.03 bits, and it costs every lookup a second read for the index. Packed a fixed number to a cache line it needs no index, but every line must hold its worst run of long code words, which costs 3.19 bits at 64-bit blocks and eighty-three code words decoded a lookup. Where the table is large enough for the saving to show, a plain three-bit table gets part of it with none of the costs.

 2.5033.504block width, bitstable bits a block64128256512four bits eacha bit and four, a line eacha bit and four, end to endcoded, a line eachthree bits eacha bit and three, a line eachmean of four seeds, about two thousand blockslabels at 64-bit blocks When the algorithm flips a coin

A bit for whether it closed

Almost half of a blocked filter's threshold table says one thing: this block never closed. Store that answer as a bit a block, and a closing value only for the blocks that did, found by counting the ones before it. At 64-bit blocks the prediction was 3.1 bits a block and two cache lines. Packed end to end it lands at 3.15 bits and 2.5 lines; packed a line at a time it reads two lines and counts one word, and costs 3.64 bits, because every line must hold the most closings any line happens to draw. At 512-bit blocks, where three blocks in five close, it saves under a tenth of a bit.

All threads