The cost that is the size of the answer

A list of documents is not a list of occurrences ends on a one-line observation: a row is the first of its document inside a range exactly when the previous row holding that document lies outside the range.

That line is Muthukrishnan’s, and everything below is what it costs to build on and what it is worth.

The chain #

For each row $i$ of the suffix array, let $C[i]$ be the previous row holding the same document — the largest $j < i$ with $D[j] = D[i]$, or $-1$ if there is none.

Inside a range $[lo, hi)$, the rows with $C[i] < lo$ are exactly the first rows of their documents in that range. There are as many of them as there are documents in the answer, and finding them is a query about minima: the smallest $C$ in a range is below $lo$ if and only if at least one first row is there.

So: find the position of the minimum. If its value is below $lo$, report its document and recurse on the two halves either side. If not, the whole range has no first rows in it and there is nothing below to find.

Each report costs one range-minimum query and produces two more; a report-free query terminates a branch. So the number of queries is $2s + 1$ for an answer of $s$ documents, independent of the range’s size — which is exactly what an output-sensitive method means.

The measurement #

Eight documents of two thousand characters, the pattern planted at increasing density inside three of them:

The query count is ten or eleven at every point, which is $2 \times 8 + 1$ give or take a branch that terminates early. The claim holds exactly.

The visits column is what those queries cost inside the range-minimum structure, and it is the column the published bound puts inside a constant.

The crossing is at thirty occurrences per document #

The scan costs one visit per occurrence. The chain costs 256 to 288 visits, near enough flat — it drifts up by twelve per cent across a twenty-six-fold growth in the occurrence count, which is the logarithm of the range growing rather than the method following it.

They cross between 219 and 406 occurrences — call it 250, which is about thirty-one occurrences per document.

That is much lower than it sounds. A phrase occurring thirty times in a document is not unusual; a common word occurs hundreds of times. So the output-sensitive method wins on ordinary queries against ordinary corpora, and loses on rare ones.

It is also much higher than an asymptotic reading would suggest. “Proportional to the answer” against “proportional to the occurrences” sounds like a rout, and at eight documents in sixteen thousand characters it is a factor of two either way.

Why the chain works, in one paragraph #

The argument is short enough to give in full, and it is the reason the method needs nothing but a minimum.

Inside a range, consider the rows of one document $x$: they sit at positions $i_1 < i_2 < \cdots < i_t$. By the chain’s definition $C[i_1]$ is the last row of $x$ before the range — which is outside it — and $C[i_k] = i_{k-1}$ for every later one, which is inside. So exactly one row of each document has $C[i] < lo$, and it is the first.

The set of first rows is therefore the set of positions in $[lo, hi)$ where $C$ falls below $lo$, one per document in the answer and none otherwise. Finding all positions in a range where a value falls below a threshold is the classic use of a range minimum: take the minimum, and if it qualifies, report it and recurse either side of it. Each recursion either finds a qualifying position or terminates, so the tree of calls has as many internal nodes as there are answers.

Nothing in that argument depends on the documents’ order, the suffix array’s structure, or the pattern. It is the same kind of reduction the row that starts at zero performs on an alignment table — a question about strings turned into a question about an array of numbers, after which the strings are irrelevant. It is a statement about an array of integers and a range, which is why the same technique appears in colored range reporting and in several other places under other names.

Where the visits go #

About thirty-five visits per document reported, and the structure is a segment tree over $n$ values.

A range-minimum query on a segment tree decomposes the range into $O(\log n)$ nodes and takes the minimum over them. Finding where the minimum is — which this method needs, since it reports the document at that row — means descending from the winning node to its leaf, another $\log n$ steps. So one query is about $2\log_2 n$ visits, and at $n = 8{,}000$ that is twenty-six.

Ten queries at twenty-six visits is 260, which is the measured number.

So the constant is a logarithm of the collection’s length, and it is exactly the logarithm the published bound removes: the succinct range-minimum structures answer in constant time, at $2n + o(n)$ bits, using a decomposition into blocks and a precomputed table over the block types.

This collection has not built one. What is reported is what this segment tree costs, which is the same accounting every other structure here gets — and it means the crossing measured above is a property of a segment tree rather than of the method. With a constant-time range minimum the crossing would be at a handful of occurrences per document rather than thirty.

The space, which is where the trade actually is #

The structures above the index, on eight documents totalling 4,103 characters:

• suffix array: 53,339 bits
• text: 20,515
• document array: 12,309
• previous-occurrence chain: 53,339
• range minimum: 106,678

The listing apparatus is 172,326 bits against the index’s 73,854 — 2.3 times — and 62% of the apparatus is the range minimum alone, which is 43% of everything.

That is the honest counterweight to the output-sensitivity plate. A method that is proportional to its answer, on a structure nearly two and a half times the index it sits on, is a trade rather than an improvement, and the size ratio is worse than the query ratio at the sizes measured.

What the succinct version would change, and what it would not #

Both, precisely, because this is the gap between what is built and what is published.

A succinct range minimum is $2n + o(n)$ bits — about 8,200 bits here against the segment tree’s 106,678, a factor of thirteen — and answers in constant time rather than $\log n$ visits.

It would move the space ratio from 2.3 times the index to about 1.1. The listing apparatus would then be the document array and the chain, which are $n\log d$ and $n\log n$, and the second of those is as large as the suffix array.

It would move the crossing from about thirty occurrences per document to a handful, since the per-query constant falls by more than an order of magnitude.

It would not change the shape. The query count is still $2s+1$, the scan is still one per occurrence, and the crossing still exists — at a lower density.

So the measured numbers here are the right ones for the structure built and the wrong ones for the structure published, and the direction of the difference is stated rather than assumed. That is the same convention the grid ladder beside this one uses for its own $o(z\log z)$: report what these bit vectors cost, name the bound that is not claimed.

An asymptotic claim measured at a size where it loses #

This is the useful discomfort of the ladder and it deserves naming rather than smoothing over.

The method is $O(s)$ queries against the scan’s $O(t)$ reads, with $t$ unbounded relative to $s$. That is a strictly better bound and it is the reason the technique exists. And on the collection this ladder can draw, at the densities a plate can show, the scan wins for most of the sweep.

Both are true, and the reason they are compatible is the constant: the better method’s per-query cost is $2\log_2 n$ and the worse method’s is one. So the bound is right and the crossing is at $t \approx 2s\log_2 n$, which at $s = 8$ and $n = 8{,}000$ is about two hundred and fifty.

That formula is the useful output, more than any of the measured numbers. It says the crossing moves up with the collection’s length, because the logarithm does, and up with the answer’s size — so a query returning many documents from a large corpus is the case where the scan holds on longest, and a query returning few documents from a repetitive corpus is where the chain wins earliest.

This collection has the same discomfort on record for a different structure. A limit is not a prediction is the essay about it, and where insertion sort actually wins is the case where the asymptotically worse algorithm is the right one up to a measured size. Neither says the bound is wrong; both say the bound is not the answer to the question of which one to run.

The chain has one more property worth having #

The recursion terminates on a range with no first rows, and that means it can be stopped early.

Asking for the first ten documents holding a pattern — which is what a search interface wants — costs ten reports and stops, without ever discovering how many there are. The scan cannot do that: it has to read every occurrence to know whether the eleventh document is there.

That is a genuine asymmetry and it is invisible in the crossing above, which measures the full answer. For a paginated interface the output-sensitive method wins at every density, because the answer’s size is bounded by the page rather than by the corpus.

The same shape appears in the cheap tail and the expensive merge: a structure whose cost follows what is asked for rather than what is held is worth more to a system that asks for little, and the benchmark that asks for everything cannot see it.

The chain is cheap to build and expensive to hold #

One asymmetry worth separating, because it decides whether the structure is worth having on a collection that changes.

Building $C$ is one pass: walk the rows in order, keep an array of the last row seen for each document, and write down what was there before overwriting it. That is $n$ steps and $d$ words of working space — the cheapest structure on this ladder to construct, and cheaper than the suffix array it is derived from by a wide margin.

Holding it is $n\lceil\log_2 n\rceil$ bits, which is exactly the suffix array’s size. So the chain doubles the index’s largest component for a structure that took a linear pass to make.

And updating it is impossible in any local sense. Adding a document changes the suffix array, which changes the rows, which changes $D$, which changes $C$ everywhere — so the whole apparatus is static, and a collection that grows rebuilds it.

That is the ordinary situation for this field’s structures and is worth stating because the corpora document listing is for — repositories, logs, version histories — are exactly the ones that grow. A structure that must be rebuilt to add a document is a structure with a batching policy attached, and the batching policy is a parameter nobody has measured.

Two ways to get it wrong #

Both in this site’s gate and both returning correct documents.

The comparison loosened by one. $C[i] < lo$ says the previous occurrence lies outside the range; $C[i] \le lo$ admits a row whose previous occurrence is the range’s own first row. It reports eight documents where there are seven — one of them twice — so the answer stops being a set and the work stops being the answer’s size, which are the two claims the method is built on.

A document array in text order. $D[i]$ is the document of the suffix in row $i$. Indexed by text position instead, it is a perfectly good array holding the same values, and querying the row range against it returns one document where there are seven.

Neither can be caught by checking that the reported documents contain the pattern. Both are caught by scanning the documents directly, which is what the gate does at three pattern lengths and three densities.

What the ladder costs altogether #

Four essays, three structures and one question, and it is worth adding up what a collection has to carry to answer the question a text cannot.

A separator, which is one alphabet symbol and free on most texts and a fifty per cent premium on a four-symbol one. A boundary vector or a document array, which is $n\lceil\log_2 d\rceil$ bits. A chain, which is as wide as the suffix array. And a range minimum, which as built here is twice that and as published is a fiftieth of it.

Against that, one query answered in $2s+1$ range-minimum queries rather than $t$ array reads, where $t$ is unbounded relative to $s$.

The reading this collection would offer: the collection’s question is expensive because it is a different question, not because the structures for it are inefficient. A text index answers “where” and the projection of “where” onto documents is a smaller set that the index has no way to reach. Every structure on this ladder exists to make that projection reachable, and their combined size is the price of the projection.

That is the same accounting the structure paid for before the first query does for the grids on the ladder beside this one: a structure that answers no query of its own, priced beside the index it accelerates, with the marginal cost separated from the total.

The three structures, and which of them a reader needs #

The ladder has produced four structures and a reader building one system needs a subset.

A separator — always, unless the documents genuinely are one text. One alphabet symbol, and one separator, or one for each is where the choice of which is priced.

A boundary vector or a document array — always, since every method needs to know which document a row belongs to. The array is $n\lceil\log_2 d\rceil$ and answers in one read; the sparse vector is $d\log(n/d)$ and answers in one rank on the position rather than the row.

The chain — only for the output-sensitive method, and it is as wide as the suffix array.

The range minimum — only with the chain, and it is the largest single structure on the list.

So the naive method needs the first two, at about 17% of the index, and the output-sensitive method needs all four, at 233%. The crossing in space is not a crossing at all: the second method is always dearer, and the question is whether the query saving is worth it at the density the corpus actually has.

That framing — a structure that is unambiguously larger and conditionally faster — is the ordinary shape of an index decision and is the one an index has a size exists to keep visible. A query cost with no size beside it is the half of the argument that always favours building more.

What is being claimed #

The query count is $2s+1$ for the reason a list of documents is not a list of occurrences sets up, for an answer of $s$ documents — ten or eleven at every point of a sweep where the occurrences run from 30 to 790.

Its cost is $2\log_2 n$ visits per query on a segment tree, so the method is output-sensitive times a logarithm, and the logarithm is 26 at eight thousand characters.

The crossing against a scan is about thirty-one occurrences per document, which is low enough that ordinary queries are past it and high enough that the asymptotic reading is misleading.

The listing apparatus is 2.3 times the index, of which 62% is the range minimum — the structure a succinct implementation would shrink thirteenfold.

And it can stop early, which the scan cannot, so a paginated query is proportional to the page rather than to the corpus — the same asymmetry the guarantee that is one query wide draws between a promise about one answer and a promise about all of them.