The structure paid for before the first query

Every structure in this field is bought before it is used. A search that is proportional to its answer instead of to a range is worth having, and the price is paid at construction time by everyone, including the reader who never searches at all.

The bill #

On a collection of thirty-two copies of five hundred and twelve characters — sixteen thousand characters, $z = 156$ phrases:

• the phrase table (lengths, sources, literals): 5,148 bits
• the three orderings of the boundaries: 3,744 bits
• the intersection grid: 1,696 bits
• the propagation grid: 1,544 bits

Total 12,132 bits, of which the two grids are 3,240 — 26.7%. They answer nothing: no occurrence, no character, no count. What they do is convert a search proportional to $z$ per occurrence into a search proportional to $\log z$ per occurrence, which is the previous essay’s subject and is worth 1.76 times at this size.

Twenty-seven per cent of a structure for 1.76 times on a query is not obviously a good trade, and saying so is the point of this essay. A structure whose query cost is quoted and whose size is not has had the easier half of its case made for it, and this field’s literature quotes the query cost in every abstract. The trade gets better as the collection grows, in both columns and at different rates, and the shape of that is the only honest way to decide.

Where the bits go, exactly #

A permutation grid over $z$ points at $L = \lceil\log_2 z\rceil$ levels is $zL$ bits of payload. At $z = 156$ and $L = 8$ that is 1,248 bits for the intersection grid, and the file reports 1,696 — so 448 bits, 36% on top, are the rank directory.

That directory is the $o(z \log z)$ in the published bound, and it is not small here. Both grids together are 2,344 bits of payload and 896 of directory: the lower-order term is 38% of the leading one, at the size a plate can draw.

The directory is a two-level structure over each level’s bit vector: an absolute counter every 512 bits and a relative one every 64. Its size is $\lceil z/512\rceil\lceil\log_2 z\rceil + \lceil z/64\rceil \cdot 9$ bits per level, which falls as a share when $z$ grows and does not vanish. This collection has measured the same arithmetic twice before, under what is still proportional to n and in the index that is smaller than the text, and the lesson is the same each time: a term written $o(\cdot)$ is a term whose constant was not worth writing down, not a term that is small.

The saving is a number in two currencies #

Before any of that can be netted off, the thing the grid is bought for has to be priced, and it prices very differently depending on which count is used.

The larger of those two numbers is the one that gets quoted, and it is the one the bits are not being spent on.

The grid replaces something, which nobody credits #

The marginal cost of the intersection grid is not 1,696 bits. It is 1,696 minus what the grid makes unnecessary.

The filtering policy needs rankInPrefix — an array taking a boundary to its rank in the prefix order — because that is what it reads for each candidate. The grid does not: it holds the same relation, in a form that supports a query the array cannot answer. So one of the three stored orderings, 1,248 bits of the 3,744, is dead once the grid is there.

The honest marginal cost is therefore 448 bits, or about a third of one ordering. That is a very different number from 1,696, and it changes the trade from “a quarter more structure for a factor of two” into “three per cent more structure for a factor of two”, which is a trade anybody would take.

Neither number is wrong. The first is what the two grids cost; the second is what adding them costs a structure that then drops what they replace. The plate carries the first because it is what is built, and this section carries the second because it is what a reader deciding should use.

How the share moves as the collection grows #

This is the column that decides, and it moves the right way.

The phrase table is $z(2\lceil\log_2 n\rceil + \lceil\log_2\sigma\rceil)$ bits — it grows with the text through the $\log n$ term, even when $z$ does not. The grids are $zL$ bits, which depend on $z$ alone. So on a collection that grows by repeating, the index grows slowly and the grids do not grow at all.

Measured across the sweep: 30.7%, 29.8%, 28.9%, 28.2%, 27.4%, 26.7% of the structure at one, two, four, eight, sixteen and thirty-two copies. Drifting steadily down — because $\log_2 n$ climbs from 10 to 14 across the sweep while $\log_2 z$ stays at 8, so the index grows and the grids do not.

On a collection whose phrase count grows — near-copies rather than copies, or unrelated documents — the grids grow with $z\log z$ and the index with $z\log n$, so the share is decided by $\log z$ against $\log n$ and the grids stay under a half. There is no regime in which they dominate, which is worth stating because a reader who has met a range structure whose cost was $O(z\log^2 z)$ would reasonably expect one.

The propagation grid’s point set is not a permutation of the same thing #

A detail that decides the second grid’s size and is easy to skip.

The intersection grid’s two coordinates are ranks of the same $z$ boundaries in two total orders, so it holds $z$ points. The propagation grid’s points are the copying phrases only — the literals copy from nowhere and cannot contain an occurrence — so it holds fewer. On this collection 137 of the 156 phrases copy, and 19 are literals, which is why the second grid is 1,544 bits against the first’s 1,696.

That nineteen is not noise. It is the alphabet-sized floor under $z$ that the phrases a text copies from itself measures: a text over $\sigma$ symbols has at least $\sigma$ literal phrases, one per symbol, whatever else it does. On a very repetitive collection most of what a phrase index stores is that floor, and the propagation grid is the one structure here that does not pay for it.

Both grids, and whether a reader needs both #

They answer different questions and a reader may want only one.

The intersection grid accelerates the crossing search, which on this collection examines three candidates. Removing three candidates is worth nothing at all, and on a pattern whose halves are common it is worth a great deal — the previous essays’ plate over pattern lengths is the measurement, and it is a property of the pattern rather than of the collection.

The propagation grid accelerates the part that costs 4,352 of the 4,355 candidates. On a repetitive collection it is the whole of the saving.

So on the collection here the right structure is the propagation grid alone: 1,544 bits, 14% of the index, and essentially all of the query saving. The intersection grid earns its 1,696 on short patterns, small alphabets and collections where crossing occurrences are common, and it earns nothing on this one.

That is why the sizes are reported as parts and not as a total. A total answers “what does the accelerated index cost”, and the question a reader actually has is which of the two structures is needed, which a total cannot be asked.

The arithmetic at a size no plate here can draw #

Every number above is measured at $z = 156$, and the trade it describes is decided by quantities that move with $z$. Both sides of it can be written down, which is worth doing because the conclusion at the measured size and the conclusion at a realistic one are different.

The space ratio is $zL$ over $z(2\lceil\log_2 n\rceil + \lceil\log_2 \sigma\rceil)$ — grid over phrase table — which is $\log_2 z$ over about $2\log_2 n$. On a repetitive collection $z$ is far below $n$, so the ratio is well under a half and falls as the collection grows.

The query ratio is the range over the logarithm: the filter walks something proportional to $z$ per occurrence and the grid descends $\log_2 z$ levels. At $z = 156$ that is 156 against 8 before constants, and after constants it was measured at 1.76. At $z$ a million it is a million against twenty.

So the space side is roughly constant in $z$ and the query side grows like $z/\log z$. There is no size at which building the grid gets worse and there are sizes at which it is the difference between a search and a scan. The measured 1.76 is not the trade; it is the trade evaluated at the smallest size that can be drawn, which is a limit is not a prediction read the other way — the asymptotics are right here and the constant is what a plate can show.

The two ladders here pull against each other #

There is a second structure in the essays beside these whose whole purpose is to make $z$ larger, and it is worth putting the two together because a reader building both pays twice.

A parse that will not follow a long chain caps the copy depth, which is what the character that costs a chain charges for reading a character. It buys a shallow chain with phrases: a cap of eight on this collection takes $z$ from 156 to 170, and a cap of four takes it to 946.

Every one of those extra phrases is another point in both grids. At $z = 946$ the grids are $946 \times 10$ bits of payload each rather than $156 \times 8$ — a factor of about seven and a half — while the index they sit on grows by the same factor. The share does not move much; the absolute cost does.

That is not an argument against either structure. It is the observation that the two questions these essays answer about one index have opposite signs in the same variable, and a plate showing either alone is drawn under an assumption about the other. The frontier at the end of the bounded-parse ladder is the picture that has both.

What it would cost to answer the question by storing the answer #

The alternative nobody builds, offered for scale.

The search’s real question is “for each split point, which boundaries have this left half and this right half”. A structure answering it by storing the answers would be a table indexed by pattern, which is a table over every substring of the collection — larger than the text by orders of magnitude and the thing an index larger than what it indexes is about.

The other extreme is to store nothing and scan the text, which is $n$ per query rather than $z$. The filtering policy is between the two, at $z$ per occurrence; the grid is at $\log z$. So the four options span the whole range from a table too big to build to a scan too slow to run, and the two in the middle differ by exactly the structure this essay prices.

That is the frame the frontier between time and space sets up for sorting, arriving in a compressed index: the interesting structures are never the endpoints, and the question is always which point on the curve the collection sits at.

The published bound, and what is not claimed #

The structures the literature builds for this are $z\log z(1 + o(1))$ bits with $O((t+1)\log z)$ query time, and some of them do better on the constant with a compressed representation of the bit vectors.

Nothing here claims that bound. What is reported is what these bit vectors and these directories cost, measured the way every other size on this site is measured, which is the same accounting the index that stores the runs and an index with z in its size use for the structures they build. The payload happens to be exactly $z\lceil\log_2 z\rceil$; the rest is a directory whose parameters somebody typed.

The gap between “what the bound says” and “what this costs” is the directory, and it is 38%. A compressed bit vector would shrink the payload on a grid whose permutation has structure and would leave the directory where it is — which is the finding the transform that emits nothing reaches from the other direction, that a compressed representation is compressed only where the thing inside it has runs.

What a size like this is usually reported as, and why that is worse #

Two conventions are common and both would have hidden something measured above.

A ratio to the text. “The index is 0.74 bits per character” is the form most papers in this field use, and on a repetitive collection it is a statement about how many copies were concatenated rather than about the structure. The whole point of a structure proportional to $z$ is that its size stops moving while the text grows, so bits per character falls by a factor of thirty-two across this sweep and reports a structure that never changed.

A single total. “The accelerated index is 12,132 bits” answers a question nobody has. A reader wants to know whether to build the second grid, and a total is the one shape of report that cannot say.

The convention this collection uses instead is parts, in bits, with the collection’s size stated beside them — the same one measuring what an algorithm keeps sets up for auxiliary space and what a window costs in bits for a streaming summary. It is more numbers and it is the only form in which the question of which structure is needed can be answered.

The marginal number is quoted for the wrong grid #

The marginal accounting is done once, for the intersection grid, and the recommendation two sections later is to build the other one. Applying the same subtraction to the structure a reader is actually being told to build changes the closing figure by more than the argument that produced it.

The propagation grid holds the by-source relation, which is exactly what the third stored ordering holds — so if the reasoning that kills one ordering when the intersection grid arrives holds by symmetry, the same 1,248 bits go when the propagation grid does. That gives:

• both grids — 3,240 gross, two orderings dead, 744 marginal, 8.4% of the index;
• intersection only — 1,696 gross, 448 marginal, 5.0%;
• propagation only — 1,544 gross, 296 marginal, 3.3%.

So the recommended structure — the propagation grid alone, which carries 4,352 of the 4,355 candidates and therefore essentially the whole saving — costs 296 bits on an 8,892-bit index. Not twenty-seven per cent, not three per cent for a quarter of the saving: three per cent for all of it.

That is a materially different sentence from the one this page opens with, and both are true of the same measurement. Twenty-seven per cent is what is built; 8.4% is what building both costs a structure that then drops what they replace; 3.3% is what the useful half costs. A reader deciding needs the third, and the page hands them the second, computed for the half it goes on to say is worthless here.

The general form is worth keeping, because it is a trap this collection’s own accounting convention sets. Reporting a size as parts makes a marginal analysis possible and does not make it consistent: the subtraction has to be redone for every configuration the parts allow, and there are three here. A single marginal number attached to a parts table reads as though it applied to the table, and it applies to one row of it.

Which sharpens the case rather than weakening it. At 3.3% the trade the operations a candidate count leaves out prices at 1.76 times on this collection is not a close decision at any size, and the arithmetic two sections up says the query side grows like $z/\log z$ while the space side stays flat. The structure was always worth building; the number that says so is a tenth of the one on the plate, and it took the same subtraction the page already performs, done once more.

What is being claimed #

The two grids are 3,240 bits against an index of 8,892, twenty-seven per cent of the structure, before any query.

Their payload is exactly $z\lceil\log_2 z\rceil$ and their directory is 38% on top of it. The lower-order term of the published bound is measured here rather than dropped.

The marginal cost is 448 bits, not 1,696, because the grid replaces one of the three stored orderings — and a reader deciding should use the marginal number while a reader counting what is built should use the other.

The share is flat as the collection repeats and falls slowly, because the index carries a $\log n$ the grids do not.

And a reader on this collection wants one of the two grids, the propagation one, which is 14% of the index and essentially all of the saving. Which of the two earns its bits is a property of the collection and the pattern rather than of the structures, so the answer for a different corpus is a different measurement and not a different reading of this one.