Where the sparse representation loses

A sparse representation of a bit vector is smaller than a plain one when the vector is sparse. That sentence has a threshold in it and the threshold is not where a reader would put it.

The numbers #

At one row in one — every row marked — the plain vector is 19,475 bits and Elias–Fano is 38,967. A factor of two the wrong way.

At one in two: 19,475 against 29,189. Still losing, by 1.50.

At one in four: 19,475 against 18,691. Winning, by a hair — 0.96.

At one in thirty-two: 19,475 against 3,905. Winning by five.

At one in a hundred and twenty-eight: 19,475 against 1,258. Fifteen.

So the crossing is between one in two and one in four, and one in four is a sampling rate real indexes use.

Why it loses when dense #

The low width is w = ⌊log₂(n/m)⌋, and at m = n that is zero.

With w = 0 there are no low parts and the high vector holds everything: m ones and n zeros, so n + m = 2n bits. The structure is a unary encoding of a set that has one element per position, which is the worst possible use of a unary encoding.

That is not a defect of the construction; it is the construction behaving correctly on an input it is not for. Elias–Fano’s cost is m(2 + log₂(n/m)) and at m = n the logarithm is zero, so the cost is 2n.

The general form: Elias–Fano beats a plain vector when 2 + log₂(n/m) < n/m, which holds for n/m above about 3.5 and fails below it.

There is a second reason the dense end is not merely a formality, and it is about a different structure. The same Elias–Fano representation is used elsewhere in this collection for a set that is not under the caller’s control: the run starts of a run-length index, which are r positions in n. On a text that does not repeat, r approaches n(1 − 1/σ) — a density of 0.8 on a four-symbol alphabet — which is deep inside the losing region.

So a structure using this representation for run starts is, on non-repetitive text, spending twice what a plain vector would. A sampling that costs more than the array is where a related inversion was found in the same family, and the general shape is the same: a representation chosen for the case the structure is for is being applied in the case it is not.

Why the check has to have this end #

A check asking “is the sparse representation smaller” would pass on every sampling rate a self-index actually uses, and would therefore never fail.

That is a check that has been fitted to its data. This collection’s habit is that an assertion which has never rejected anything proves nothing, so the strand carries a check requiring the sparse representation to lose at density one — and it does, by exactly the factor the arithmetic predicts.

Two-ended checks of that kind cost almost nothing to write and they are what turns a measurement into a claim. Without the dense end, the sentence “Elias–Fano is smaller” is a statement about the sampling rates somebody happened to test.

The picture at density a half is worth looking at because it makes the arithmetic visual. Half the squares are filled, in no pattern, and there is nothing a representation could exploit: not runs, because there are none; not sparsity, because there is none. A plain bit vector is the right answer for that set and no encoding will beat it by much.

That is the general statement of where all three representations stand. A plain vector is optimal for a set of density a half and suboptimal everywhere else, and the two alternatives each attack one side.

What the compressed-block line does #

There is a third representation on the plate and its behaviour is the opposite of Elias–Fano’s, which makes the comparison more interesting than a two-way one.

A block-classed vector stores each block of bits as its class — the number of ones — and an offset within that class. A block that is all zeros or all ones has one possible offset, so its offset costs nothing.

At density one every block is all ones, so the representation costs its directory and almost nothing else: 1,789 bits against the plain vector’s 19,475. A factor of eleven, in the case where Elias–Fano is a factor of two worse.

At density a half it is 17,305 — barely better than plain, because a block of random bits has close to the maximum number of offsets.

At one in thirty-two it is 4,557, which is worse than Elias–Fano’s 3,905.

So the two representations cross each other, and where they cross is twenty bits apart.

What a one-ended plate would have said #

It is worth writing out the essay that would have been produced by measuring only the sparse rates, because it is a plausible essay and every sentence in it is true.

The sample marks are n bits and hold n/s bits of information. Represented as an Elias–Fano array they cost a fifth of that at one row in thirty-two and a fifteenth at one in a hundred and twenty-eight. The index falls by fifteen per cent and the locating apparatus’s share stops flattening.

All correct. What it omits is that the representation is a loss at the dense end of the same dial, so a reader adopting it for an index sampling one row in two would make their structure fifty per cent larger.

That is not a hypothetical rate. An index optimised for locate speed — a genome aligner reporting many occurrences per query — samples densely, and one in two or one in four is where it lives.

Where a dense sampling comes from #

It is worth saying why an index would sample densely, because a reader whose mental model of a self-index is “small at any cost” will not believe the crossing matters.

A locate walks a row backwards until it reaches a sampled one, so the walk’s expected length is s/2 LF steps. Each LF step is a rank and an access on the wavelet tree — several bit-vector operations. So a locate on a sparsely sampled index is genuinely slow: at one in a hundred and twenty-eight it is sixty-four LF steps, or a few hundred bit-vector operations, per occurrence.

A query returning ten thousand occurrences on such an index spends a few million operations locating them. That is the regime a read aligner is in, and its response is to sample densely — one in four, one in two — and accept a much larger index.

The saving, spent measured that trade from the other side: bits saved elsewhere and spent on a denser sampling are worth a factor of five in locate speed at equal total size.

So the dense end of this dial is not a corner case. It is where half the systems using these structures operate, and it is the half where the sparse representation is the wrong choice.

The dial, again #

This is the fourth time in this neighbourhood that the sampling rate has turned out to be the parameter a result depends on, and it is worth collecting them because the pattern is now a rule.

A sixth of what, exactly — a saving quoted as a sixth is 14.0% at one rate and 30.5% at another.

The array that says where is twice the samples — the marks dominate the values above s = log n and are dominated below it.

The saving, spent — a saving is worth a factor of five in locate speed if it is spent on sampling rather than banked.

And this. Four results, one dial, and in every case a number quoted without it is a number about one setting.

The rule this collection now follows: a plate about an index’s locating apparatus carries its sampling rate, and a claim about it that does not name a rate is not a claim.

Where the crossing actually is #

Interpolating between one in two and one in four: the two lines meet at about n/m = 3.5, which is a density of 0.29.

Substituting into the formula: 2 + log₂(3.5) = 3.81 against 3.5. Close, and the measured crossing is a little below the formula’s because the plain vector’s directory is being counted and the formula’s is not.

That is a detail worth noticing because it is the direction the other comparison in this strand goes. A model that omits directories reports Elias–Fano as smaller than it is, and here omitting the plain vector’s directory reports it as smaller too — so the crossing moves in a direction that depends on which structure’s overhead is being ignored.

Counting both, as the measurement does, is the only version that gives a crossing anybody can use.

The two ways a check can be fitted #

The check this essay is about had two available failure modes and only one of them is the obvious one.

Fitted by tolerance. Requiring the sparse representation to be smaller “by at least ten per cent”, where ten is chosen because the data passes at eleven. That is the failure a code word is at least one bit records for a different check in a different strand: the tolerance was widened until the red went away, which produces a check that accepts anything.

Fitted by input. Requiring the sparse representation to be smaller, and only ever running the check at sampling rates where it is. That is subtler because nothing about the check looks loose — it is an exact inequality with no tolerance in it — and it still cannot fail, because the inputs it is given are all on one side of a boundary.

The second is the one this strand had to guard against, and the guard is a check requiring a loss. That is not a natural thing to write: a test asserting that a structure is worse is a test whose failure would be good news, which reads backwards.

It is the right shape anyway. What is being asserted is not that the structure is bad but that the boundary exists where the arithmetic says, and a claim about a boundary needs a point on each side.

What a system should do about it #

The practical form is short, and it is a decision rather than a default.

Sampling at one in eight or sparser: use Elias–Fano. The saving is between two and fifteen times on the marks and between five and eighteen per cent of the whole index.

Sampling at one in four or denser: use the plain vector. The sparse array is at best a wash and at worst twice as large, and the marks are a small share of the apparatus anyway because the sampled positions dominate.

And if the rate is a run-time parameter, the representation should be too. That is more machinery than most systems want, and the alternative is to pick the representation for the rate the system actually runs at, which requires knowing it.

That last is the uncomfortable one. A library shipping a self-index with a configurable sampling rate and a fixed mark representation has made a choice on the user’s behalf, and the choice is right over part of the range.

What the plate says about the third line #

There is a reading of the plate that makes the compressed-block representation look like the answer, and it is worth closing off.

The block representation is better than plain at every density on this plate, and better than Elias–Fano at densities above one in sixteen. So a system that used it everywhere would never be much worse than the best of the three.

Two things against it. Its operations are more expensive: a rank on a block-classed vector decodes a block from its class and offset before counting, which is several times a plain vector’s work, and the marks are read once per LF step of every locate.

And its advantage at density one — the factor of eleven — is on a case nobody runs. An index sampling every row has no marks worth the name; the vector is all ones and the question is why it exists.

So the three-way comparison is really a two-way one over the range that matters, and the block representation’s spectacular numbers are at the ends.

What the marks are at each rate, in one place #

Collecting the whole dial in one list, because the strand’s numbers are scattered across four essays and the ordering is the useful thing.

One in one. 16,385 ones. Elias–Fano 38,967, plain 19,475, blocks 1,789. The set is not a set; it is every row. Nothing here is a real configuration.

One in two. 8,193 ones. Elias–Fano 29,189, plain 19,475, blocks 17,305. Elias–Fano loses by half.

One in four. 4,097 ones. 18,691 against 19,475 and 14,304. Elias–Fano crosses the plain line and is behind the blocks.

One in sixteen. 1,025 ones. 6,745 against 19,475 and 6,765. Elias–Fano and the blocks are twenty bits apart.

One in thirty-two. 513 ones. 3,905 against 19,475 and 4,557. Elias–Fano ahead.

One in a hundred and twenty-eight. 129 ones. 1,258 against 19,475 and 2,566. Elias–Fano ahead by two on the blocks and fifteen on plain.

The plain vector’s 19,475 appearing six times is the point of the list. It is the only one of the three that does not move, and it is the reason the locating apparatus had a floor.

A representation that would not have this problem #

There is a construction that avoids the crossing entirely and it is worth naming so that the choice above is understood as a choice between two specific structures rather than an unavoidable dilemma.

A hybrid vector partitions the universe into blocks and chooses a representation per block: plain for dense blocks, Elias–Fano for sparse ones, a run-length code for uniform ones, with a few bits of header saying which. Its size is within a constant of the best of the three at every density, and it costs a branch per operation.

That is what a production succinct-structures library ships, and it is the reason the crossing above rarely shows up as a practical problem: the library has already made the decision per block rather than per structure.

It is not built here, and the reason is worth stating rather than skipping. This collection’s structures are built to make a mechanism visible, and a hybrid’s mechanism is “measure and choose”, which is a good engineering answer and a poor subject for a measurement — every plate about it would be a plate about the choice rather than about either representation.

What building the two separately buys is the crossing itself, which is the number a hybrid’s implementation needs and which its own measurements would not show, because a hybrid never operates at a density where it has made the wrong choice.

That is a general property of adaptive structures worth carrying: an adaptive structure hides the boundary it adapts across. Measuring the boundary requires the non-adaptive versions, and a field that only ships hybrids stops knowing where the crossings are.

The collection decides which index is small is the same argument at a much larger scale — three whole indexes rather than three vector representations, with the same conclusion that the crossing is the result and the adaptive answer is to measure the corpus.

The shape of a two-ended result #

Stepping back, this essay is a small instance of something this collection does often enough to name.

A measurement establishing that X is better than Y is incomplete until it has found where X is worse. If X is never worse, that is a strong result and needs saying. If X is worse somewhere, the boundary is the result and “X is better” is a summary of one side of it.

The reason it matters here is that the boundary is inside the range a real system operates in. A crossing at one row in ten thousand would be a curiosity; a crossing at one in four is a decision.

And the reason a one-ended measurement is tempting is that the sparse end is where the interesting number is. Fifteen times is a better sentence than “smaller above a density of 0.29”, and it is a sentence about a rate somebody chose.

The habit that follows is cheap and worth stating as a rule. When a plate reports that one representation beats another, its sweep runs until the ordering reverses or until the reversal is shown to be unreachable. The first case gives the crossing, which is the number an implementation needs. The second gives a stronger claim than the plate started with, and it costs a few extra points on an axis that was already being drawn.

What that rule refuses is the sweep that stops just before the interesting part — a range chosen so the answer stays the same across it. Such a sweep is not wrong about anything it draws. It is simply a plate whose axis was cut where the conclusion was still comfortable, and nothing in its own numbers can tell a reader that the cut happened.