What the generated collection was right about

This is the accounting. Five strands were built on collections made by one line with one dial; a corpus that nobody made now exists; here is what each strand’s conclusions look like against it.

The summary is that structural conclusions transfer and descriptive ones sometimes do not, and that one number nobody could check turns out to be met — with the structure the strand on range minima built, and not otherwise.

The crossing that was guessed at #

The cost that is the size of the answer measured that the output-sensitive listing beats a scan above about thirty-one occurrences per document, and then wrote a sentence that was a guess:

That is much lower than it sounds. A phrase occurring thirty times in a document is not unusual; a common word occurs hundreds of times.

On twelve real essays of 144,617 characters, the most frequent six-character string is " that " at 388 occurrences across all twelve documents — 32.3 per document.

The guess was right and it was right by a hair. The most frequent six-gram in a real corpus sits exactly at the crossing, and everything less frequent is below it: the fourth-most frequent is at 20.3 per document, the sixteenth at 14.1, the sixty-fourth at 8.3.

So with a segment tree the output-sensitive method wins on two of twelve real queries — the two most frequent patterns at four characters, and nothing at six.

Why the top of a frequency distribution is where it sits #

It is worth understanding the coincidence, because it is not entirely one.

Natural language’s word frequencies fall steeply — the commonest few words account for a large share of a text — so the most frequent six-character string in a corpus of any size occurs a number of times roughly proportional to the corpus. Twelve documents of twelve thousand characters gives about four hundred occurrences of " that ", and four hundred over twelve is thirty-three.

Double the corpus and that number doubles; halve it and it halves. So “the top of the distribution sits at the crossing” is a statement about a corpus of this size, and a corpus ten times larger would have its top ten times above the crossing.

The useful reading is therefore not that real queries just barely reach the crossing. It is that at this corpus’s size they barely reach it, and the crossing is a fixed number of occurrences per document while the frequency distribution scales with the corpus.

What the other strand changed about that #

Where a crossing moved to replaced the segment tree with the structure the method is published with, and measured the crossing moving to 10.8 occurrences per document.

On the same twelve real queries: seven of twelve.

That is the clearest cross-strand result here. A structure built in one strand decides whether a method from another strand is worth using on real data, and neither strand could have said so alone: one had no real corpus and the other had no alternative range structure.

It is also the clearest instance here of a pattern worth naming. Both strands were pieces of work named earlier and taken together, for unrelated reasons — one because a structure was named and not built, the other because every collection was generated. Neither anticipated the other.

Taking several deferrals at once produces results neither would have had, and that is an argument for the way this collection schedules work rather than an observation about range minima.

What transferred exactly #

The artefact arithmetic. (m − 1)(d − 1) spanning windows, on all three parts at four window lengths, exact to the window.

The listing’s query count. 2s + 1 range-minimum queries for an answer of s documents, whatever the range holds. It is a property of Muthukrishnan’s recursion and it does not know what the documents are.

The two repetition measures’ relationship, which the collection decides which index is small established. A collection with more runs per character has more phrases per character, on real data as on generated, across all three parts.

And the order-independence. Shuffling a version history’s documents moves the run count by 0.06% and the phrase count by 0.4%. The generated collections are exchangeable copies by construction; the real one is exchangeable too, on these measures.

What transferred with a different constant #

The share of artefacts that are new. The occurrences a join invents said just under half; twelve unrelated essays say all of them, at every window length. That correction makes the original argument stronger, and documents that are not the same length is where it is measured.

The depth of a parse. Every measurement in the ladder a parse that will not follow a long chain opened was taken on a collection whose worst depth was between ten and twenty-two, and those numbers are properties of how many copies of how long a base text. No real depth profile has been measured, and that is a gap this strand does not close.

And the crossing. Thirty-one occurrences per document was measured on a planted pattern at eight documents; on real prose at twelve documents the top of the frequency distribution sits at 32.3, which is the same number by coincidence and would not be on a different corpus.

What was a property of the generator #

One headline, and it is a clean one.

A separator per document costs a whole bit per character, which is one separator, or one for each’s headline. It does, at 22 symbols, where fourteen separators cross 32. Real prose has 87 symbols with 41 of headroom below 128, and the same separators cost 0.04%.

That is the only conclusion in five strands that this corpus overturns, and it is worth being clear about why it is the only one. Everything else is a statement about a relationship — how a size follows a measure, how a cost follows a count — and a relationship survives being evaluated at a different point. The separator finding is a statement about a value, evaluated at a threshold, and a value evaluated at a threshold is a statement about where the data sits.

The measure that did not need checking and got it anyway #

The order-independence result is the only one here that was a genuine surprise in the direction of the model being right.

The intuition — a version history is small because consecutive versions sit next to each other — is natural, is stated nowhere in this collection, and is wrong. Both measures find a previous occurrence wherever it is; every version of a file resembles every other version, not only the one before it; so which version a phrase copies from moves under a shuffle and how many phrases there are does not.

That matters beyond this strand, because it says the generated collections’ central simplification — that copies are exchangeable — is one the real thing shares. A generator that produced the right documents in the wrong order would be indistinguishable from one that got the order right.

Why “per document” is the right axis, and which kind of growth moves it #

The crossing is quoted in occurrences per document, and the table shows why that unit is not an arbitrary normalisation — it is the only one in which the crossing is a constant.

Read the succinct column: 149, 143, 120, 102, 108, 50 for patterns occurring 388, 244, 169, 99, 42 and 17 times. The occurrence count falls by a factor of twenty-three and the cost falls by three. That is because the listing performs $2s+1$ range-minimum queries for an answer of $s$ documents, and every one of the top patterns is in most of the twelve, so $s$ barely moves. The method’s cost is bounded by the corpus’s document count and is nearly blind to how often the pattern occurs inside them — which is what output-sensitive means, stated in the unit the answer is actually measured in.

The scan’s cost is the opposite: it is the total occurrence count, with no ceiling at all.

So the comparison is $c\,d$ against $f\,d$, where $d$ is the document count, $c$ is what a document costs the listing and $f$ is occurrences per document. The $d$ cancels, and the crossing lands at $f = c$ — a fixed number of occurrences per document, independent of how many documents there are. That is the invariance the axis is exploiting, and it is the reason 31 and 10.8 are quotable as numbers rather than as numbers-for-this-corpus.

Which sharpens the scaling paragraph above, because the two ways a corpus can grow are not the same.

Longer documents move the crossing’s traffic. A fixed string’s frequency per document is proportional to a document’s length, so doubling the length of every document doubles $f$ and pushes every pattern up the table. Ten times the length and the top pattern sits ten times above the crossing, which is what the essay’s scaling argument describes.

More documents move nothing. Adding a thousand documents of the same length multiplies both sides by a thousand: the scan sees a thousand times the occurrences and the listing answers a thousand times the documents. The top pattern still occurs 32.3 times per document and still sits at the crossing. A corpus that grows by acquiring documents never clears it.

That second case is the one document retrieval is actually about — many short documents rather than a few long ones — and it is the corpus shape this strand explicitly does not have. So the honest reading of “seven of twelve real queries” is that it is a measurement at one document length, and that the missing corpus of a thousand emails of four hundred characters would put every pattern below the crossing rather than above it, because four hundred characters is a thirtieth of an essay.

Which does not make the output-sensitive method useless there; it makes the comparison a different one. On short documents the scan is cheap because there is little to scan, and the listing’s advantage has to come from somewhere other than occurrence density — from a list of documents not being a list of occurrences in the first place, which is a statement about what the query asks for rather than about what either method costs. Where a crossing moved to settles the cost side; this is the parameter it holds fixed.

What could not be checked at all #

Three things, and the honest position is that nothing here touches them.

Scale. This corpus is 320,000 characters. The structures these strands weigh are deployed on genomes and code archives at a thousand times that, and nothing in this collection has ever measured above 65,536.

The depth profile of a real repetitive collection. The cap ladder’s whole subject is generations of copying, and no real version history’s depth histogram has been computed here. It is one linear pass now, and it is a deferral rather than a result.

And a real corpus of many short documents, which is the shape document retrieval is actually about. Twelve essays of twelve thousand characters is not a thousand emails of four hundred, and the artefact count — (m − 1)(d − 1) — is worst on exactly the collection this corpus is not.

The distinction the whole strand is about #

A generated collection is an instrument. Its job is to produce a controlled input so that a structure’s behaviour can be measured as a function of a stated degree of repetition, and it does that job: the dial moves the measures monotonically, the same setting gives the same collection, and every measurement taken against it is reproducible.

It is not a sample — the distinction the model a bound was quoted in makes about bounds, applied to data. It has one document length, one edit rate, one alphabet, one arrangement of its repetition — so any sentence of the form this is what a repetitive collection is like drawn from it is a sentence about the instrument.

The failure, where there was one, is not in the generator. It is in sentences that treated an instrument’s reading as data, and there turn out to be very few of those across five strands: one, and it is about separators.

What this collection should do differently #

Three habits, and the first is nearly free.

Say what the collection was, in the plate. Every plate in these strands already carries its collection’s parameters in its caption strip; what none of them carried was the alphabet, which is the parameter the one overturned finding turned on.

Draw the threshold with the data on it. A finding about crossing a power of two should be drawn as a number line with the powers of two and the collection’s own value marked. That plate would have shown, at a glance, that 22 is unusual and 87 is not.

And measure the real thing once per strand, not once per collection. This corpus took a day and it exists now; every future strand about text can check itself against it in a function call. The reason five strands went by without one is that parsing a hundred and forty thousand characters was two hours before the linear construction landed, which is what a quadratic construction was setting in its most consequential form.

The three cheap measurements that kept turning up #

There is a thread running through all five of these strands that has nothing to do with text.

A compressed grid was proposed on an intuition about runs; a one-pass mean-run measurement and a two-line break-even would have settled it. A depth cap was swept ten times; a one-pass depth histogram would have said which caps were live. A generator was fitted to a corpus with two measures; a one-pass edit-shape measurement would have said the model was the wrong shape before any fitting.

Three strands, three cheap measurements not taken, three questions answered expensively instead. In each case the expensive route produced something extra — a floor, a scaled sweep, a fitted disagreement — so none of the work was wasted. But the pattern is consistent enough to be a habit worth adopting:

Before building the apparatus, measure the shape of the data the apparatus is about. It is nearly always one pass.

What a reader should take #

Structural conclusions transfer. How a compressed index’s size follows the run count, how a listing’s query count follows the answer’s size, how a filter’s candidate count follows the seed length — all of those are relationships and all of them hold on real data.

Descriptive conclusions need a real sample. How many documents, how long, what alphabet, how the edits are shaped: every one of those was fixed by construction in every collection here, and three of the four turn out to be different on real text by a factor of three or more.

And a threshold finding is a finding about a place. The separator result is correct and its domain is small alphabets. Stating a threshold result without stating where the data sits relative to the threshold is how a correct measurement becomes a wrong conclusion.

What the corpus cost, and what it is worth #

It is worth putting a price on this strand, because a collection deciding whether to build one should know.

The corpus itself is a list of thirty documents written out in full, frozen so that nothing can move under it. Assembling it was an afternoon. Measuring it needed the linear parse, which was another strand’s work and would have been done anyway.

What it bought: one overturned headline, one confirmed guess, three transferred findings verified rather than assumed, two new controls — the length-truncation rejection and the character shuffle — and a permanent object that every future strand about text can check itself against for the cost of a function call.

Set against five strands of conclusions that had never met real data, that is cheap. The reason it went undone so long is that it looked expensive, because the one measurement it turns on was quadratic.

What is checked #

The succinct listing wins more real queries than the tree does — seven of twelve against two — asserted, and asserted with the second condition that the tree does not win all of them, so that a corpus change making both trivially successful would fail here.

The spanning-window arithmetic is exact on all three parts.

The real alphabets are more than twice the generated one on every part, and no join crosses a power of two.

And the two controls stand behind everything: a corpus cut to one length loses 55.8% of itself and moves both measures, and a corpus with its characters shuffled multiplies the run count by 7.42 with its entropy unchanged.

What this leaves #

The oldest deferral in this collection is closed and it leaves three sharper ones: a real corpus at a million characters, a real depth profile, and a real collection of many short documents.

All three are now one function call away from being measured, because the corpus exists and the parse is linear. That is the difference between a question that has been open for years and one that has been open for a week.