The scan the order does not touch

The propagation has two halves and the ordering substitution touches one of them.

Which occurrences to process, and in what order. That is the sweep, and it removes a visited set for a factor of 1.6 on query working memory.

Which phrases contain a given position. That is a scan over the parse, and it is where the work is.

What the index does today #

For each known occurrence at position p, walk the phrases in source order and stop when a source exceeds p. For each one reached, check whether its source region reaches past p + m; if so, produce a copy.

That walk is over every phrase whose source is at or before p, which at the right-hand end of the text is every phrase in the parse.

Measured: 207.0 phrases examined per probe, on a collection of two hundred and thirty-eight phrases.

So the scan is essentially the whole parse, once per occurrence, and on a query with thirty occurrences that is six thousand phrase examinations against an index holding two hundred and thirty-eight phrases.

That the scan is the dominant cost is worth putting in proportion, because the strand’s other change is on a quantity two orders of magnitude smaller.

Per query on this collection, the propagation examines about seventeen hundred phrases and holds between four and thirty-one positions.

Seventeen hundred against thirty-one. So a change to the phrase examinations is worth roughly fifty times a change of the same proportion to the bookkeeping — and the two changes available are a factor of nineteen on the first and a factor of 1.6 on the second.

A constant factor, not a term is the essay about the smaller one, and its honest conclusion is that the strand’s real result on cost is here.

The structure #

Sort the phrases by source — which the index already does — and keep, alongside them, a running maximum of their source regions’ right ends.

Then to find the phrases whose source region contains [p, p + m):

Binary search for the last source at or before p. Walk left from there. At each step, if the running maximum is below p + m, stop — nothing further left reaches far enough right, because the maximum is a maximum over everything to the left.

Otherwise check this phrase’s own right end and report it if it reaches.

Measured: 10.9 phrases examined per probe, including the binary search’s eight steps.

A factor of 19.0.

Why the running maximum works #

The walk is leftward through phrases sorted by source, so at every step the sources are getting smaller and the phrases are getting less likely to reach p + m.

Without a maximum, “less likely” is not “impossible”: a phrase far to the left could be very long and reach past p.

The running maximum makes it decidable. maxEnd[i] is the largest right end among phrases 0 through i, so if maxEnd[i] < p + m then no phrase at or below i reaches, and the walk can stop for good rather than continuing to check.

That is a standard interval-stabbing structure and it is the cheapest possible one: one extra array, monotone, built in one pass.

What it costs #

The running maximum is one value per phrase with a source, at ⌈log₂ n⌉ bits: 2,821 bits on a collection whose index is 13,090.

Twenty-two per cent more bits for a factor of nineteen on the propagation’s dominant cost.

That is a favourable trade and it is worth stating with the denominator, because twenty-two per cent of a phrase index is a real amount. An index with z in its size is where the index’s own parts are set out, and the addition is comparable to one of its three boundary orders.

The eight steps of binary search are worth accounting for separately, because on a small parse they are most of what the structure costs.

At two hundred and thirty-eight phrases, ⌈log₂ 238⌉ is eight, and the measured total is 10.9 — so the search is eight and the walk is 2.9.

That means the structure’s cost here is dominated by finding where to start rather than by walking. On a larger parse the search grows logarithmically and the walk does not, so the ratio shifts further toward the search.

Which has a consequence worth naming: on a very large parse the structure’s cost is essentially log z, and the running maximum’s contribution to the saving falls away. The whole win becomes the binary search, and the running maximum is what makes the walk after it bounded rather than what makes the method fast.

Why this is on a different plate from the sweep #

The sweep and the scan are two independent changes to one method, and reporting them together would report one saving as two.

The sweep changes which occurrences are processed in what order, and removes a visited set. Factor of 1.6 on working memory, no change to phrases examined.

The scan changes how the phrases containing a position are found, and removes a linear walk. Factor of nineteen on phrases examined, no change to working memory.

They compose trivially, because they act on different quantities, and a plate showing both would be showing two lines that have nothing to do with each other.

That separation is a convention this strand adopted deliberately: the scan and the sweep are never on one plate as one saving. It is the same discipline two factors that do not multiply exists for, applied before rather than after the confusion.

The two methods must agree #

The check is that the scan and the structure find the same phrases at every position, and it is an exact set comparison rather than a count.

Forty probes across a six-thousand-character collection with two hundred and thirty-eight phrases. Every probe agrees.

A count comparison would pass on a structure that found a different set of the same size, which for an interval-stabbing query is a plausible failure: an off-by-one in the running maximum’s comparison would drop the phrases that reach exactly to p + m, which is a set of the same shape and a different membership.

So the check is on the sorted phrase identifiers, and it is the primary one — the operation counts are secondary, because a faster method finding a different set is not a faster method.

Where the structure does not help #

The running maximum lets a walk stop early, and how early depends on the intervals’ lengths.

On a collection whose phrases are short, the maximum falls below p quickly and the walk stops after a few steps. That is the case measured: 10.9 examinations against a possible 207.

On a collection whose phrases are long — a highly repetitive text where a phrase copies hundreds of characters — the maximum stays high for most of the array and the walk goes nearly all the way. The structure then costs its bits and saves little.

So this is a two-ended result and the unfavourable end is the collection the whole family is built for. That is worth stating plainly: the more repetitive the collection, the less the running maximum helps, because long phrases are exactly what a repetitive collection has.

Whether it flips to a loss is a question of where the crossing is, and this strand does not sweep it. What can be said is that the bits are 22% and the saving is 19× on ordinary prose copies, so there is a wide margin before the trade goes bad.

The picture is also a picture of what decides the structure’s value. Each line’s length is a phrase’s length, which is the interval the running maximum is a maximum over — so a plate full of long lines is a collection where the maximum stays high and the walk goes far.

On these four copies the lines are mostly short with a few long ones, which is the favourable case: the long ones raise the maximum in a few places and most of the array is below it.

A collection of two copies of a large base would be the unfavourable case — one enormous phrase, whose right end dominates the maximum everywhere to its right, so no walk can stop before reaching it.

That is a real shape and it is the shape a mirror or a backup produces. So the structure’s value depends on the parse’s length distribution rather than on its size, which is a property nothing in this collection’s corpus descriptions records.

The published alternative #

The literature’s answer to this question is a two-dimensional range structure over a z × z grid, and it is worth saying why this collection built the cheap thing instead.

The propagation is a stabbing query: which intervals contain this point. The published indexes answer it with a range structure, which also answers the primary-occurrence intersection — which boundaries have the left half ending here and the right half starting there — so one structure serves both.

This collection’s phrase index does both by filtering the smaller range, and reports the points examined rather than assuming a grid away. An index with z in its size records that decision and its reason: the sizes reported are the sizes of what is stored, and the grid’s own o(z log z) is not claimed.

The running maximum is a third option — cheaper than a grid, more expensive than nothing, and answering only one of the two questions. Its place in the accounting is that it is a measured structure with a measured cost, which a grid whose overhead is asserted is not.

The structure that would answer both questions #

Since the published answer is a grid serving two purposes and this is a cheap structure serving one, it is worth asking what the other purpose costs separately.

The primary occurrence search intersects two ranges: the phrase boundaries whose following text starts with the pattern’s right half, and those whose preceding text ends with its left half. That is a two-dimensional dominance query and it is genuinely what a grid is for.

This collection’s index answers it by filtering the smaller of the two ranges against the other’s rank window, and reports the points examined rather than assuming the grid away. The measured points are on the plate of the occurrences that cross a boundary, and they are the number a grid would reduce.

So the family has two range questions, one answered by filtering and one by a running maximum, with a grid available that would answer both at a cost this collection does not know how to measure honestly — because a grid’s o(z log z) is an asymptotic claim about a structure with several published variants.

Building one and measuring it is the obvious next thing and it is not this strand’s. What this strand establishes is that the second question is cheap to answer well without one, which narrows what a grid would have to justify.

Whether the bits are worth it #

A structure costing 22% of an index to make one query nineteen times cheaper is not obviously a good trade, and the answer depends on what the index is for.

A phrase index’s whole claim is being proportional to z, which on a repetitive collection is much smaller than the text. Adding 22% to it is giving back part of that claim.

Its query cost is already the family’s weak point: a character is produced by following a copy chain whose depth is a property of the parse and is bounded by nothing, and a propagation examines phrases per occurrence. The character that costs a chain is where the first of those was measured.

So the family is small and slow, and a change trading 22% of the size for 19× on one query cost is trading in the direction the family needs.

The counter-argument is that a reader who wants speed should not be using this family — the entropy-bounded index is faster at everything and larger, and the collection decides which index is small is where the crossing is. A structure whose selling point is size should be reluctant to spend it.

Both readings are defensible and the measurement does not settle them, which is the honest state. What the measurement supplies is the exchange rate: 22% of the bits for 19× on the propagation, and a reader with a workload can decide.

What the scan’s cost is proportional to #

Worth stating because it is the quantity the structure changes.

The linear scan examines every phrase whose source is at or before p, which is z·(p/n) on average over uniformly distributed positions — so about z/2 per probe, and z at the right-hand end.

The structure examines log z for the binary search plus however many steps the running maximum permits, which is a property of the interval lengths and is small when phrases are short.

So the scan is linear in the parse and the structure is logarithmic plus a data-dependent walk. On a two-hundred-phrase index that is 100 against 11; on a two-thousand-phrase index it would be 1,000 against about 14.

The factor therefore grows with the collection, which is the direction that matters: a bigger parse makes the linear scan worse and the structure barely worse at all.

Twenty-two per cent, against what #

The bits the running maximum costs deserve the same treatment every share in this slate has had, because 22% is a share of something and the something matters.

The index is 13,090 bits: phrase lengths 2,712, sources 2,712, literals 1,130, boundary orders 5,424. The running maximum is 2,821 — one value per copying phrase at ⌈log₂ n⌉ bits.

So it is 22% of the whole index and roughly the size of the phrase sources array, which is one of the four parts. It is half of one boundary order.

Against the parse — lengths, sources and literals, without the orders — it is 38%. Against the orders alone it is 52%.

Four denominators, four numbers between 22% and 52%, one structure. A sixth of what, exactly is this collection’s essay on exactly that, and the convention it settled is the one used here: the share is of the whole index, and the parts are listed so a reader can compute the others.

The reason to prefer the whole index as the denominator is that it is what a system pays. The reason to list the parts is that a reader comparing against a different implementation — one without three boundary orders, say — needs to reconstruct the number against their own base.

What this leaves #

The propagation, after both changes: occurrences visited in text order with a cursor and no visited set, and each one’s containing phrases found by a binary search and a bounded leftward walk.

Two independent changes, one to the traversal and one to the lookup, on two plates, with two separate checks.

And the index’s largest part untouched: half an index is three permutations is where the boundary orders are measured at 45.3% of the structure, which is the size result this family has available and which neither of these changes approaches.

The three results together make an odd shape for a strand. Its deferral asked for an ordering substitution and got one worth 1.6 on a quantity nothing reports. Building it exposed a scan worth nineteen for 22% of the bits. And measuring the index to price that 22% exposed that nearly half of it is three permutations, one of which is derivable from another.

None of the three is what the strand set out to find, and the second and third are larger than the first. That is the ordinary yield of building something a deferral names: the deferral describes what somebody could see from outside, and what is found is what the building makes visible.