A document already in the answer

The algorithm is six lines, and every one of them was already there.

Given the rows [lo, hi) of a pattern: ask the range minimum for the position of the smallest chain value in the subrange; look up the document at that position; if it is already in the answer, stop; otherwise report it and recurse on both sides, left first.

The only change from the published version is the third line, which used to compare a chain entry against the start of the range.

Why it is the same walk #

The two tests agree at every step, which is stronger than the two methods agreeing on the answer.

That is checked directly: run the walk with both tests evaluated at every subrange, and require them never to differ. Over forty collections, 268 steps in total, they never do — and a step where they differed would be a counterexample rather than a discrepancy to explain.

The array the walk never reads is the argument for why: C[at] < lo says this is the first row of this document in the range, and a left-first walk has already reported every document whose first row lies to the left. The test is asking whether the document is new, and the answer knows.

Where the recursion order matters #

The chain version does not care about the order. C[at] < lo is a comparison of two numbers that do not depend on what has been visited, so recursing right before left reports exactly the same set, in a different sequence.

The chainless version cares completely.

Exchange the two recursions and the walk loses documents. On a collection of 24 documents, over 40 patterns tried, some were lost on 5% of them — and the worst case reported nine documents against a true seventeen.

The mechanism: with the order reversed, a subrange to the right can be visited before the subrange containing a document’s first row. The document is not yet in the answer, so the walk reports it there — fine — but it also prunes on the left where the real first occurrence was, and the recursion that would have found other documents beneath it never happens.

The failure is silent, which is what makes it worth a check rather than a comment. Every document the broken walk reports is genuinely in the answer; the answer is short, and a document listing has no way to notice what it did not find.

The bitmap, and how it is cleared #

The state is one bit per document, and clearing it is where a naive implementation loses the property the method exists for.

Walking the bitmap costs d per query. On two thousand documents, answering a query whose answer is three, that is the dominant cost and it is proportional to the collection rather than to the answer — which is exactly the thing output-sensitive listing is supposed to avoid.

So the walk remembers what it set and unsets that: |answer| writes, not d. Measured on a collection of 512 documents with an answer of 166: 166 clears.

The check requires both halves — that the clears equal the answer’s size, and that they are fewer than the collection — because a version that cleared everything would satisfy the first half of the sentence and none of its purpose.

And the mirror defect is in the gate too. Leave the bitmap dirty between queries and a later query reports 0 documents where the answer is 3, because they were all marked by an earlier one. Same silence, same shape.

The range minimum, told to forget #

The structure over the chain is built from the chain and does not hold it. That is the property the shape a range question is about establishes: 2n parentheses hold the shape of the array, the query returns a position, and the value at that position is read out of the caller’s array purely as a convenience.

A caller that only ever compares the answer has no use for the values, so this one drops them — and the range minimum drops its reference too.

That is a method rather than a constructor flag, because it is a claim: after the call the structure cannot read a value even by accident, so a caller that still works has demonstrated it never needed them. Asking it for one raises.

The check is the obvious one: build the index, ask the forgotten structure for a value, require it to refuse. Without that, “the chain is not part of the structure” would be a statement about code somebody read rather than a property of the object.

What is checked, in total #

Five things, and they divide into the ones that must hold and the ones that must fail.

Must hold. All three methods — scanning the occurrences, walking with the chain, walking without it — return the same documents on every pattern tried. The two tests agree step for step. The queries are identical in number. The clears equal the answer’s size. The apparatus is smaller than the index it sits on, which is the size claim of the strand.

Must fail. A right-first walk loses documents. A dirty bitmap under-reports. A forgotten range minimum refuses to hand back a value.

That division is the shape every strand here ends with: the check must reject, because an assertion that has never rejected anything proves nothing about the sentences written on top of it.

What Sadakane’s substitution actually is #

Worth naming plainly, because “replace the test” undersells it.

The published method needs the chain because its test is about the chain. What the substitution notices is that the information in the test — is this document new — is available for free from the output, and that the output exists whether or not anybody thought of it as state.

That is a specific kind of move: an algorithm’s own accumulating answer is a data structure it is already paying for. Nothing else in this collection uses it, and it is worth having as a habit, because a structure that duplicates something the algorithm already holds is a structure that can be removed rather than shrunk.

The cost is that the algorithm becomes order-dependent. The chain version’s test is a function of the input alone, so it is correct under any traversal; the chainless version’s test is a function of the traversal’s history, so exactly one order works. That is the price of removing n⌈log₂ n⌉ bits, and it is paid in the form of an invariant somebody has to know about.

Reading the trace #

The plate at the top of this page is the algorithm running, and it repays being read row by row.

Each row is one subrange the walk considered. The first column is the subrange; the second is the position the range minimum returned and the document there; the third is what the chain test said; the fourth is what the answer-so-far test said.

The first row is the whole range: the minimum lands somewhere in the middle, its chain entry is before the range, and both tests say new. The walk reports the document and recurses left.

Two rows later a subrange arrives whose minimum is a document already reported. The chain entry there is inside the range — it points at the row where that document was first found — and both tests say not new. The walk stops, and everything below that subrange is pruned in one step.

That pruning is where the output-sensitivity comes from. A subrange whose minimum fails the test contains nothing new by definition: the minimum is the smallest chain value in it, so every other entry is at least as large and therefore also inside the range.

Why exhaustion rather than examples #

The equivalence is checked over forty collections and 268 steps, and the checks that must fail are run over forty patterns each. That is not a large number, and it is a deliberate choice about what kind of evidence this is.

A proof would be better and this collection does not prove things: it states a claim and gives it a test it could fail. The test here is strong in a specific way — it compares the two tests at every step, not the two answers at the end — so a single subrange where they differed would be a counterexample, and a hundred collections agreeing on their answers while differing internally would not pass.

The other side of the same discipline is that the defects have to be found rather than argued about. The wrong recursion order does not fail on every pattern; it failed on 5% of the forty tried, which means a check running one pattern would have passed and a check running ten would probably have passed.

That is the argument for sweeping rather than sampling wherever it is affordable, and here it is affordable: forty patterns over a small collection is milliseconds.

Forty patterns is not enough, and the arithmetic says how many is #

“It failed on 5% of the forty tried, which means a check running one pattern would have passed” is the right instinct and it stops one step short. The same rate says something about forty.

A defect that fails on a share $p$ of patterns escapes a gate of $N$ independent patterns with probability $(1-p)^N$. At $p = 0.05$ and $N = 40$ that is $0.95^{40} = 0.129$: the gate as run misses this defect about one time in eight. Not once ever, on the collection it was tuned against — but a gate is meant to catch the defect on a tree nobody has seen, and one run in eight is not a check, it is a coin weighted three to one.

Rearranged, the requirement is

$$N \;\ge\; \frac{\ln(1-c)}{\ln(1-p)},$$

which for 99% confidence is about $4.6/p$: ninety patterns to catch a defect failing at five per cent, four hundred and sixty to catch one failing at one per cent, and forty-six hundred at a tenth of a per cent. The size of a sweep is set by the rarest defect it has to catch, and that rate is not observable from the defects it has already caught — the 5% here is measured on one broken implementation, and the next broken one will have its own.

Two things follow, and the first is free.

Run more patterns. Forty patterns over a small collection is milliseconds, so the gate is nowhere near a cost that justifies the sample size it uses. Two hundred would put the escape probability at $0.95^{200}$, which is one in twenty-three thousand, at a cost nobody would notice.

And prefer the check that fails per step. This is where the step-level comparison earns its place beyond the argument this page already makes for it. Comparing the two tests at every subrange gives 268 opportunities to disagree across the same forty collections, against forty opportunities to produce a short answer — so the defect’s per-case rate is enormously higher against the stronger check, and the required $N$ collapses. A check placed close to the mechanism needs a smaller sweep than one placed at the output, and the ratio between the two sample sizes is the ratio between their per-case rates.

That is the same discipline one pass, k slots, and two randomness budgets applies to a biased sampler, where the noise floor at four hundred runs is fourteen per cent against a bias of twenty-three and the test proves nothing, and at forty thousand runs the two are a factor of seventeen apart. There the sample size is set by an estimator’s variance; here it is set by a defect’s incidence; in both cases a gate that has not had its own detection probability computed is a gate whose passing means an unknown amount.

Neither changes the conclusion of this page. The right-first walk is broken, the check found it, and the equivalence holds where it was measured. What the arithmetic adds is that the sweep should be larger than the one that happened to be enough.

What an implementation should actually do #

Three notes for anybody writing this, because the details are where it goes wrong.

Keep the reported set as a bitmap indexed by document, not as a hash set. The cost of the method is meant to be proportional to the answer, and a hash set’s constant is large enough to matter against a range-minimum query that is nine or ten memory accesses.

Clear it by the answer. The list of reported documents is the output, so unsetting exactly those bits is free of extra bookkeeping. Clearing by sweeping is d per query and undoes the method on a large collection.

And make the range minimum forget. If the structure holds a reference to the chain, the chain stays alive and the saving is imaginary — which is the difference between a paper result and a measured one. The forgetting is also what turns “the values are not needed” into something the build can check.

A fourth note, which is about the shape of the code rather than about performance: the recursion is naturally written as two calls, and the order of those two calls is load-bearing. It deserves a comment, because it looks like a symmetry and is not.

What it does not fix #

Two things, and both are properties of the method rather than of this formulation.

The answer can still be large. Output-sensitive means proportional to the answer, and a pattern occurring in every document of a large collection has an answer the size of the collection. The method is then doing d queries, each of which is several memory accesses, against a scan that would have read the occurrences — and the crossing that never arrives is the page about when that comparison goes the wrong way.

And the document array is still there. Every step reads D[at] to find out which document a row belongs to, so the array that answers that is not removable by this argument. It is the largest remaining part of the apparatus, and what the chain cost is where the accounting lands.

So this page removes one of the three structures the apparatus is made of. The second was replaced by a smaller one in an earlier strand, and the third is information the collection genuinely contains.

The invariant, written down #

Since the whole correctness of this rests on a property of the traversal, it is worth stating in the form somebody could check against an implementation.

At the moment the walk considers a subrange [a, b), every position in [lo, a) has been visited, and every document whose first row in [lo, hi) lies in [lo, a) has been reported.

The first clause is the left-first order. The second follows from it plus the pruning rule: a document’s first row has a chain entry below lo, so no subrange containing it can be pruned, so if it is to the left it has been reported.

Given that, the test D[at] ∈ answer is true exactly when C[at] ≥ lo, which is the equivalence the substitution needs. And an implementation that violates either clause — by recursing right first, by pruning early, by clearing the bitmap mid-query — loses documents silently.

That is the sort of invariant that belongs in a comment beside the recursion rather than in a paper, because the code that breaks it looks correct.

Where this sits in the strand #

The array the walk never reads is what the chain’s test is asking. This page is the algorithm. What the chain cost is the size the removal buys, and the apparatus that is smaller than its index is the accounting with the recommendation attached.

The structure the walk queries was built in the shape a range question is about, and the reason the walk exists at all is a list of documents is not a list of occurrences — a collection supports a question a text does not, and answering it at the price of its answer is the whole of document retrieval.

The two silences #

Both defects in this page fail silently, and the pair is worth putting beside each other because they fail in the same direction and for different reasons.

A right-first walk under-reports because the equivalence between the two tests breaks: a document not yet in the answer is reported at the wrong position, and the recursion that would have found the rest is pruned. Nothing about the answer looks wrong; it is short.

A dirty bitmap under-reports because the per-query state is not per-query: documents reported by an earlier query are skipped by a later one. Again, nothing looks wrong.

Neither is detectable from the output, because a document listing’s output is a set with no size anybody knows in advance. That is what makes them worth catching in a gate rather than in review, and it is why both are in this collection as checks that must fail rather than as comments about care.