The crossing that never arrives

The argument for output-sensitive document listing is one sentence, and it is a good one.

A pattern occurring four thousand times in eight documents has an answer of size eight, so an algorithm proportional to the occurrences is doing five hundred times the work an algorithm proportional to the answer would.

Everything follows from it: the document array, the chain of previous occurrences, the range minimum over the chain, and the walk that visits the answer instead of the rows. The cost that is the size of the answer is the whole construction, and it works exactly as advertised.

On a real collection of two thousand short documents, the sentence is false at every point that can be measured on it. The most frequent six-character string occurs 543 times in 522 documents. The next occurs 529 times in 510. Occurrences per document is 1.04, and everything below it is 1.00.

What the ratio has to be #

The crossing is easy to state once the two costs are written down.

A scan reads every row of the pattern’s interval and collects the documents: cost is the occurrence count, and each unit is one array read.

The walk asks a range structure for the position of the smallest chain entry, reports a document, and recurses on both sides: cost is one query per document in the answer, plus one per pruned branch, and each query is not one read. On a segment tree it is a descent of ⌈log₂ n⌉ visits; on a succinct structure it is nine or ten memory accesses. The shape a range question is about is where that constant was priced.

So the walk wins when

occurrences × 1 > documents in the answer × cost of a query

which is to say when occurrences per document exceed the cost of one query, measured in array reads. That number was 32.2 when the range structure was a segment tree, and 10.8 once it was succinct — the crossing moved by a factor of three because a query got three times cheaper, which is the cleanest cross-strand result this collection has produced.

On the short-document collection the ratio is 1.04. It is not near either crossing; it is an order of magnitude below the friendlier of the two.

The same prose, cut the other way #

The measurement is worth trusting because the control is available: the same essays, in the same collection, cut into 82 documents instead of 2,214.

Here the ratio is 4.38 for the most frequent pattern and between 1.65 and 3.85 for the rest. The walk reads 123 queries against 359 rows for the top pattern, so it does about a third of the work — and one third is not a win, because a query costs nine or ten reads. At 4.38 occurrences a document the scan is still ahead.

Two shapes of the same prose, then, and neither of them reaches the crossing. One of them is not close.

Why a short document cannot get there #

The reason is arithmetic rather than a property of this corpus, which is what makes it worth a page.

A document of 230 characters holds 225 distinct six-character windows. A six-character string that occurs in it twice would have to be one of a small number of repeated windows in a passage of two sentences — and prose does not repeat itself at that scale. It repeats words, and a six-character window that captures a common word occurs once per use of that word, which in two sentences is once.

So occurrences per document is bounded above by roughly the document length divided by the length of the repeating unit, and for short documents that bound is close to one whatever the text is. The only way to get a large ratio is a document long enough to say the same thing many times.

That plate is honest and its axis is a planted parameter. The pattern is inserted into each holding document as many times as the sweep asks for, because a pattern drawn from a real collection of near-copies occurs once per document and there is nothing to measure. The planting is the right experimental design for the question does the method behave as claimed — and it means the axis is not a distribution any collection supplies.

What a query costs, and why it is not one #

The crossing is a comparison between two units, and the whole difficulty is that one of them is a read and the other is not.

A scan’s unit is an array access: read the document number at row i, put it in a set. On a machine that is one cache line most of the time, because the rows of an interval are contiguous and the document array is read in order. It is about as cheap as a unit of work gets.

A walk’s unit is a range-minimum query, and what that costs depends entirely on which structure answers it. A segment tree over n values answers in ⌈log₂ n⌉ node visits, each a read of a node that is nowhere near the last one — 17 scattered reads at 131,072 values. The shape a range question is about replaced that with a structure holding the shape of the array and not its numbers, which answers in a constant number of steps: two selects, a block lookup and a rank, nine or ten accesses in all.

That is the difference between a crossing at 32 occurrences a document and one at 10.8, and it is worth stating as a general point about output-sensitive methods. The claim “proportional to the answer” is a claim about growth, and at the sizes anybody actually runs it is the constant that decides. A method whose cost is 10 × |answer| beats one whose cost is 1 × |occurrences| exactly when the occurrences are ten times the answer — which is a statement about the data, not about either algorithm.

The plate below is the same comparison drawn as work rather than as a threshold, and the flat line is the one the argument is about.

Where the crossing does live #

The shape where occurrences per document is large is not exotic; it is just not this one.

A version history. Ten revisions of a file, each nearly identical: a string in the original occurs once per revision, so a phrase common in the file occurs many times in each document as well. This is the case the whole compressed-index family is built for, and it is the one a corpus that was not generated froze so that the numbers about it would be about a fixed object.

A collection of long documents. A book is half a million characters; a common word occurs thousands of times in it. The ratio is enormous, the answer is one document, and output-sensitive listing is worth every bit it costs.

Logs, records, and anything machine-generated. A boilerplate line occurs in every record of a large file, and the file is one document.

A collection whose documents overlap. Where the same passage appears in several documents — quoted, forwarded, copied — the occurrence count rises without the answer rising, which is the ratio the method wants. That is a property of a corpus’s provenance rather than of its subject, and documents that are not the same length is the nearest this collection comes to measuring it.

And a query that is a word rather than a window. Every measurement here is over six-character windows because that is what a text supplies. A real query is a word, and a word that occurs in a document usually occurs in it more than once — though on a two-sentence document, not much more.

That plate is the one this page is arguing with, and the argument is not that it is wrong. On twelve long documents the ratio genuinely reaches 32; the walk genuinely wins; the structures are genuinely worth their bits. Both measurements are of real collections. They disagree because the collections are different shapes, and neither of them is the shape.

What it costs to be wrong about this #

The apparatus is not free, and on the shape where it buys nothing it costs the most.

On 2,214 documents the apparatus is 2.64 times the index it sits beside — a document array at 12 bits a row, a chain as wide as the suffix array, and a range structure over the chain. That is the price of an ability the collection cannot exercise.

Removing the chain, which the array the walk never reads shows is never consulted, and which what the chain cost prices in full, takes it to 0.93. Removing the whole apparatus — keeping only the document array, and answering “which documents” by scanning the occurrences — takes it to 0.48, and costs nothing measurable on this collection because the scan was winning anyway.

So the recommendation for this shape is the blunt one: keep the document array, drop the listing structures, scan. It is smaller and it is faster, and the only thing it gives up is a guarantee about a regime the collection never enters.

The measurement this collection should have made first #

There is a version of this page that could have been written before any of the structures were built, and it would have taken an hour.

Take the collection. Count, for each of its own frequent strings, how many occurrences and how many documents. That is a suffix array and a loop over an interval — no chain, no range structure, no listing algorithm at all. The answer is the ratio the whole apparatus’s usefulness depends on, and it is available before a single bit of the apparatus exists.

This collection has a name for that habit: compute the break-even first. It is the rule that came out of a slate where three of five strands would have been settled by a one-pass measurement — a mean run against a code’s crossing, a depth histogram against a cap sweep, a run-length comparison against a substitution model — and where the expensive route was taken in each case and produced something extra. Here the cheap route would not have produced something extra. It would have said, in one plate, that the collection the structures were about does not reach the regime they win in.

What makes that worth stating rather than regretting is that the structures were still worth building. A list of documents is not a list of occurrences is a real distinction and the walk is a real algorithm; the succinct range minimum built for it turned out to decide the crossing for the other shape of collection, where it moved the answer from two of twelve queries to seven of twelve. The measurement that should have come first would not have stopped any of that. It would have changed which sentence went at the top.

How to tell, in one measurement #

The useful form of all this is a check somebody can run before building anything.

Take the collection. Take a hundred of its own most frequent strings at the length queries actually are. For each, count occurrences and count distinct documents. Take the ratio.

If the median ratio is above about ten, build the apparatus: the walk will win, and the succinct range structure makes the crossing low enough that it wins on most queries rather than the extreme ones. If it is between two and ten, the answer depends on the query distribution and on what a query costs on the machine in question, and the honest thing is to measure both methods rather than reason about them. If it is near one — and it is near one for every collection of short documents — the apparatus is bits spent on nothing.

The measurement takes a suffix array and a loop. It is cheaper than the structures it decides about by three orders of magnitude, and nothing in the published account of the method suggests making it, because the published account is about the regime where the answer is already known.

The document count is not only what keeps the crossing out of reach. It is also what a join has to be protected against, and the same ratio drives both.

So the shape that makes output-sensitive listing pointless is the shape that makes the join’s artefacts numerous. One collection parameter, two consequences, and neither of them visible on a collection built out of a dozen long documents.

What this does to the strand #

Three sentences, and the middle one is the retraction.

The construction is correct and the sweep supporting it is correctly drawn. Output-sensitive listing does what it says on a collection where occurrences exceed documents, and this collection has measured that on real text.

The regime is narrower than the strand implied. Every plate here that showed the method winning was drawn on twelve long documents or on a planted sweep, and the shape a document collection usually has does not reach the crossing at any query the collection itself supplies. That was never checked because the collection to check it on did not exist.

And the general habit is the one this strand keeps arriving at: a method’s cost model is an input, not a property. The cost model is an input says it about the machine; this says it about the data. A structure whose advantage is a ratio is only an advantage on collections where the ratio is large, and the ratio is a property of a shape nobody was sweeping.

Length is not the variable, and three measurements say so #

The explanation offered above is a length argument: a document of 230 characters cannot hold the same six-character string many times, so the ratio is near one whatever the prose is. That is true and it is not the whole mechanism, because this page already carries three measurements and they do not line up on length.

Put them in order. The captions are about 230 characters each and give 1.04. The essays are the same prose cut into 82 documents instead of 2,214, so each is about twenty-seven times longer — call it six thousand characters — and gives 4.38. The twelve long documents of the frozen corpus are 2,048 characters each and give 32.3.

The middle collection has documents three times longer than the last and a seventh of its ratio. Length cannot be the variable, or that row is impossible.

What separates them is what the documents are. The twelve-document corpus is a set of near-copies — the collection a corpus that was not generated froze precisely because it repeats — so a string appearing once in the source appears once in every revision, and a frequent string appears many times in each. The essays are eighty-two distinct pieces of prose, and prose does not say the same six characters over and over however long it runs.

So the ratio has two inputs and the page has been attributing it to one. Length sets a ceiling — 230 characters cannot hold eleven occurrences of anything, so the captions could not reach the crossing whatever they contained — and repetition decides where under the ceiling a collection actually sits. The essays have the headroom and do not use it.

That reorders the deferrals below. A sweep of the ratio against pattern length varies the axis with the least leverage on this page: between the two long-document collections, at a fixed pattern length of six, the ratio moves by a factor of 7.4 on nothing but provenance. A pattern-length axis would have to move it further than that to be the more informative experiment, and there is no reason to think it can — occurrences and documents both fall as the pattern lengthens, so the ratio is a quotient of two shrinking numbers rather than a trend with a direction anybody can predict.

The measurement worth making instead is the one this page keeps recommending and has now run three times by accident: take four or five collections of genuinely different provenance, hold the pattern length fixed, and read the spread. It is the same suffix array and the same loop, it costs the same hour, and the answer it gives is the one a reader deciding whether to build the apparatus actually needs — because provenance is the thing they know about their corpus before they index it.

It also sharpens the recommendation into something checkable without any measurement at all. A collection of short documents cannot reach the crossing, by the ceiling argument, and two thousand documents of two hundred characters is that case. A collection of long documents may or may not, and which one it is depends on whether the documents are versions of each other. Nothing about being long is sufficient, which is the half of the recommendation these three rows add.

What is deferred #

A query log. Every ratio here is measured over the collection’s own most frequent windows, because that is what a text supplies and a planted pattern is a parameter. Real queries are words, they are unequally frequent in a way the text’s own windows are not, and the ratio under a real query distribution is a different number that nothing here estimates.

A repetitive collection of short documents, which is the one cell of the two-by-two this page does not fill: long and repetitive is the version history, long and diverse is the essays, short and diverse is the captions, and short and repetitive — logs, records, generated documents — is where a compressed index and a large document count meet.

And the ratio as a function of pattern length. Six characters is one point on an axis. A longer pattern occurs less often and in fewer documents, and both terms of the ratio fall; whether the ratio itself falls, rises or holds is a sweep of one parameter over a real collection, and it decides whether the recommendation here depends on what people search for.