The index that replaces the text
An index larger than what it indexes
What an index costs in bits, computed from the structure rather than from a serialisation — why a suffix array grows faster than its text, why it cannot be separated from it, and what the check that enforces the second one is.
A search that runs backwards
Backward search over a Burrows–Wheeler transform — the interval that narrows, the LF mapping it is built on, why the count arrives before any occurrence does, and why the cost does not depend on the length of the text.
The index that is smaller than the text
Why a compressed self-index is compressed — class-and-offset bit vectors, the block length that turns out to have an interior optimum, and the lower-order term that is three-fifths of the structure.
The sampling that goes the other way
Position-to-row sampling in a self-index — why extraction is asymmetric without it, what the second sampling costs, and why it is a second structure rather than an optimisation of the first.
The index that stores the runs
The run-length FM-index — what it stores, how a rank becomes three counted operations, and where it crosses the entropy-bounded structure it replaces.
The sampling that follows the runs
Why a compressed index's last term proportional to the text is its sampling, and what replacing it with two suffix-array values per run actually costs.
The occurrence carried through the search
How an r-index knows one occurrence by the time its search finishes, what maintaining that costs, and why the samples it needs are at the ends of runs.
An index with z in its size
What a self-index proportional to the phrase count stores, how it answers a query without a transform, and where it beats the two structures beside it.
The search that spends a budget
What approximate matching looks like when it never leaves the index, what it spends, and why it is not a filter.
The collection decides which index is small
Three self-indexes sized by three measures of repetition, with their query and extraction costs beside them, and how to choose between them from two numbers.
The candidates a filter cannot avoid
What the intersection at the centre of an LZ77 index actually costs when it is done by filtering a range, and what shape the cost has as a collection grows.
What a ceiling costs in phrases
The measured trade between a bound on the copy depth and the size of the parse, across a dial, a collection and four kinds of text.
A list of documents is not a list of occurrences
The document listing problem, why it is not the occurrence problem with a post-processing step, and what answering it naively costs.
An interval that grows at both ends
The index that can add a character at either end of the pattern, what keeps its two intervals in step, and what an extension actually costs.
A block, a class and an offset
The class-and-offset bit vector applied to a grid, what it saves, what a control says about how much of that is structure, and the select support it did not have.
Documents that are not the same length
The document strand's findings taken to real documents, which of them transfer exactly, and the headline that turns out to be a property of the generator's alphabet.
Two thousand documents of two hundred characters
A real collection of 2,214 short documents measured beside one of 82 long ones, with the document array, the separators and the join artefacts all recomputed on the shape document retrieval is actually about.
The half that is never asked where
What the reverse half of a bidirectional index is actually used for, why its rows cannot be read as positions anyway, and which parts of an FM-index answer which question.
Every child at once
The compound wavelet-tree operation that returns a rank and the count of smaller symbols from a single descent, measured against the loop it replaces across four alphabets.
The array the walk never reads
What the test in Muthukrishnan's document listing is actually asking, why the answer so far can answer it, and what the array it appears to be about is doing in the structure.
The index that does not notice
The FM-index, the run-length index and the phrase index measured against the copy count of one collection, and the crossing that decides which one a corpus wants.
The tree answers the question
Document listing by an interval-symbol descent over the compressed document array, and the third structure this apparatus removed by noticing something already present answered its question.
Asking about symbols that are not there
The operation that enumerates an interval's distinct symbols in one descent, against the loop that asks about each symbol in turn, with the dead branches counted.
What the locating apparatus becomes
The share of a self-index that exists to answer where, measured across the sampling dial with the marks held two ways.
Three savings on one structure
Three improvements to one index measured separately and then together, and what composes with what.
The same occurrences, less bookkeeping
A queue with a visited set against a text-order sweep, measured on the same queries, with the work held equal and the state not.