Work that falls as the answer grows

An output-sensitive method is one whose cost follows the size of the answer rather than the size of the input. The phrase is usually taken to mean linear in the answer, and for the methods this apparatus started with that is right.

The descent over a compressed document array is not linear in the answer. It is sublinear, and the reason is a counting fact about trees that has a consequence for how the method should be reported.

The sweep #

Thirty-two documents, a pattern planted in a controlled number of them, and the number of holding documents swept from one to thirty-two. The row range grows from seventeen to three hundred and twenty-four — a factor of nineteen — and the answer from seven documents to thirty-two.

Reading every occurrence goes from seventeen operations to three hundred and twenty-four. That is the range, exactly, because that is what it reads.

The range-minimum walk goes from a hundred and fifty-four to eight hundred and eighty-six.

The descent goes from thirty-six to sixty-two.

Per document: 5.14 operations at an answer of seven, and 1.94 at an answer of thirty-two. The work per document falls by a factor of 2.65 while the answer rises by a factor of 4.6.

Those three lines are three different functions and it is worth naming them before explaining any of them. The first is the range. The second is the answer times a logarithm times a constant of about twenty. The third is the answer times a logarithm that shrinks as the answer grows. Only the third has a shape that is not one of the two things a cost is usually proportional to.

Why it falls #

A descent enters exactly the ancestors of the leaves it reports. The ancestors of one leaf are a root-to-leaf path, log₂ d nodes. The ancestors of two leaves are two paths that share their top, so fewer than 2 log₂ d. The ancestors of k leaves in a tree of d number at most k(1 + log₂(d/k)), which is a standard counting bound and is tight when the leaves are spread evenly.

At k = 1 that is 1 + log₂ d, or six on thirty-two documents. At k = d it is d, every leaf and its one distinct ancestor’s worth, which is 2d − 1 nodes for the whole tree.

So the per-leaf cost is (1 + log₂(d/k)), which falls as k rises and reaches one when k = d. Two ranks a node makes the operation count 2k(1 + log₂(d/k)), and dividing by k gives 2(1 + log₂(d/k)) operations a document.

Substituting: at k = 7 and d = 32 that is 2(1 + 2.19) = 6.4, and the measured figure is 5.14. At k = 32 it is 2, and the measured figure is 1.94. The bound is loose by about twenty per cent because the leaves are not evenly spread, and the shape is exactly right.

The same counting fact appears in two other places in this collection and it is the same fact each time. A trie over k keys of length m has fewer than km nodes because prefixes are shared; a merge of k sorted lists costs n log k rather than n log n because the tree is shallower; and here, k leaves have fewer than k log d ancestors. In every case the saving is that paths overlap near the root and the overlap is worth log(d/k) rather than log d.

What makes it visible here rather than absorbed into a constant is that k moves over the sweep. In a trie the key count is fixed by the input; here the answer’s size is the axis, so the discount is drawn rather than assumed.

What that does to the phrase #

“Proportional to the answer” has a constant in it, and the constant here is not constant.

A method costing c·k operations for an answer of k has a single number c that can be quoted, compared and used to find a crossing. A method costing 2k(1 + log₂(d/k)) does not: its effective constant is 6.4 at one answer size and 2 at another, on the same collection.

That matters for the crossing. Reading every occurrence costs the range, which on this collection is roughly ten times the answer. So the descent beats it when 2(1 + log₂(d/k)) < 10 × (range/answer per document), and the left-hand side is moving.

There is a second thing “proportional to the answer” hides, and it is the one that bit the earlier methods. Two methods can both be linear in the answer and differ by a factor of twenty in their constants, which is what the range-minimum walk and the descent do here — 886 operations against 62 for the same thirty-two documents. Asymptotically identical, and one of them loses to reading every row on every collection this field has and the other does not.

That is the general reason the cost that is the size of the answer drew a crossing rather than reporting a class. A class tells a reader which method wins eventually; a crossing tells them whether eventually has arrived.

The comparison that decides #

At an answer of seven the descent costs thirty-six operations and reading every occurrence costs seventeen. The naive method wins.

At an answer of thirty-two the descent costs sixty-two and reading every occurrence costs three hundred and twenty-four. The descent wins by a factor of five.

Somewhere between an answer of seven and an answer of sixteen the two cross. On this sweep the crossing is at an answer of about ten documents out of thirty-two, which corresponds to a range of about eighty-six rows — that is, about nine occurrences a document.

That number should be read carefully because it is a crossing in the range, not in the density. The relevant question is whether the range is large relative to the answer, and on this planted collection the range grows faster than the answer because more holding documents means more occurrences per holding document too.

Doubling the document count deepens the tree by one level, so the per-document cost at a fixed answer size rises by two operations, and the discount at a full answer grows because log₂(d/k) has further to fall. The two effects push in opposite directions and the second wins at large answers: the descent’s advantage over the naive method is larger on a collection with more documents, which is the direction a reader would want and is not automatic.

Why the earlier crossing was so much worse #

The crossing that never arrives measured the published apparatus and put its crossing at 10.8 occurrences a document. That structure held a chain, a segment tree and the document array, and its walk cost a range-minimum query per reported document plus one per pruned subrange.

The descent’s crossing on the same kind of collection is around three and a half, and the reason is entirely the constant. Both methods are proportional to the answer in the asymptotic sense; one of them pays a segment-tree traversal per document and the other pays two ranks per shared ancestor.

That is a large enough change to alter the conclusion of an earlier essay, and it does not alter it enough. One copy per document is one occurrence per document measures the density on every collection shape available here and finds 1.84 to 1.88 for a pattern a reader would ask for. A crossing at three and a half is still above that.

So the apparatus went from losing by a factor of two and a half to losing by a factor of about two, and it is still losing on the collections that exist.

There is a fair objection to that comparison, which is that the two methods are being run on different structures — the walk on a chain and a segment tree, the descent on a compressed array — so the operation counts are not commensurable. A segment-tree node visit and a bit-vector rank are not the same unit.

The answer is that both are counted the same way here: an operation is a read of a directory entry or a node, charged once. That is a coarse unit and it is the one this collection has used throughout, and its coarseness cuts against the descent rather than for it, because a bit-vector rank on a compressed vector is genuinely more expensive than a segment-tree comparison. So the factor of fourteen between 886 and 62 is a lower bound on the descent’s advantage in operations and an overstatement of it in time.

Quoting it as a factor of fourteen in time would be the error the unit of cost is not one exists to prevent, and it is not quoted that way here.

The floor the descent cannot get under #

There is a floor and it is worth stating because it bounds what any further improvement can achieve.

Reporting k distinct documents requires distinguishing them, and distinguishing k things out of d requires at least k log₂(d/k) bits of information to be read — an information-theoretic bound rather than a property of any structure. The descent reads 2k(1 + log₂(d/k)) bit-vector ranks, and each rank returns a number rather than a bit — the distinction rank is the only thing it does is built on, so the comparison is not immediate; but the shape of the descent’s cost is the shape of the bound.

That is unusual in this collection. Most structures here have a cost whose shape is an artefact of the structure — a segment tree’s log is the tree’s depth, a chain’s cost is a comparison per row — and this one has a cost whose shape is the problem’s.

It means the descent is not merely better than the range-minimum walk; it is within a constant of the best possible shape for the reporting part of this problem. What it does not bound is the searching part, which is finding the row range in the first place, and that is the suffix array’s job and is unaffected.

The other direction: early stopping #

The sublinearity has a practical consequence that nothing in this apparatus exploits and a real system would.

A search interface showing ten results does not want all four hundred documents holding a pattern. It wants ten. The descent visits leaves in a definite order — the tree’s leaf order — so it can stop after ten, at a cost of 2 × 10 × (1 + log₂(d/10)) operations rather than the full answer’s.

On a collection of ten thousand documents with an answer of four hundred, reporting ten costs about 200 operations against the full answer’s 3,900. That is a factor of twenty for a query nobody would notice was truncated.

The range-minimum walk supports the same thing and reading every occurrence does not, which is a genuine advantage of both output-sensitive methods that no measurement in this strand has taken. It is named here and not built.

A crossing that is not a number #

One more consequence of the shrinking constant deserves stating, because it changes what a crossing is.

With two methods whose costs are a·range and c·answer, the crossing is a single ratio: the method wins when range/answer exceeds c/a. One number, quotable, and the same on every collection.

With the descent the comparison is range against 2k(1 + log₂(d/k)), which involves d as well as the ratio. So the crossing depends on the collection’s document count and on where in the collection the answer sits, and there is no single ratio to quote.

Working it out on this sweep: at d = 32 the descent wins when the range exceeds roughly 2k(1 + log₂(32/k)), which at k = 8 is 56 rows and at k = 32 is 64. So the crossing in rows barely moves while the crossing in occurrences per document falls steeply — from seven at a small answer to two at a full one.

That is why this strand’s crossings have been quoted three different ways in three essays and none of them was wrong. The published apparatus had a constant, so 10.8 occurrences a document was the right form. The descent does not, so a single density is the wrong form and the honest statement is the formula plus the collection’s d.

Which order the leaves come in #

Early stopping raises a question the full-answer case does not, and it is worth flagging because it turns a small ordering issue into a correctness one.

The descent’s leaf order is the tree’s, which on a frequency-shaped tree is frequency order rather than document order. Stopping after ten therefore reports the ten documents whose codes come first, which is an arbitrary subset — not the ten smallest document numbers, not the ten with the most occurrences, and not any ordering a reader would expect.

For a full answer that does not matter, because the set is the same and sorting is cheap. For a truncated answer it matters completely: the ten reported are decided by the code shape, which is decided by the collection’s length distribution, which has nothing to do with relevance.

So a system doing early stopping needs either a balanced tree, which gives document order and costs the compression, or a ranking criterion applied to the whole answer, which defeats the point. The smaller tree hands it back unsorted prices the first of those, and the second is why real search systems do not truncate a document list this way.

Three shapes a cost can have #

It is worth collecting the shapes this apparatus has produced, because a reader choosing between them is choosing between shapes rather than between numbers.

Proportional to the input. Reading every occurrence costs the range. It is the cheapest method when the range is small and it degrades without limit: a pattern occurring a million times in three documents costs a million operations to report three.

Proportional to the answer, with a large constant. The range-minimum walk. Its cost stops following the range, which is the property being bought, and the price is a constant of about twenty-seven operations a document — enough that on every collection in this field the property is not worth what it costs.

Proportional to the answer, with a shrinking constant. The descent. Its cost is 2k(1 + log₂(d/k)), so it is between six and two operations a document depending on how much of the collection is in the answer, and it is the only one of the three whose per-unit cost improves as the work grows.

The third shape is the one worth having and it is also the one that is hardest to summarise. A method whose per-unit cost is 5.14 in one regime and 1.94 in another cannot be quoted with a single constant, and the temptation is to quote the average — which is the statistic distributions, not averages exists to warn about, and which here would hide exactly the feature that makes the method good.

The right summary is the formula, and the formula is short enough to carry: two ranks per shared ancestor, and the shared ancestors of k leaves out of d are k(1 + log(d/k)). Everything above follows from that and from nothing else about the structure.

What the measurement had to be careful about #

The sweep above holds one thing fixed that is easy to let move, and getting it wrong produces a plate that says nothing.

The answer’s size is varied by planting the pattern in a controlled number of documents. The occurrences per holding document is held at the planting rate. So the range grows because the answer grows, and the ratio between them stays roughly constant — which is what makes “work against answer” a meaningful axis.

The alternative — varying the pattern’s length, which changes the range — moves both the answer and the density at once, and the resulting plate cannot separate a method that follows the answer from one that follows the range. That is the same design error a boundary that costs nothing records for a different sweep: the axis has to be the thing being varied and nothing else.

The check that the sweep is measuring what it claims is that the per-document cost of the descent stays inside a band while the range moves by a factor of nineteen. It moves by 2.65, which is the ancestor-sharing effect and is predicted; if it moved by nineteen the method would be following the range and the label would be wrong.