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

Sparse set — where it appears

A set of m positions in a universe of n where m is much smaller than n. Its information content is about m log(n/m) bits, so a dense bit vector holding it spends several times what it carries and a positional encoding does not.

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

01e+42e+43e+44e+450100one sampled position in every …bitsplain, one bit a rowcompressed blocksElias-Fano16,384 rowscrosses at one in 4

Twenty bits apart

Two representations of one sparse set, six thousand seven hundred and forty-five bits against six thousand seven hundred and sixty-five. One exploits sparsity and the other exploits runs, and on this set at this density they price identically.

machine · Space 05e+31e+41.5e+40246bits kept in the low partbits⌊log₂(n/m)⌋ = 2low partshigh vector2,049 marks in 16,385 positions1 bits between the two roundings

The flat bottom of a shallow curve

The low width is chosen as the floor of log of the universe over the count. Rounding it up instead costs one bit on five thousand, because the total is m·w plus n over two to the w and the minimum is where those two are equal.

bounds · Space plain bit vector19,475compressed blocks4,55723.4%Elias–Fano3,90520.1%positions, priced as Elias–Fano3,59118.4%16,385 rows · one in 32 markedElias-Fano at 20.1%

A position split in two

Write each sorted position as a high part and a low part. Store the low parts packed and the high parts as a bit vector in which the k-th one sits at position (p >> w) + k. A select on that vector and a low read recover any position.

structures · Space 01e+42e+43e+44e+450100one sampled position in every …bitsplain, one bit a rowcompressed blocksElias-Fano16,384 rowscrosses at one in 4

Where the sparse representation loses

At every row marked, Elias–Fano costs twice the plain vector. The crossing is at one row in four, which is a sampling rate a real index uses — so the choice between the two is a choice, not an improvement.

wrong · Space

Named alongside it

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

Elias fanoIndex sizeSample marksBit vectorCrossing pointRankCheckCompressed bit vectorOptimisationParameter choiceSelectSelf-index

All concepts