A test that is the top of the search

A count that names every point asked whether the grid inside a phrase index could be smaller if it only had to count. The grid is a wavelet tree over a permutation of 3,612 points, one for each phrase boundary of a repetitive text, placed by the boundary’s rank among reversed prefixes and among suffixes. A search for a pattern splits it at every position, looks up the prefix’s range in one order and the suffix’s in the other, and asks the grid what lies in the rectangle the two ranges make. That essay found that an exact counter pays the same floor as a structure that reports points, $\log_2(3612!) = 37{,}485$ bits, the floor a bit for every bit set, because count questions alone decode the permutation. An approximate counter can go under the floor, and the grid cut to eight of its twelve levels counted the index’s own rectangles badly, 46% of them right.

It did one thing well. An empty rectangle came back empty 96% of the time. The closing section noticed that a phrase index answering does this pattern occur? needs exactly that, split by split, and can stop at the first split that says yes. It proposed the cheapest existence test the grid itself offers: stop the descent at depth $d$ and answer possibly yes whenever a node the rectangle reaches at that depth holds a point of the column range. It predicted that at six levels, half the grid, the test would turn away nine in ten empty splits and never an occupied one.

The second half of the prediction is true by construction. The first half is not, and the reason it fails is the more useful finding: the splits a test can turn away cheaply are the splits an existence query was never going to spend much on.

Three answers from a descent that stops #

A wavelet tree answers a rectangle by descending from the root. Each node covers a range of heights and holds the points of the column range whose heights fall in it. A node holding no points, or whose range of heights misses the rectangle, is abandoned. A node whose range of heights lies wholly inside the rectangle and holds a point is a certain yes, since every point under it is inside. Every other node is split in two and the descent continues. At the twelfth level each node is a single height, so every node is either inside or outside and the search is exact.

Stopped at depth $d$, the descent can end in three ways. It finds a node wholly inside the rectangle holding a point, and answers yes with certainty. It reaches depth $d$ with a node that overlaps the rectangle only in part and holds a point, and answers maybe, since the point may lie in the overlapped part or not. Or every node is abandoned, and it answers no, which is certain too, because a point inside the rectangle would have kept some node alive at every level. The test is a prefix of the search, stored exactly as the full grid stores them, since the level where compression stops paying found that coding each level its own way saves 26 bits of 47,668: its first $d$ levels, the 4,300 bits each that the structure paid for before the first query priced with their rank directories, and nothing else.

Two sets of patterns are asked, 300 of each, half of eight characters and half of sixteen. The first are substrings of the text, which occur. The second are the same kind of substring with one character replaced by another from the text’s alphabet, kept only if the text does not contain the result. Every split of a pattern that leaves a non-empty prefix range and a non-empty suffix range is a rectangle, as in the earlier essay: 2,275 of them in all, 1,787 holding a point and 488 empty.

Three quarters at half the grid #

Stopped at six of its twelve levels, 25,800 bits, the grid turns away 75% of the empty splits, not the nine in ten predicted. Nine in ten takes ten levels, 43,000 bits, which is above the floor of 37,485 that an exact structure pays. Below the floor the test reaches 85% at eight levels and no further. No occupied split is turned away at any depth, which is the part of the prediction that could not fail.

The other curve on the plate is the one the prediction did not mention. At six levels only 9% of occupied splits are answered yes outright; the other 91% are maybe. A rectangle the index asks averages 27.6 rows, and at six levels a node covers about 56 heights, so a rectangle is usually smaller than one node at the stopping depth. A node wholly inside such a rectangle exists only deeper down. The test can rule things out long before it can rule anything in, and the asymmetry is the same one the cut counter showed: an empty rectangle comes back empty easily, an occupied one is a guess.

The arithmetic behind the 75% is that of the earlier essay’s error plate turned into a yes-or-no question. An empty split is turned away only when no point of its column range lies in any node it touches at depth $d$. Turning away fails when a point lies in a node the rectangle overlaps in part, and whether that happens depends on how close the rectangle sits to points it does not contain. The fourth plate measures that directly. First, though, the question of which splits an existence query actually asks.

Where an existence query’s splits come from #

94% of patterns that occur are settled by the first split asked, and 56% of patterns that do not occur never reach the grid at all. These two numbers decide how much any test in front of the grid can save, and both were fixed before the grid was consulted.

A pattern that occurs splits at every position, and the first split, with a prefix of one character, makes a rectangle 245 columns wide. A single character’s range among the reversed prefixes holds every phrase that ends in that character, which on English text is a large share of all phrases, and a rectangle that wide almost always catches a point. An existence query asking splits from the shortest prefix up stops there, and the 14% of splits that are empty are mostly later splits it never asks.

A pattern that does not occur is stopped earlier still. Replacing one character in a substring of eight or sixteen characters almost always creates a string the text lacks on both sides of some position, and for most splits either the prefix or the suffix has no range at all. The search for that range, in the sorted orders that a rectangle over a permutation built the grid from, fails before any rectangle exists. Of the 300 absent patterns, 168 have no split with both ranges non-empty. The other 132 ask one or two splits each, all empty, and those 198 rectangles are the whole of the grid’s work on patterns that do not occur.

So the empty splits the closing section had in mind come from two places, and neither is where an existence query spends. Most of them, 290 of the 488, belong to patterns that occur, after the split that already said yes. The candidates a filter cannot avoid found most of a search’s cost in splits that come to nothing, but that search was reporting every occurrence and had to ask every split. A search that stops at the first yes does not.

The splits the test lets through #

At six levels the empty splits answered maybe miss the nearest point of their column range by a median of five rows, and 27% miss it by one row; those turned away miss it by a median of 250. The closing section asked whether the splits that come to nothing are the ones whose rectangles sit closest to points they miss. They are. A test that stops the descent early cannot separate a rectangle that misses a point by one row from a rectangle that holds it, because both share a node at every depth above the last few.

That closeness is not an accident of this grid. A split’s rectangle is the intersection of a prefix range and a suffix range of a pattern that almost occurs, or of a pattern that occurs, at a position where it does not cross a phrase boundary. In the suffix order, the suffix ranks just outside the rectangle are suffixes that share most of the pattern’s suffix and differ in a later character. If the prefix side matches too, there is a point there, a phrase boundary preceded by the right prefix and followed by nearly the right suffix. Near-misses are what a repetitive text is made of. A collection of 24 copies of one base text at five per cent divergence is full of strings that differ from an occurring one in one character, which is exactly how the absent patterns were made.

So the test works where the question is easy and fails where it is hard, which is the shape of every early-exit filter. The 75% it turns away were mostly turned away cheaply by the full grid too, which is the same lesson the operations a candidate count leaves out drew from a filter priced by what it removed rather than by what removing it saved. A rectangle that misses every point by 250 rows is abandoned by the full descent within a level or two of where the test stops.

What the full grid already costs #

Without any test, the full grid settles an existence query for a pattern that occurs in 12.9 nodes, asking the shortest prefix first, and for one that does not occur in 3.1. That is the budget a test has to beat. Twelve levels and a few branchings is what a single occupied split costs, and a pattern that does not occur costs a quarter of that because most of them cost nothing.

The order of the splits moves the first number by a quarter. Asking the longest prefix first costs 9.4 nodes, since a long prefix has a narrow column range, 8.4 columns on average against the first split’s 245, and a descent over a narrow range of columns empties its nodes quickly. It asks 1.26 splits instead of 1.10, because a narrow rectangle is more often empty, but each costs less. Middle-first is the worst of the three. None of the orders touches the cost of absent patterns, which ask every split they have.

The test in front of the grid #

Put in front of the full grid, the test only adds work: at six levels a pattern that does not occur costs 4.2 nodes against 3.1, and one that occurs costs 20.4 against 12.9. At no depth does the combination cost less than the full grid alone, for either kind of pattern.

The plate’s arithmetic is simple once the test is seen for what it is. The test’s nodes are the top levels of the same descent the full grid makes. A split it answers no is a split the full grid would have abandoned in about the same number of nodes, since the abandoning happens near the top. A split it answers maybe is searched again from the root, so its top levels are paid twice. For a pattern that occurs, the first split is nearly always a maybe at six levels and is nearly always occupied, so the test is pure overhead on the one split the query needed. A test built from the top of a search is not a cheaper question. It is the first half of the same question, asked twice when the answer is unclear.

There is one setting where the plate’s count of nodes is the wrong measure. If the top six levels lived in fast memory and the rest on a slower medium, the cost would be the splits sent on, not the nodes. Patterns that do not occur then send 0.15 splits each to the slow levels against 0.66 without the test, 77% fewer. Patterns that occur send 1.05 against 1.10, almost no saving. The test pays only where most queries are for patterns that do not occur, and only where its levels are cheaper to read than the rest.

The test with nothing behind it #

On its own, the grid stopped at six levels, 69% of the floor, says occurs with certainty for 53% of patterns that occur and absent for 87% of those that do not, and leaves the rest undecided. It is never wrong. It is a structure that knows only whether, at three quarters of the bits an exact structure must hold, and the price is a third answer.

The two kinds of pattern are undecided for different reasons. A pattern that occurs needs some split’s rectangle to contain a whole node at depth six, which needs a rectangle at least about 56 rows tall at a point. A pattern with a long suffix and a short prefix often has one, and about half do. A pattern that does not occur is undecided when one of its few splits misses a point by fewer rows than a node covers, which is the near-miss of the closeness plate. Of the 180 patterns the six-level test leaves at possibly, 142 occur and 38 do not.

That is also the exact limit the floor sets. An existence test that is right on every rectangle decodes the permutation the same way an exact counter does. In a single column, “is there a point at height $y$ or below?” is a count of nought or one, so binary search on existence alone finds every point, in the same 42,860 questions a count that names every point used. Exact existence costs the floor. Approximate existence can go under it, and what it buys is measured by the undecided share, which falls from 47% to 11% between six and ten levels as the test approaches the floor and passes it.

What the prediction got right, and what it was really about #

The closing section predicted that at six levels the test would turn away nine in ten empty splits and never an occupied one. It turns away three in four and never an occupied one. Nine in ten takes ten levels, above the floor.

The prediction’s premise was that a cheap test for empty splits would do most of the work of an existence query, because most of a search’s cost is splits that come to nothing. That premise belonged to a search that reports every occurrence. An existence query stops at the first yes and, on a pattern that occurs, its first split is a one-character prefix across 245 columns that is almost always occupied. On a pattern that does not occur, the sorted orders already answer absent for most of them before any rectangle exists. What is left for the grid to settle are the near-misses: rectangles a few rows from a point, which is exactly where a test that stops early cannot see.

The finding generalises past this index. An early-exit test built from the top of a structure is worth having only when the structure’s own search does not already exit early. A wavelet descent abandons empty nodes at the top by itself, so a test made of those top levels repeats work the descent was going to do anyway. The answer that is allowed to be wrong bought error with bits in summaries that see each item once. A test that sits in front of an exact search buys nothing unless it is cheaper to read than the search’s own first steps.

What the measurement assumes #

Patterns made by substitution. The absent patterns are substrings of the text with one character replaced. That makes them near-misses by construction, which is the hardest case for the test and probably the commonest absent query for a repetitive collection, a variant of a passage that is almost there. Absent patterns drawn from another text would mostly fail at the sorted orders and never reach the grid.

Splits asked shortest prefix first. The cost plates use the order the earlier essays used. Longest-first costs a quarter less for the full grid, and it changes which split the test sees first, since a narrow rectangle is more often a no. The test in front of a longest-first search was not measured.

Nodes as the cost. Every cost is nodes visited, each a pair of rank queries. A test kept in faster memory than the rest of the grid changes the account to splits sent on, which is reported beside it but not timed.

Still open: the split asked first #

The full grid settles a pattern that occurs in 12.9 nodes asking the shortest prefix first and 9.4 asking the longest first, and both orders are fixed before the query sees anything. But both ranges of every split are known before the grid is consulted: they are the result of the searches in the sorted orders, and their widths say how large each split’s rectangle is. A rectangle wide in columns and tall in rows is the likeliest to hold a point, and a rectangle narrow in columns is the cheapest to descend.

The measurement that follows orders the splits by a score computed from the two ranges alone, such as the rectangle’s area, its column width, or the product of its width and height against the number of points the grid holds, and asks the full grid in that order until the first yes. It counts nodes and splits for patterns that occur, against the three fixed orders. The prediction is that ordering by the expected number of points, width times height over the grid’s size, settles a pattern that occurs in under eight nodes, because it asks first the split most likely to be occupied among those that are cheap to descend. The question is whether an existence query can choose its own first question from what the two sorted orders already told it, or whether the cheapest split and the likeliest split are too seldom the same one.