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

Space — where it appears

The bits a structure holds, as against the operations it performs. It is the axis this collection puts beside every count, because two structures answering the same question in the same number of steps routinely differ in size by a factor.

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

01234567801234567891724303539424410182531364043111926323741122027333813212834142229152316one unit = one subproblem given a valueeach number is a storage offset, of 45 slots

A triangle stored in a square

An interval table has a cell for every range of keys and nothing below its diagonal, and it can be stored as a square array, as packed rows, or as packed diagonals — the last matching the order it is filled in. On sixty-four keys, with every read replayed through a small cache, the square misses 39.7% of its reads, packed rows 38.8%, and packed diagonals 78.4%. Storing a table in the order it is written is storing it in the order it is not read.

tables · Table cache misses per split point consideredsquare array, by length1.1063,128,465 missestwo copies, by rows0.212598,455 missessquare array, split scans0.095268,386 missesfully associative · 32 lines × 8 elements · LRU256 keys, 32,896 cells

The split scan cut into blocks

Every way of filling an interval table one cell at a time stops at about one cache miss per split point considered once the table outgrows the cache — 1.01 at 128 keys, whether the cells go by length, by rows, or in a recursive tiling. Cut each cell's scan into blocks instead, and apply a block of split points to a block of cells whose inputs are all in hand, recursively at every scale, and the same 357,760 split points cost 0.094 misses each. The fill is told nothing about the cache, blocks of one and of four do equally well, and it needs no extra memory, where storing the table twice gets to 0.151 by doubling it.

tables · Table forward · wavelet tree18,377forward · rank directories5,037forward · C table100forward · sample marks8,193forward · sampled positions3,598reverse · wavelet tree18,377reverse · rank directories5,037reverse · C table100reverse · sample marks8,193droppedreverse · sampled positions3,598dropped8,192 characters · sampling every 3216.7% of both halves

An index that cannot locate

Take an FM-index, remove the sampled positions and the bit vector marking them, and refuse every request for a position. What is left still counts, still extends intervals, still runs a whole search — and is a third smaller.

space · Distance 0102030255075100125one sampled position in every …of both halves saved, per cent"about a sixth"the marks alone: 14.0%8,192 characters16.7% at one in 32

A sixth of what, exactly

The saving from a counting-only reverse half is 30.5% at one sampled position in four and 14.0% at one in a hundred and twenty-eight. A number quoted without its sampling rate is a number about a setting somebody chose.

wrong · Distance both halves, one in 3215.0 steps100.0% the sizeforward sampled one in 3215.0 steps83.3% the sizeforward sampled one in 167.0 steps88.4% the sizeforward sampled one in 83.0 steps98.5% the sizeforward sampled one in 41.7 steps118.8% the size8,192 characters · 6 occurrences5.0x faster, 98.5% the size

The saving, spent

A bidirectional index whose reverse half cannot locate is a sixth smaller. Give that sixth back to the half that does locate, and the same total size answers a locate five times faster.

practice · Distance tree · suffix array2,363,886tree · text656,635tree · document array1,050,616tree · previous-occurrence chain2,363,886tree · range minimum4,727,772succinct · suffix array2,363,886succinct · text656,635succinct · document array1,050,616succinct · previous-occurrence chain2,363,886succinct · range minimum1,483,854chainless · suffix array2,363,886chainless · text656,635chainless · document array1,050,616chainless · range minimum1,483,854chainless · reported bitmap256131,327 characters · 256 documents6 parts

What the chain cost

The chain of previous occurrences is one row number per row — exactly as wide as the suffix array it sits beside, and the largest single part of a document-listing apparatus. It is now absent, and what replaces it is one bit per document.

space · Index a segment tree over the chain2.70x8,142,274 bitsa succinct range minimum over the chain1.62x4,898,356 bitsno chain at all0.84x2,534,726 bitsthe dashed rule is the index itself: a suffix array and the text131,327 characters · 256 documents2.70x → 0.84x

The apparatus that is smaller than its index

Answering "which documents hold this" at a price proportional to the answer used to cost 2.70 times the index it sits beside. Two changes later it costs 0.84, and the largest thing left is an array that says which document each row belongs to.

practice · Index

Named alongside it

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

Index sizeBidirectional indexFM-indexLocatePracticeRankSamplingTradeCacheDocument arrayDocument collectionDocument listing

All concepts