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

Space accounting — where it appears

The practice of reporting a structure's size in named parts rather than as a total. It is what lets a later question ask where the bits are, and it is how a term proportional to n gets found inside an o(n) that nobody had opened.

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

0.020.050.10.20.5121235810filter bits a keywasted reads per absent lookupno filters: all 3 levelssame rate every levelrates sized to levelsn = 65,536, size ratio 4, first run 1,024 keysthe same memory at every point

The filter each run carries

A log-structured store turns every lookup for a missing key into a read of every level, and a Bloom filter on each run buys those reads back with memory. Spread five bits a key evenly across three levels and a missing key still wastes 0.279 reads. Give the small levels more bits and the large one fewer — the same memory — and it wastes 0.201. At four levels the gap is 0.382 against 0.209, because sized filters stop the waste growing with the number of levels.

applied · Transfer 0%25%50%75%100%ln 2mean leaf fillrandom, even splits2,906 leavesrandom, rightmost-split rule2,949 leavesascending, even splits3,971 leavesascending, rightmost-split rule2,048 leavesdescending, even splits4,095 leavesdescending, rightmost-split rule4,095 leavesbulk-loaded from sorted keys2,048 leaves131,072 keys, leaves of 64each bar names its rule

The keys that arrive late

Insert 131,072 keys into a B+-tree in random order and its leaves end up 70.5% full; in ascending order, 51.6%; in descending order, 50.0%. The rule databases use to fix ascending inserts — split a full leaf at its right-hand end — fills them completely, and it does nothing for descending keys. Let one key in a hundred arrive late in an otherwise ascending stream and the rule's leaves fall from 100% to 53.4% full. How much of an index is empty is decided by the order its keys arrived in, and a trickle of disorder undoes the fix.

applied · Transfer 6080100how far a full leaf looks for room, in siblingsmean leaf fill, per cent12481664randomascendingdescendingascending, 1% late131,072 keys · leaves of 64 · fan-out 64a reach of 1 is the adjacent-sibling rule

A key passed along the row

A full B+-tree leaf that offers a key to its immediate neighbours before splitting leaves an ascending stream 67.2% full. Let it look one sibling further and the same stream fills its leaves completely, 2,048 leaves where there were 3,048, for about the same key moves. On random keys each doubling of the reach adds a few points of fill and more writes than it saves, and at the whole parent a key travels sixteen leaves on average. On a stream that is mostly in order the same reach costs almost nothing.

applied · Transfer 4,097 rows · one in 32 marked3.1% of the rows

The array that says where is twice the samples

An index keeps one suffix-array value in every thirty-two, and a bit vector over all n rows saying which. The vector is sixteen thousand bits and the values it points at are seven thousand — the index of the samples is twice the samples.

space · Space range minimum and chain838,797255.0%range minimum, no chain285,46086.8%one descent over D119,97236.5%the document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree64 documents · 16,447 characters14.3% of the published apparatus

The apparatus, three times smaller again

Eight hundred and thirty-nine thousand bits became two hundred and eighty-five thousand, and now a hundred and twenty thousand. The listing apparatus is fourteen per cent of what it was and holds one array, which is the only part of it that was ever information.

space · Index 02040255075100125one sampled position in every …of the index, per centplain marks: 18.5%Elias-Fano: 3.8%16,384 characters14.9% off at one in 32

What the locating apparatus becomes

The two parts that answer "where" are half an index at a dense sampling and a fifth at a sparse one, and the fifth does not fall further. Represent the marks properly and it keeps falling, to under four per cent.

indexes · Space both halves locate250,584100.0%the reverse half counts only226,50490.4%and its marks are Elias-Fano210,93484.2%the saving spent on sampling241,47596.4%16,384 characters · one in 3284.2% smaller, or the same size and faster

The ladder, and the rung that spends

Two hundred and fifty thousand bits, then two hundred and twenty-six, then two hundred and eleven. The fourth rung takes the whole saving and buys a four-times denser sampling with it, landing at ninety-six per cent of where it started and locating several times faster.

space · Distance 0102030100200one sampled position in every …of both halves saved, per centplain marks: 13.5%Elias-Fano: 1.8%16,384 characters17.6x against 2.3x

The floor was the marks

A saving reported as about a sixth of a bidirectional index, falling to an eighth and levelling off. Represent one array properly and it falls to a fiftieth instead — most of what was being dropped was a badly encoded bit vector.

practice · Space 020406080255075100125one sampled position in every …of the plain index, per centsize: 84.7%67.5 steps16,384 characters · 8-character patternssize falls, the walk lengthens

Bits and steps on one frame

The size falls from ninety-nine per cent to eighty-six as the sampling thins, and the walk to a sampled position rises from two and a half steps to sixty-four. Neither line is the answer; the answer is a point on the pair.

structures · Distance phrase lengths2,71222.6%phrase sources2,71222.6%phrase literals1,1309.4%boundary orders5,42445.3%three permutations of 226 elements: 1,808 bits each, and one is the inverse of another226 phrases · 4,096 characters45.3% in the orders

Half an index is three permutations

A phrase index stores a length, a source and a literal per phrase — and three orderings of its boundaries, at forty-five per cent of the structure. One of the three is the inverse of another, and nothing needs both at once.

space · Parse 0100200300400102030copies of the basebits held during one querythe visited set: 420the frontier: 2666-character patterns20x to 1.58x

A constant factor, not a term

The substitution was expected to remove a quantity proportional to the answer. Both traversals hold a quantity proportional to the answer, and what it removes is a factor of 1.6 that shrinks as the collection grows.

wrong · Parse

Named alongside it

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

Index sizeLocatingElias fanoSample marksSuffix array samplingBidirectional indexBlock transferTrade offB-treePhrase indexPresortednessSelf-index

All concepts