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

Workload — where it appears

The mix of operations and inputs a structure is actually asked to serve, as distinct from the worst case it was analysed for. Which design is cheapest usually depends on it: the share of range queries, the answers' distances, the keys that arrive.

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

1101001,000queries seenshare of the trie's prefixes ever visited10%20%30%50%70%100%misspelt vocabulary wordsmisspelt words it lacks7,709 prefixes, 2,424 wordsthe bounded walk, bound discovered

A trie fitted to its queries

A nearest-word search over a trie of 2,424 words gives a column to about 30% of the prefixes each query, and it was proposed that a stream of queries would pick out a part of the trie worth keeping and a part worth collapsing. A hundred queries have visited 93% of it; two thousand, 99.5%. A stream does not choose a part of the trie. It chooses a distance: misspelt vocabulary words all lie within two edits, and a search that starts at the median past answer does a fifth of the work of one that discovers its bound. Misspellings of words the vocabulary lacks break that, unless the search tries the learned bound once and then gives it up.

tables · Table 234681016110size ratioblock transfers · levelsa range of 100 keyslevelsan absent point lookup1,048,576 keys, 5 bits a keyfilters answer one of these two

The read a filter has no key for

A Bloom filter on every run of a log-structured store turns a lookup for a missing key from a read of every level into a fraction of one — 0.72 transfers across eight levels at five bits a key, and 0.00027 at twenty. A range query over the same store reads nine transfers at five bits and nine at twenty, because a filter answers whether one named key is in a run and a range has no key to name.

applied · Transfer 0%25%50%75%100%8101214161820222426283032bits of key prefix the filter is built onshare of the empty levels the filter skips83%72%64%46%ranges of 0.1 keysranges of 1 keyranges of 10 keysranges of 100 keys5 bits a key, 4 levels, 2,000 ranges eachdigits: the best length's share

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.

applied · Transfer

Named alongside it

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

Block sizeBloom filterDesign parameterLsm treeRange queryRead amplificationSorted runSpace time tradeBlock transferCompactionCorpusDynamic programming

All concepts