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

Succinct — where it appears

Held in a number of bits close to the information-theoretic minimum for the object, plus a term that grows more slowly. The second term is the subject rather than the footnote: at the sizes anybody runs it is regularly several times the first, so the phrase describes a limit rather than a size.

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

0000200121200the parenthesis sequencethe minimum excess of each block of 213 blocks · lookup table 72 bits, sharedblock 2 · 24 parentheses13 blocks

The table that fits inside a block

A block of six parentheses has sixty-four possible shapes and twenty-eight questions can be asked about each, so all 1,792 answers fit in a table of 9,408 bits — computed once, shared by every structure of that block length, and never counted in any of their sizes.

machine · Range 10010100occurrences of the patternreadsthe scanchain, treechain, succinct8 documents · answer 8crossing 267 → 75

Where a crossing moved to

The prediction was that a succinct range minimum would move the document listing's crossing "to a handful". It moves it from 32 occurrences per document to 11 — a factor of three, not an order of magnitude — because a constant-time query is ten lookups rather than one.

bounds · Range parentheses131,07216.7%select support115,71214.8%superblock minima16,3982.1%superblock table80,97010.3%block minima147,46518.8%block tables291,25537.2%the partsbitstotal 782,872 · the segment tree 2,228,224shared lookup table 82,944, not counted65,536 values · openings in index order, found by select2.85x smaller

Two bits a value, and what undoes them

The parentheses of a range minimum over 65,536 values are 131,072 bits. Everything that makes them answerable is 651,800 more — five times the payload — and one encoding choice nobody quotes accounts for a sixth of it on its own.

space · Range 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.

Range minimumDocument listingIndex sizeConstant factorMeasurementSegment treeSpace overheadTrade offCartesian treeDocument arrayDocument collectionLookup table

All concepts