A list of documents is not a list of occurrences

A text supports two questions: how many times does this occur, and where. A collection of documents supports a third — which documents contain it — and it is not the second question with a mapping step on the end.

The sizes of the two answers #

They are unrelated, and the gap can be as large as the collection.

A pattern occurring once in each of eight documents has eight occurrences and eight documents: the two questions cost the same and there is nothing to discuss.

A pattern occurring a hundred times in each of eight documents has eight hundred occurrences and eight documents. Measured on a collection built to have that shape — eight documents of two thousand characters, the pattern planted repeatedly inside three of them and occurring naturally in the rest:

The answer is eight throughout. The occurrence count grows by a factor of twenty-six and the answer does not move.

That is the whole reason document listing is a subject. If the answer were always about the size of the occurrence set, an index that locates would be an index that lists.

The unbounded direction is the one that matters. A pattern can occur in one document a million times and the answer is one; there is no bound on the occurrence count in terms of the document count, and the ratio is a property of the corpus and the query rather than of the structure.

What the naive method costs #

Locate every occurrence, map each position to its document, put them in a set.

The mapping is cheap — one rank on the boundary bit vector, or one read of a precomputed array indexed by suffix row — so the cost is one operation per occurrence: 30, 75, 219, 790 across the sweep. Linear in a quantity that has nothing to do with the answer.

And it is not merely inelegant. On a compressed self-index the mapping is worse than one operation: a suffix row does not carry its text position, so locating one occurrence is a walk to the nearest sampled position — the cost the sampling that goes the other way measures and every occurrence at the same price removes for a different structure, which is half the sampling rate on average. At a rate of thirty-two that is sixteen LF steps per occurrence, so eight hundred occurrences is thirteen thousand steps to produce an answer of size eight.

The document array, which makes the mapping free #

Store, for each row of the suffix array, the document that row’s suffix belongs to. That is $n\lceil\log_2 d\rceil$ bits — 12,309 bits for eight documents in four thousand characters — and it turns the mapping into an array read.

It does not change the shape of the cost. The naive method is still one read per occurrence, and the occurrence count is still unrelated to the answer. What it buys is a constant: an array read rather than a locate.

That is worth being precise about because the document array is often described as the structure for document retrieval, and on its own it is not a solution to anything. It is the structure that makes a bad algorithm cheap per step.

The property that makes a better method possible #

Look at the rows again. Inside the range of rows for a pattern, the rows belonging to one document are scattered — the suffix array’s order has nothing to do with which document a suffix came from.

But each document has a first row in that range. Eight documents, eight first rows, however many hundred rows there are.

So the answer is a set of eight positions inside the range, and if there were a way to find them without visiting the rest, the cost would be the answer’s size. Finding them is the next essay, and the observation that makes it possible is one line: a row is the first of its document exactly when the previous row holding that document falls outside the range.

That is a condition on a number that can be precomputed per row and never changes. Which is what turns a search over a range into a small number of queries against a structure.

Two failures the naive method makes easy #

Both are in this site’s gate as checks that must reject, and both produce answers that are correct.

Reporting one document per row. The rows for the pattern give 54 document identities and 7 distinct ones on the collection measured. A listing that returns the list rather than the set returns every document that holds the pattern, each of them a genuine answer, seven or eight times over — and its cost is the occurrence count by construction, because the output is the occurrence count.

That failure is worth noticing because the two properties it breaks are the two the whole ladder is about: the answer stops being a set, and the work stops being the answer’s size. A check asserting “every document reported contains the pattern” passes it.

A document array indexed by text position rather than by row. $D[i]$ is the document of the suffix in row $i$, and the rows are the sorted order. An array of the same length holding the same values indexed by position is a perfectly good array; querying it over the row range returns documents that exist, and on the collection measured it returns one where there are seven.

Neither has a signature. Both return real document identities, in range, sorted, with no duplicates in the second case. The only check that separates them from the truth is exhaustion — scan each document for the pattern — which is what this site’s gate does at every pattern length it measures.

Why this is not a text question with a filter on it #

Worth stating carefully, because “it is just deduplication” is the natural reading and it is wrong in a specific way.

Deduplicating a list of size $t$ into a set of size $s$ costs $t$ operations at best, since each element has to be looked at to know whether it is a duplicate. So any method built on producing the occurrence list first is $\Omega(t)$, and $t$ is unbounded relative to $s$.

To do better, the method must never produce most of the occurrences, which means it must decide which rows to visit before visiting them. That is only possible if something has been precomputed about the rows’ relationships, and that something is the structure this ladder is heading for.

The general shape appears elsewhere in this collection. The cost is the number of subproblems is the version in dynamic programming: the cost of a table is the number of cells, and a method visiting only the cells that matter is a different algorithm with a different bound rather than an optimisation of the first.

What the collection’s question costs before it is asked #

Three structures sit above the index to answer this question, and they are the subject of the next essay’s arithmetic. In advance:

• the suffix array and the text: 73,854 bits on eight documents of 512 characters
• the document array: 12,309
• the previous-occurrence chain: 53,339
• the range minimum over it: 106,678

So the collection’s own question costs 2.3 times what the text’s questions cost, before any query is answered — and 62% of that is the range minimum, which the naive method does not need at all. That is the price of turning a text into a collection, and it is a price nothing about the search cost can pay back on a small collection.

Three questions, three costs, one index #

It is worth putting the collection’s three questions on one page, because the pattern of what each costs is the field’s shape in miniature.

How many times does this occur? One backward search — $m$ rank operations — and the answer is the size of the row interval. Independent of the text’s length and of the number of occurrences, which is the property the index that is the text is about and is the most surprising thing a self-index does.

Where does it occur? One locate per occurrence, each a walk to a sampled position. Proportional to the answer, times the sampling rate — and the sampling rate is the dial the sampling that goes the other way sweeps.

Which documents hold it? Naively, one operation per occurrence, which is proportional to something the answer has no relation to.

So the three questions cost: nothing per answer, a constant per answer, and a constant per non-answer. The third is the odd one out, and the reason it is odd is that it is the only one whose answer is a projection of the occurrence set rather than the set itself.

That is the general form worth carrying past this ladder: a query whose answer is a projection of a larger set is the one an index built for the larger set answers badly, and the fix is never a post-processing step.

What a real system does instead #

Worth saying, because the naive method is not obviously wrong in practice.

An occurrence count of 790 in a collection of four thousand characters is a very high density. Real queries against real corpora usually have few occurrences per document — a phrase in a document collection, a gene in a genome collection — and the naive method’s cost is then within a small factor of the answer’s.

The regimes where listing matters are the ones where a pattern is common: a short pattern, a repetitive corpus, a query that is a single word against a million documents. Those are exactly the cases where the occurrence list is enormous and the document list is not, and they are also exactly the cases a search engine faces.

So the honest framing is: the naive method is fine until the density is high, the crossing is measurable, and the next essay measures it. It is at about thirty occurrences per document, which is lower than it sounds.

The document array’s other use #

One thing the document array does answer well, which is worth separating from what it does not.

Counting the documents rather than listing them — how many distinct documents hold the pattern — is the same problem and has the same cost by the naive method. But a weighted version, “how many occurrences in each document”, is genuinely one pass over the rows and is the natural thing to want for ranking. There the occurrence count is the answer’s size, so a method proportional to it is output-sensitive by definition.

So the document array is the right structure when the question is about occurrence counts per document, and the wrong one when the question is which documents at all. The two questions look nearly identical and their answers differ in size by whatever the density is.

That is a distinction a system designer has to make before choosing a structure, and it is not the kind of thing an index’s documentation makes prominent. The cost model is an input is the thread; here the input is which of two nearly identical queries the application actually issues.

How the collection is built so that the two costs separate #

The sweep above needs a pattern whose occurrence count moves while its document count does not, and producing one takes care — which is itself part of the finding.

A pattern drawn at random from a collection of near-identical documents occurs about once per document, so the two costs are equal and there is nothing to measure. The collection here plants the pattern repeatedly inside three of the eight documents, at an increasing rate, so the occurrence count sweeps from 30 to 790 while the set of documents holding it does not change.

The answer is eight rather than three, because the documents are near-copies at five per cent divergence and the pattern survives in most of them naturally. That is left as it is rather than tuned: an answer of eight from eight documents is the honest shape of a query against a version history, where a phrase present in one version is usually present in most.

The sweep asserts that the document count is constant across every row before reporting anything, which is what makes the plate a comparison rather than two unrelated curves. A sweep where both quantities moved would show two rising lines and say nothing about which one each method follows.

That is the same discipline sized for a rate that does not hold still is about, applied to a benchmark instead of to a structure: if the quantity being held fixed is not fixed, the axis being swept is not the only thing moving.

Why the third question is the one a corpus actually asks #

Worth arguing rather than asserting, since this collection has spent five essays on the first two questions and is now claiming the third matters more.

A reader searching a repository wants the files, not the byte offsets. A biologist searching a collection of genomes wants the organisms. A search engine’s index is entirely about which documents, with the positions kept only for ranking and snippets. In each case the occurrence list is an intermediate the application throws away.

And the intermediate can be enormous. The phrases a text copies from itself measures collections where one pattern occurs once per copy and the copies number in the thousands; a repetitive corpus is precisely the case where an occurrence list is orders of magnitude larger than the document list.

So the two facts point the same way: the question people ask is the third one, and the corpora this field’s compressed indexes are built for are the corpora where answering it via the first two is worst. That is the argument for the ladder, and it is the reason the naive method’s honest performance — fine until the density is high — is less reassuring than it sounds.

Both closing numbers are for the apparatus as first built #

Two figures carry the discouragement on this page — the apparatus at 2.3 times the index, and the crossing at about thirty occurrences per document — and both are measurements of the structure at its first stage. The strand’s own later work moves each by about a factor of three, in the direction that favours building it.

The crossing first. It is where one array read per occurrence passes one range-minimum query per document in the answer, so it is simply the cost of a query measured in array reads. A segment tree over $n$ values answers in $\lceil\log_2 n\rceil$ scattered node visits, which is where thirty comes from; a succinct range minimum answers in a constant number of steps — two selects, a block lookup and a rank, nine or ten accesses — and the crossing falls to about eleven.

So the naive method stops being the right one three times sooner than this page says, and the sentence about high density being rare needs the same correction: eleven occurrences per document is a common shape for a word against a document collection, where thirty is not.

The size runs the same way. Of the 172,326 bits the apparatus costs here, the chain is 53,339 and the range minimum 106,678 — and both of those are what the later ladder attacks. Replacing the segment tree with the succinct structure takes the range minimum to about a third; removing the chain, once the walk is shown never to read it, takes 53,339 to nothing.

What is left is the document array, a much smaller range structure, and a bitmap: on the proportions the later strand measures, the apparatus falls from 2.3 times the index to about 0.6 times it. The parts are measured on a different collection there, so the ratio transfers and the bit counts do not — but the direction and the rough size do, and the direction is the whole of the argument.

Which changes what this page’s closing sentence should be. A price nothing about the search cost can pay back on a small collection is true of the apparatus as first built and false of the one the strand ends with: an apparatus smaller than the index it sits beside, crossing the naive method at eleven occurrences per document rather than thirty.

The observation the next essay is built on — a row is the first of its document exactly when the previous row holding that document lies outside the range — is what makes both improvements available, since it is the line that eventually shows the chain is never read. The cost that is the size of the answer is the construction, and the numbers on this page are its first and dearest version rather than its final one.

What is being claimed #

The answer’s size and the occurrence count are unrelated. Eight documents throughout a sweep where the occurrences go from 30 to 790.

The naive method costs one operation per occurrence, and on a compressed index the operation is a locate rather than an array read — sixteen LF steps at a sampling rate of thirty-two.

A document array makes the operation cheap and does not change the shape. It is a constant-factor structure, not an answer to the listing problem.

Any method that produces the occurrence list first is $\Omega(t)$, which is a floor of the same kind as a floor one pass cannot get under — an argument about what has to be looked at rather than about how cleverly it is looked at, and, so a better method must decide which rows to visit before visiting them.

And the property that lets it is one line: a row is the first of its document in a range exactly when the previous row holding that document lies outside it.