Where a crossing moved to

The cost that is the size of the answer ended with a prediction, and predictions on this site are made to be checked.

The situation it left was this. A document listing that is proportional to the answer — twice the number of documents holding the pattern, plus one — costs 258 range-minimum queries’ worth of node visits, flat, whatever the range holds. A scan that is proportional to the occurrences costs one visit each. They cross at about 250 occurrences, which on eight documents is 32 per document, and below that the output-sensitive method loses.

The essay then said that a succinct range minimum “would move the document listing’s crossing from thirty-one occurrences per document to a handful”. This is what it does.

The answer #

The crossing moves from 257 occurrences to 86 — from 32.2 per document to 10.8, a factor of 2.98.

That is a real improvement and it is not a handful. Below eleven occurrences per document the scan still wins, and eleven occurrences of a phrase in a document is not a high bar to fail: it is what a moderately common word does in a page of text, and what a rare one does in a chapter.

The reason is in the previous essay and can be stated in one line: a constant-time range-minimum query is nine or ten memory accesses, not one. Ten or eleven queries at ten accesses each is about a hundred, and a hundred accesses cross a scan at a hundred occurrences.

It is worth being concrete about what that means for the method’s own claim. “Output-sensitive” says the cost follows the size of the answer rather than the size of the range, and that is true of both structures: at 790 occurrences the succinct chain spends 98 accesses and at 30 it spends 96. The claim is not weakened by the constant. What the constant decides is whether the other method — the one whose cost does follow the range — has got out of the way yet, and at eight documents that takes eighty-six occurrences.

So the honest summary of the method is two sentences rather than one. Its cost is proportional to the answer. Its constant is about a hundred accesses, and below a hundred occurrences a scan is proportional to something smaller than that.

Where the prediction went wrong #

Nothing was miscalculated. The prediction was made from an asymptotic reading, and an asymptotic reading has no place to put a constant of ten.

“Constant time” and “logarithmic” differ by a factor that grows without bound, so a structure that replaces the second with the first sounds like it removes the cost. What it removes is the growth of the cost. At the sizes here the segment tree’s logarithm is about 25 accesses a query and the succinct structure’s constant is about 10, and a factor of 2.5 is what a factor of 2.5 looks like.

This is a limit is not a prediction applied to a structure rather than to an algorithm, and it is the third time in this collection that the same reading has produced the same size of error in the same direction. The constant the notation drops is the general case; this is a worked one, with the prediction on record before the measurement.

It is also the shape of the error that the operations a candidate count leaves out records for a grid, and the two are close enough to be worth putting side by side. There, a filter’s candidate count fell by a factor of 132 and the operations those candidates cost fell by 1.8, because a candidate on one side was an array read and on the other was a point lifted through a dozen levels. Here, a query’s asymptotic class improved without bound and its cost fell by 2.5, because the class was never what was being paid.

Both are the same lesson: the unit that changes is not always the unit that is billed, and the only defence is to measure in something a reader could be charged for.

The sweep, line by line #

Eight documents of two thousand characters, the pattern planted at rising density in three of them, so the answer stays at eight documents throughout and only the occurrence count moves. That is the separation the plate needs: one cost follows the axis and the other does not.

Both chains are flat, and the succinct one is flatter — 96 to 100 across a twenty-sixfold growth in the occurrence count, against 256 to 288. The drift in the tree’s figure is the logarithm of the range the queries are asked about growing; the succinct structure has no such term, so what drift it has is which block the endpoints happen to land in — the block structure the table that fits inside a block builds, showing through in the third decimal place.

What did not change, and why that matters #

The number of queries is the same in every row: ten or eleven, which is 2s + 1 for an answer of eight documents give or take a branch that terminates early. Changing the range structure cannot change it, because that count is a property of Muthukrishnan’s recursion and not of what answers its queries.

That is worth stating because it is the part of the method that is genuinely output-sensitive, and it survives everything. A list of documents is not a list of occurrences is where the recursion comes from and where its query count is derived. What the range structure decides is the constant multiplying it, and this strand has now measured two values of that constant. There is no third one available without a different recursion.

The other half: what it costs to hold #

The crossing is one of two numbers the earlier essay left. The other was that the listing apparatus — the document array, the chain of previous occurrences, and the range minimum over the chain — came to 2.3 times the index it sits on, with 62% of that being the range structure alone.

With the succinct structure it comes to 1.47 times, and the range minimum falls to about a third of the apparatus rather than nearly two thirds of it.

That is the more decisive of the two results. A structure that triples the size of the index it is bolted to is one a reader weighs; a structure that adds half again is one they build. And the two remaining terms — the document array and the chain — are each n⌈log₂ n⌉ bits and are untouched by anything in this strand, which is the same position one separator, or one for each left the collection’s own text in, so they are now the larger half of the apparatus and the obvious place for the next idea.

Why the crossing does not move further #

It is tempting to read the two results together and expect the crossing to have moved by the same factor the apparatus did. It did not: the apparatus fell by 1.63 and the crossing by 2.98, and neither number causes the other.

The crossing is set by the query cost and the apparatus by the size, and the succinct structure is better at both by different amounts — 2.5 times on accesses and 4 times on the range structure’s own bits. Nothing requires those to agree, and a structure that traded more space for fewer accesses would move one and not the other.

That is worth carrying because a reader deciding whether to build this has two questions and this strand answers them separately. If queries are rare and the index has to fit, the size result decides it. If the collection is queried constantly, the crossing does.

The crossing on a smaller collection #

There is a regime where the chain never wins at all, and the earlier essay drew it: a collection small enough that the whole range fits in fewer occurrences than a chain’s fixed cost.

Eight documents of five hundred characters, swept the same way, never reaches 86 occurrences, so the succinct chain loses at every point of it — as the tree’s does, further out. That is not a defect of either structure; it is the flat cost of any output-sensitive method meeting a problem too small to have an output worth being sensitive to.

What a real corpus does to this #

Eleven occurrences per document is a number about a planted pattern, and a planted pattern is a parameter rather than a measurement. Whether real queries reach it is a different question, and it is one this collection could not answer until it had a corpus it did not generate.

The short answer, measured on twelve essays of a hundred and forty-five thousand characters: with a segment tree the chain beats the scan on two of twelve patterns drawn from the corpus’s own vocabulary, and with the succinct structure on seven of twelve. What the generated collection was right about is where that measurement sits, and it is the clearest case in this collection of one strand’s structure deciding another strand’s conclusion.

What was checked #

The two structures are required to answer identically, not equivalently: the same position, on four hundred random ranges of a three-thousand-element array, at three combinations of encoding and blocking. A tie makes “the same minimum” and “the same position” different claims, and a listing that walks left and right of the reported position notices the difference.

The listing itself is required to return the same documents by both routes on every collection measured, checked against exhaustion — the set of documents obtained by looking at every occurrence. And the crossing is computed by interpolation between measured points rather than read off a plate, so that the number quoted is not a member of the list of densities that happened to be swept.

The two numbers this strand produced are a query cost and a size, and the section after next is about which of the method’s parameters the first of them is really a function of.

What a reader should take from a structure with two numbers #

There is a habit this collection keeps returning to, and this strand is a clean instance of it: a structure has a size and a query cost, and quoting either one alone is a way of choosing the answer.

The published description of a succinct range minimum leads with the size — 2n + o(n) bits — because that is the surprising half and the half the name is about. Read only that, and the structure is a seventeenfold saving over a segment tree. Measure it, and it is 2.85 times, because o(n) at sixty-five thousand values is five times the payload.

The published description leads on the query with “constant time”, because that is the strong statement. Read only that, and a query costs nothing. Measure it, and it is ten memory accesses, which crosses a scan at a hundred occurrences.

Neither reading is wrong about the mathematics and both are wrong about the structure, in the same direction, by about the same factor. What O-notation does not say is the essay this collection opens with and it is the one this strand keeps rediscovering: a class is a statement about a family of inputs growing without bound, and every decision anybody makes is about one input of a fixed size.

Two numbers that did not exist before this strand #

Both of the results above are comparisons, and comparisons need both sides to have been built. That is the reason this strand exists at all rather than being a paragraph in the essay that named it.

The earlier essay could say that the crossing was at thirty-one occurrences per document and that a succinct structure would move it. It could not say where to, because the number depends on a constant that no account of the structure states — nine or ten accesses is not in any description of the method, and it is not derivable from “constant time” by any amount of reading.

The same is true of the apparatus. That the range minimum was 62% of the listing’s overhead was measurable from the segment tree; that it becomes about a third was not measurable from anything until the alternative was built and weighed the same way.

A structure that is named and not built is a structure whose constants are unknown, and this collection’s habit of building the alternative rather than citing it is what turns two hopeful sentences into two numbers. The hopeful sentences were, in this case, optimistic by a factor of about three.

Which parameter the crossing is actually about #

The crossing is quoted per document — 10.8 with the succinct structure against 32.2 with the tree — and the per-document form hides which parameter it depends on, which is worth extracting because it decides where the method is worth using.

The chain’s cost is $2s+1$ queries at about ten accesses each, where $s$ is the number of documents holding the pattern. So the crossing, in total occurrences, is about $(2s+1)c$ and it does not mention the size of the collection at all. Dividing by the number of documents to get a per-document figure introduces a $d$ that was never in the cost.

Which means the honest statement is: the chain wins when the pattern occurs more than about $(2s+1)c$ times in total, and whether that is easy or hard depends entirely on how $s$ behaves as the collection grows.

A rare pattern is the good case. If a phrase appears in three documents whatever the collection’s size, then $s$ is fixed, the crossing stays near ninety occurrences, and the per-document figure falls like $1/d$ — so on a collection of a thousand documents the method wins on a pattern occurring ninety times anywhere in it, which is a very low bar.

A common pattern is the bad case. If the pattern is in a constant fraction of the documents then $s$ grows with $d$, the crossing grows with it, and the per-document figure is constant — the method never gets any easier however large the collection becomes.

That is the reverse of the reading the per-document number invites, and it explains the real-corpus result without any further measurement. Seven of twelve patterns beat the scan there because patterns drawn from a corpus’s own vocabulary are mostly rare — most words are in a few documents rather than in most of them — and it is exactly the rare ones the method is built for.

So an output-sensitive listing is worth building for a collection whose queries are specific, and worth nothing for one whose queries are common words. Both halves of that were in the arithmetic before either structure was built, and neither is visible in a crossing quoted per document.

What this strand did not do #

It did not touch the chain of previous occurrences, which is n⌈log₂ n⌉ bits and is now the largest part of the listing apparatus. It did not touch the document array. And it did not change the number of queries, which is the part of the method that is genuinely output-sensitive.

What it did was replace one structure with the structure the method is published with, and measure what that is worth: a factor of three on the crossing and 1.6 on the apparatus, from a structure whose own accounting turned out to be five times its payload and whose most expensive design decision was which order to write its parentheses in.

The strand’s own deferral is what it leaves: an output-sensitive listing whose apparatus is now dominated by two plain arrays, and no idea here for making either of them smaller.