Algorithms & Data Structures
the bound is a claim, and it is checkable
What is taught wrongly

A constant factor, not a term

The substitution was expected to remove a quantity proportional to the answer. Both traversals hold a quantity proportional to the answer, and what it removes is a factor of 1.6 that shrinks as the collection grows.
19 min read 8 figures Measured, not assumedA limit is not a predictionSpace is the other axisAn index has a size

The document listing’s chain went and the apparatus got 1.93 times smaller. The deferral naming the phrase index’s version called it the largest part of a different apparatus, and the expectation was a saving of the same kind.

It is a factor of 1.6, and it shrinks with the collection.

A constant factor, and not the term the deferral expectedWhat each traversal holds during one query, against how repetitive the collection is. Both lines rise with the copy count, because both are proportional to the ANSWER — and the answer is the copy count, since a phrase of the base occurs once in every copy. So the substitution removes a hash set and a constant factor rather than a term: 20x at 2 copies and 1.58x at 32, which is a factor that shrinks rather than grows. Against a structure of 20,640 bits whose whole claim is being proportional to the phrase count, the query holds 2.0% more that nothing in its own accounting mentions.0100200300400102030copies of the basebits held during one querythe visited set: 420the frontier: 2666-character patterns20x to 1.58x
Fig. 1 What each traversal holds during one query, against how repetitive the collection is. Both rise together.

The measurement

At two copies: the visited set is 20 bits and the frontier is 0. At four: 44 and 11. At eight: 96 and 48. At sixteen: 208 and 130. At thirty-two: 420 and 266.

Ratios: 4.0, 2.0, 1.6, 1.58.

Both lines rise, and the ratio falls. The advantage is largest on the smallest collection and settles at about 1.6.

The two-copy point is worth discarding rather than reading. At two copies the query finds two occurrences, one primary and one secondary, and the frontier’s peak is zero — the single production is inserted and immediately processed. A ratio of four on a query holding twenty bits is not a measurement of anything.

That is a general hazard with a ratio whose denominator can be small: the first point of a sweep is often the least informative and the most extreme. The sweep is drawn from two copies because starting at eight would hide the trend, and the leftmost point is context rather than data.

The three points that matter are 2.0, 1.6 and 1.58, and they are converging.

Why both rise

The visited set holds every occurrence found, so it is the answer.

The frontier holds every occurrence known and unprocessed at once. On these collections a pattern’s occurrences are spread one per copy, and each one produces the next as the cursor advances — but the productions run ahead of the cursor rather than immediately behind it, so the frontier accumulates.

How far ahead they run is a property of the parse’s shape: copiesOf builds each copy from the whole preceding text, so a phrase in copy k may point anywhere in copies 1 through k − 1, and an occurrence in copy 1 produces several at once.

That fan-out is why the frontier is a constant fraction of the answer rather than a bounded number.

A constant factor, and not the term the deferral expectedWhat each traversal holds during one query, against how repetitive the collection is. Both lines rise with the copy count, because both are proportional to the ANSWER — and the answer is the copy count, since a phrase of the base occurs once in every copy. So the substitution removes a hash set and a constant factor rather than a term: 2.50x at 2 copies and 1.42x at 32, which is a factor that shrinks rather than grows. Against a structure of 17,040 bits whose whole claim is being proportional to the phrase count, the query holds 7.5% more that nothing in its own accounting mentions.05001e+3102030copies of the basebits held during one querythe visited set: 1,274the frontier: 8966-character patterns2.50x to 1.42x
Fig. 2 The same measurement on a corpus built to repeat, where the phrases are longer and the propagation’s shape differs.

The convergence toward 1.6 rather than toward 1.0 is worth explaining, because a frontier that was a fixed fraction of the answer would be a coincidence and one that converges is a structure.

At the point where the cursor is halfway through the answer, the occurrences behind it have been processed and their productions are ahead. On a collection where each occurrence produces about one, the productions ahead are about as many as the occurrences behind — so the frontier is about half the answer, and the ratio is about two.

The measured 1.6 is a little under that because the frontier’s peak is not at the midpoint: it is somewhat earlier, where productions have accumulated and the cursor has not caught up.

So the constant is a property of the propagation’s fan-out and the parse’s displacement distribution, and there is no reason for it to be 1.0 or to fall further.

What the deferral expected

The listing’s chain was an array of n⌈log₂ n⌉ bits held at rest. Removing it removed a term from the structure’s size.

The propagation’s visited set is occ positions held during a query. Removing it removes nothing from any size the structure reports.

So the two substitutions have the same mechanism — an ordering makes a bookkeeping structure unnecessary — and completely different currencies. Every copy points right is the mechanism and this is the accounting.

The deferral’s error was in the noun. “The largest part of a different apparatus” describes something at rest; what was found is something during a query; and the phrase index’s actually-largest part is elsewhere. Half an index is three permutations measures the boundary orders at 45.3% of the structure, which is where a size result in this family has to come from.

The two substitutions also differ in how the removed structure was replaced, which is worth noting because the listing’s replacement had a trap and this one does not.

The listing’s chain was replaced by a bitmap — one bit per document, holding the answer so far. That bitmap has to be cleared between queries, and clearing it by walking it costs d per query, which on two thousand documents answering a query whose answer is three is worse than the array it replaced. A document already in the answer is where that trap is written out.

So the listing traded an array for a smaller structure with a subtle cost. The sweep trades a set for nothing — the sorted list it walks is the list of occurrences it was going to hold anyway, and the cursor is an integer.

That is a cleaner substitution and it is a consequence of the currency. Removing something at rest requires putting something in its place; removing query state can leave a hole.

What a query holds that nothing reports

The measurement’s more useful half is not the ratio but the existence of the quantity.

At thirty-two copies over twelve thousand characters, the index is 20,640 bits. The visited set is 420 — two per cent, held during a query.

That two per cent is proportional to the answer and the index is proportional to the phrase count, and there is no relationship between them. A pattern occurring a thousand times on a collection whose parse has three hundred phrases would hold fourteen thousand bits of visited set against an index of about ten thousand.

So a structure whose whole claim is being proportional to z has a query holding something proportional to occ, and its own accounting says nothing about it.

That is not specific to the visited set. Any method reporting occ occurrences holds occ of something somewhere, and the honest version of the claim is that the structure is proportional to z rather than the system.

The same occurrences, and the two things one traversal has to remember8 patterns of 6 characters on a collection of 8 near-copies, 3,072 characters, 205 phrases. Each row is one query: the occurrences found, the visited set the published queue holds, and the largest frontier the sweep holds. The two traversals examine exactly the same 17,715 phrases and report exactly the same occurrences — that is the check, and a difference would be a wrong answer rather than a slower one. What differs is the bookkeeping: the queue keeps every occurrence found so far in a set, and the sweep keeps one ordered list and a cursor."t than"8 found · set 8 · frontier 4"of her"7 found · set 7 · frontier 4" that "16 found · set 16 · frontier 11" every"31 found · set 31 · frontier 19"the ev"8 found · set 8 · frontier 4"o of c"8 found · set 8 · frontier 5" than "15 found · set 15 · frontier 9"ime ra"7 found · set 7 · frontier 4the visited set, pale; the sweep's frontier, dark17,715 phrases examined either way1.67x on what is held
Fig. 3 The same comparison per query rather than per collection: the occurrences found, the set held, and the frontier held.

The gap this names

Every structure in this collection reports a size in parts, checked, and none reports a query working set.

For most of them that is right, because the working set is a few registers: a backward search holds an interval, a locate holds a row and a counter, a rank walk holds a position.

Two structures in this slate break it. The document listing’s chainless variant holds d bits — one per document — and this propagation holds occ positions.

Neither appears in any accounting, and both are proportional to something about the query.

The obvious repair is a working-set column beside the size, and it would be a change to every structure here. What this strand does instead is name it, which is the smaller thing and is what a strand that found the gap rather than set out to fix it can honestly do.

What would make it a term

Since the substitution is a constant here, it is worth saying what collection would make it more — because the answer says the 1.6 is a measurement of a construction rather than of a method.

The ratio is (occurrences found) over (peak pending). It is large when the propagation is deep and narrow and small when it is shallow and wide.

Deep and narrow: a chain of versions where each revision copies the previous one, so a pattern’s occurrence in revision k produces exactly one in revision k + 1. The frontier is one and the ratio is the revision count.

Shallow and wide: a base copied d times in parallel, where every copy points at the base. One occurrence produces d − 1 at once, the frontier is d − 1, and the ratio is about one.

The collections here are the second shape, because each copy is built from the whole preceding text rather than from its immediate predecessor.

A versioned archive is plausibly the first shape, and on one the substitution would be worth a factor rather than a constant. That is not measured, and saying so is more useful than extrapolating.

The retraction, stated

Three sentences.

The substitution works. The visited set can be removed and the sweep reports the same occurrences on every query tested — seventy-two comparisons, fourteen hundred and seventy-one occurrences.

It is worth a constant factor of about 1.6 on query working memory, on the collections this strand measures, and the factor falls as the collection grows.

And it is not a size result. Nothing the index reports changes, and the deferral describing it as the largest part of an apparatus was describing something else.

Almost half the phrase index is three permutations of its boundariesWhere a 226-phrase index over 4,096 characters keeps its bits. The parse itself — a length, a source and a literal per phrase — is 6,554. The boundary orders are 5,424, or 45.3% of the whole structure, and they are three permutations of 226 elements at 1,808 bits each: the boundaries in suffix order, the boundaries in reverse-prefix order, and the INVERSE of the second. Nothing in the index needs the second and third at once — the search walks a range in one and tests membership in the other — so the third is a time-for-space choice worth 15.1% of the structure that has never been priced here. The published alternative is a shortcut representation answering both directions from one array.phrase lengths2,71222.6%phrase sources2,71222.6%phrase literals1,1309.4%boundary orders5,42445.3%three permutations of 226 elements: 1,808 bits each, and one is the inverse of another226 phrases · 4,096 characters45.3% in the orders
Fig. 4 Where the phrase index’s bits actually are: nearly half of it is three permutations of its phrase boundaries.
The other half of the propagation, which the order does not touchFinding which phrases' source regions contain a position, two ways, over 40 positions of a 6,144-character collection with 238 phrases. The index does it by walking every phrase whose source is at or before the position: 207.0 phrases examined a probe. Sorting the intervals by source and keeping a running maximum of their right ends lets a leftward walk stop for good the first time the maximum falls short: 10.9, a factor of 19x, for 21.6% more bits. The two agree at every position. This is deliberately not on the same plate as the sweep: they are two independent changes to one method, and reporting them together would report one saving as two.phrases examined per probethe linear scan207.0sorted, with a running maximum10.9 — 19xthe running maximum costs 2,821 bits — 21.6% of the index40 of 40 positions checked, and the two agree at all of them238 phrases · 6,144 characters19x on the scan
Fig. 5 The quantity that dominates the propagation and which this substitution does not touch: phrases examined per probe, two ways.

The three savings this strand has, ranked

Putting the strand’s results in order of size makes the shape of it clear, and the order is not the order they were expected in.

The scan: a factor of nineteen, on phrases examined per probe — a hundred and seventy against eleven, for twenty-two per cent more bits. That is the strand’s real result on cost.

The boundary orders: 45.3% of the index, of which one of three permutations is the inverse of another and is a time-for-space choice never priced here. That is the strand’s real result on size, and it is a diagnosis rather than a change.

The visited set: a factor of 1.6 on query working memory — the quantity the same occurrences, less bookkeeping measures per query. That is the deferral’s own subject, and it is the smallest of the three.

A deferral naming the third and the strand producing the first two is the ordinary outcome of building something: the sentence that names the work is written from outside it, and what is found is what the building exposes.

Why it is still worth taking

A constant factor of 1.6 on a quantity nobody accounts for is a small result, and there are two reasons the substitution belongs in the structure anyway.

It removes a hash set from an inner loop. A set has a load factor, an allocation and a scattered access pattern; a sorted array and a cursor have none of those. That difference is not visible to an instrument charging bits, and it is the difference a profiler would see.

And it makes a property checkable. The sweep’s guard asserts, at every production, that a copy lies to the right of its source. That is a fact about the parse which was previously implicit, and a parse losing it would now fail loudly rather than returning short answers.

From the right, two of sixteen is what a short answer looks like: 87.5% of the occurrences missing, every one reported genuinely there, and nothing but a comparison against the other traversal able to see it.

The other half of the strand

The substitution above is one of two changes this strand makes to the propagation and it is the smaller.

The other is the scan: finding which phrases’ source regions contain a position, which the index does by walking every phrase with a source at or before it. That is a hundred and seventy per probe on a two-hundred-phrase index, and sorting the intervals with a running maximum of their right ends brings it to eleven.

A factor of nineteen, on the quantity that dominates the propagation’s cost.

The scan the order does not touch is that measurement, and the two are deliberately kept on separate plates: they are independent changes to one method, and reporting them together would report one saving as two.

That separation is also why this essay’s result reads small. It is small — and the strand has a large one, on a different quantity, that the ordering has nothing to do with.

The same sweep, run from the right, finds two of sixteenWhat the order is worth, measured by taking it away. The sweep visits its known occurrences in text order and inserts each one it produces ahead of the cursor; run from the right instead, an occurrence produced to the right of the cursor lands BEHIND it in that order and is never processed. On a collection of 16 copies the correct traversal reports 16 occurrences and the reversed one reports 2 — it loses 14, which is 87.5%. Every occurrence it does report is genuinely there, so the failure is silent: the answer is short and nothing but a comparison against the queue can see it. This is the phrase index's version of a defect the document listing had one strand ago, on a different object and in the same shape.occurrences reportedin text order16from the right2 — 14 lostevery one it reports is real, so the answer is short rather than wrong1 of them were found by the boundary search and never propagated16 copies · 6-character pattern87.5% lost
Fig. 6 The failure the guard prevents: the same sweep run in the wrong order, reporting two occurrences of sixteen with no indication that fourteen are missing.

The check the retraction needed

A result that comes out smaller than expected needs a check as much as one that comes out larger, and this one’s is worth describing because its shape is unusual.

The obvious check is that the sweep holds less than the queue. That passes at every point and says nothing about the magnitude.

The check written requires two things: the sweep never holds more, at any copy count, and the advantage stays inside a band across the sweep — a factor of at most four between its largest and smallest values.

That second clause is the retraction, asserted. A claim that the advantage grows would be a claim the measurement refuses, and a check requiring it to stay bounded is what makes the refusal something the machinery states rather than something the prose reports.

It is a check that would fail if the expectation had been right, which is the correct relationship between a check and a retraction. This collection’s habit is that an assertion which has never rejected anything proves nothing; a check asserting a limitation is the same habit applied to a result that came out small.

Measured: the factors are 4.0, 2.0, 1.6 and 1.58, and their spread is 2.53 — inside the band, and the check holds.

What a working-set column would look like

Since this essay names a gap in the accounting, it is worth sketching what closing it would take — not as a plan but so that the size of the omission is legible.

Every structure here reports bits() returning a total and its parts. A working set would be a second method returning bits held during a query, and it would have an argument: the query, or at least the answer’s size, because most of these quantities are functions of occ or of d.

That argument is the difficulty. A size is a number; a working set is a function, and reporting a function on a plate means choosing a point on it — which is the sampling-rate problem a sixth of what, exactly is about, arriving on a different axis.

The tractable version is to report the working set’s shape: O(1), O(d), O(occ), with the constant. Three of the structures in this slate would report the first, one the second and one the third, and a reader sizing a system would know which queries can blow up.

That is a small enough change to be worth doing and it is not done here. What is done is the naming, and the reason the naming is worth an essay is that the gap was invisible until a substitution’s whole subject turned out to live in it.

Every copy points left, and that is the whole of the substitutionThe first 60 copying phrases of a 1,024-character collection, each drawn as a line from the text it copies to the text it produces. Every line points right, and it must: a greedy self-referential parse chooses a phrase's source from text already produced, so a source is always earlier than the phrase that uses it, by construction rather than by luck. That single fact is what removes the visited set from secondary propagation — an occurrence produced by a phrase lies strictly to the right of the occurrence it was copied from, so a sweep in text order reaches each one exactly once and cannot produce one twice. The parallel to the document listing's chain is exact: there it was left-first and here it is left-to-right, and both times the array being deleted recorded what the traversal order already knew.01,024120 phrases · 1,024 characters60 drawn, every one pointing right
Fig. 7 The property the substitution rests on, whatever it turns out to be worth: every copying phrase points left, so every production lies to the right.

What the shape of the retraction says

This collection’s phases have produced several retractions and this is a mild one, so it is worth placing.

The strongest retractions overturn a conclusion: repetition does not give a listing apparatus anything to do; a separator does not break a run; depth is mostly not generations of copying.

This one overturns a magnitude and a currency while leaving the mechanism intact. The substitution is real, it works, and it is worth a fraction of what a sentence written before it was built implied.

That is the ordinary outcome of building something a deferral named, and it is worth reporting in the same terms as the dramatic ones. A deferral is a guess about what a piece of work will produce, and a guess that names the right mechanism and the wrong size is a good guess that still has to be corrected.

What makes this particular correction worth its essay is the gap it exposed. A deferral describing query state as “part of an apparatus” is a deferral written by somebody thinking about a size, and the reason that confusion was available is that no structure here reports a working set — so there was no place in the accounting for query state to be, and it got filed under the only heading that existed.

A vocabulary with one word for two things is how two things get treated as one, which is a price with no structure under it’s subject on a different pair. The repair there was an operation count; here it would be a second column, and neither is a deep change.

The same occurrences, and the two things one traversal has to remember8 patterns of 6 characters on a collection of 8 near-copies, 3,072 characters, 139 phrases. Each row is one query: the occurrences found, the visited set the published queue holds, and the largest frontier the sweep holds. The two traversals examine exactly the same 28,418 phrases and report exactly the same occurrences — that is the check, and a difference would be a wrong answer rather than a slower one. What differs is the bookkeeping: the queue keeps every occurrence found so far in a set, and the sweep keeps one ordered list and a cursor."t than"22 found · set 22 · frontier 14"of is "22 found · set 22 · frontier 15"until "46 found · set 46 · frontier 31"easure"55 found · set 55 · frontier 38"the ev"23 found · set 23 · frontier 15"red ho"31 found · set 31 · frontier 21"sserte"22 found · set 22 · frontier 14"ss a r"23 found · set 23 · frontier 15the visited set, pale; the sweep's frontier, dark28,418 phrases examined either way1.50x on what is held
Fig. 8 The per-query view on a repetitive corpus, where the two quantities being confused are drawn side by side for eight queries.

Where this goes next

"t than"8 found · set 8 · frontier 4"of her"7 found · set 7 · frontier 4" that "16 found · set 16 · frontier 11" every"31 found · set 31 · frontier 19"the ev"8 found · set 8 · frontier 4"o of c"8 found · set 8 · frontier 5" than "15 found · set 15 · frontier 9"ime ra"7 found · set 7 · frontier 4the visited set, pale; the sweep's frontier, dark17,715 phrases examined either way1.67x on what is held The same occurrences, less bookkeeping Two traversals examine identically many phrases and report identically many occurrences. What differs is that one holds every occurrence found so far in a set and the other holds an ordered list and a cursor. 01,024120 phrases · 1,024 characters60 drawn, every one pointing right Every copy points right A greedy self-referential parse chooses each phrase's source from text already produced, so an occurrence copied from another lies strictly to its right. That one fact removes a visited set from a propagation, exactly as a left-first walk removed an array one strand ago. tree · suffix array2,363,886tree · text656,635tree · document array1,050,616tree · previous-occurrence chain2,363,886tree · range minimum4,727,772succinct · suffix array2,363,886succinct · text656,635succinct · document array1,050,616succinct · previous-occurrence chain2,363,886succinct · range minimum1,483,854chainless · suffix array2,363,886chainless · text656,635chainless · document array1,050,616chainless · range minimum1,483,854chainless · reported bitmap256131,327 characters · 256 documents6 parts What the chain cost The chain of previous occurrences is one row number per row — exactly as wide as the suffix array it sits beside, and the largest single part of a document-listing apparatus. It is now absent, and what replaces it is one bit per document.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

What links here

Every essay whose body links to this one.

The objects this essay names

Each one links to every other essay that touches it.

Index sizePhrase indexPropagationSecondary occurrenceSpace accountingVisited setWorking memory