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

Suffix array sampling — where it appears

The policy deciding which of an index's suffix-array values are kept, which sets both the structure's size and how far a locate must walk. Sampling one position in s gives n/s values and a walk of s/2 steps, so it is a time-space dial rather than a setting.

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

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 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 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

Named alongside it

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

Index sizeLocatingSpace accountingElias fanoSample marksBidirectional indexSelf-indexBit vectorTrade

All concepts