The flat bottom of a shallow curve

Elias–Fano has exactly one parameter: how many of each position’s low bits to store packed, with the rest going into the high vector.

The textbook answer is w = ⌊log₂(n/m)⌋ and the reason is a calculation short enough to do in a line.

The low parts cost m·w. The high vector has m ones and n/2ʷ zeros, so it costs m + n·2⁻ʷ. The total is m·w + m + n·2⁻ʷ, whose derivative in w is m − n·2⁻ʷ·ln 2 — zero at 2ʷ = n·ln 2/m.

So the optimum is at w = log₂(n/m) + log₂(ln 2), and log₂(ln 2) is −0.529. The textbook floor is within half a bit of the true optimum by construction, and the difference between the two is what this essay is about — which is to say, almost nothing.

The curve #

For a thousand and twenty-five marks in eight thousand one hundred and ninety-three positions:

w = 0: low 0, high 9,219, total 9,219. w = 1: low 1,025, high 5,122, total 6,147. w = 2: low 2,050, high 3,074, total 5,124. w = 3: low 3,075, high 2,050, total 5,125. w = 4: low 4,100, high 1,538, total 5,638. w = 5: low 5,125, high 1,282, total 6,407. w = 6: low 6,150, high 1,154, total 7,304.

The minimum is at w = 2 and the next value is one bit away.

Reading the two component lines is worth a moment because they explain the shape better than the total does. The low parts are a straight line through the origin with slope m; the high vector is an exponential decay from n + m toward m. Their sum is a curve that falls steeply while the exponential dominates and rises linearly once the line does, and the transition between those two regimes is the minimum.

Everything about the curve’s shape follows from that, including its asymmetry: it is steeper on the left, because an exponential rising is faster than a line rising, so under-splitting is worse than over-splitting by the same amount. At w = 1 the total is 6,147 and at w = 3 it is 5,125, both one step from the optimum in opposite directions and a thousand bits apart.

Why the bottom is flat #

The two terms move in opposite directions and at different rates, which is what makes the sum’s minimum shallow.

The low parts grow linearly in w: each extra bit costs m bits, always.

The high vector shrinks exponentially: each extra bit halves n/2ʷ.

Near the optimum those two rates are equal by definition, so moving w by one changes the total by (the linear cost of one bit) minus (half the current high vector), and near the optimum those are the same number. The first-order term cancels and what is left is second-order.

That is the general reason a sum of a linear and an exponential has a flat minimum, and it is why the choice is forgiving.

What the flatness excused #

This collection has carried an Elias–Fano size model since the repetition strand — a class that reports r·low + 2r bits for a set of r positions — and it rounds the split up where the structure rounds it down.

On a set of m = n/8 the two disagree: the model splits at 3 and the structure at 2. On the curve above those are 5,125 and 5,124.

One bit in five thousand. The model has been pricing sets correctly, for several strands, using the wrong parameter — and nothing noticed, because the parameter it uses is one step from the one it should use on a curve whose steps near the bottom are single bits.

That is a comfortable outcome and it is worth being precise about what it does and does not say. The model’s width is wrong by one. Its total is right to a bit per thousand. And its omission of the high vector’s directory is a genuine error of ten per cent, which is a different matter and is a price with no structure under it.

So the flatness excused one of the model’s two problems and not the other.

The flatness is not the same everywhere on the sampling dial, and the direction is convenient. A sparser set has a larger optimal w, and the curve near a larger w is flatter — because the exponential term is smaller there, so the second-order behaviour dominates over a wider range.

So a size model rounding the width the wrong way is most accurate on the sparse sets where the structure is most worth using, and least accurate on dense ones where it is not being used anyway.

Why the floor rather than the round #

Given that the true optimum is at log₂(n/m) − 0.529, a reader might ask why the convention is the floor rather than rounding to nearest.

Two reasons, and only the second is about size.

The floor is what makes the bucket occupancy about one. The number of positions sharing a high part is m·2ʷ/n, which at w = ⌊log₂(n/m)⌋ is between a half and one. That is what bounds a rank’s scan, and it is the reason the choice is not purely a size question.

And rounding to nearest would sometimes give a larger w, which makes buckets emptier and the high vector longer — costing bits and a slightly longer select. The floor errs toward the side where the scan is bounded.

What the curve looks like away from the bottom #

The flatness is local and the curve is not flat elsewhere, which matters because a parameter chosen badly is caught by the size.

At w = 0 the total is 9,219 against the optimum’s 5,124 — a factor of 1.80, and every position is in the high vector, which is a unary encoding.

At w = 6, four above the optimum, it is 7,304 — a factor of 1.43, and the structure is approaching a packed array of positions.

So a wildly wrong width costs between forty and eighty per cent, which is enough to be noticed by any size measurement and not enough to be catastrophic. That is the shape of a well-behaved parameter: forgiving near the answer, mildly punishing far from it, and never wrong in kind.

The rejection test in this strand forces the degenerate case and requires the size check to catch it: at w = 0 on a sixteen-thousand-position set the structure is 10,043 bits against the chosen split’s 1,968, a factor of 5.1. That is a larger factor than the curve above shows because the set there is sparser — one row in thirty-two rather than one in eight — and the sparser the set, the more the high vector suffers from a small width.

What a rejection has to do here #

A parameter whose wrong values cost only a size needs a rejection test that checks a size, and that is a weaker kind of check than most in this collection — so it is worth saying what it does and does not establish.

The test forces the degenerate split, rebuilds the high vector to match so that the object is a working structure with a badly chosen parameter rather than a broken one, and requires the size to be larger. It comes out at 10,043 bits against 1,968.

What that establishes is that the size accounting is sensitive to the parameter. What it does not establish is that the chosen parameter is the best one, because a check comparing two points cannot say anything about the rest of the curve.

The curve itself is the evidence for that, and a plate is not a check. So this strand’s position is: the width’s optimality is drawn and not asserted, and what is asserted is that a wrong width is caught.

That is the right division. Asserting an optimum would mean computing the whole curve at every check, which is the measurement rather than a guard; asserting that a specific bad value is caught is cheap and catches the failure that would actually happen, which is a width computed from the wrong quantity.

The parameter that is not a tuning knob #

There is a difference between a parameter with an optimum and a parameter with a trade, and this one is the first kind. That is worth stating because most of the parameters in this collection are the second.

A sampling rate trades size against locate time, so there is no optimum — only a curve a system picks a point on. A compressed vector’s block size trades compression against decode cost. A cache’s size trades memory against hit rate.

The low width trades nothing. There is one number that minimises the size, it also happens to bound the rank’s scan, and moving away from it makes both worse. Nobody has to decide anything.

That is unusual enough to be worth noticing when it happens, because a parameter with an optimum can be computed at construction time and forgotten, and a parameter with a trade cannot.

A position split in two is the construction this parameter belongs to, and the array that says where is twice the samples is the term it is replacing. Both quote sizes that assume the width chosen here.

Where the second-order term goes #

For completeness, the size at the optimum is worth writing because it is the number every other essay in this strand compares against.

Substituting 2ʷ = n·ln 2/m into m·w + m + n·2⁻ʷ gives m·log₂(n/m) + m·log₂(ln 2) + m + m/ln 2, which is m·log₂(n/m) + m(1 − 0.529 + 1.443) — that is, m·log₂(n/m) + 1.914·m.

The information-theoretic minimum for a sorted set of m elements in n is log₂ C(n, m) ≈ m·log₂(n/m) + 1.443·m.

So Elias–Fano is within 0.47 bits per element of the entropy of a sparse set, with constant-time select. That is the reason it is the standard representation and it is a bound rather than a measurement.

At m = 513 that gap is 241 bits against a structure of 3,905 — 6.2%, before the directory. The directory is 596 bits, which is another 15%. So the object is about a fifth over the information, and the encoding is six per cent over.

The two roundings, side by side #

It is worth putting the specific numbers down because they are the whole of the incident that produced this essay.

A set of 1,025 marks in 8,193 positions. n/m is 7.993 — just under eight, which is where the two roundings differ maximally.

⌊log₂ 7.993⌋ = 2. ⌈log₂ 7.993⌉ = 3.

At w = 2: low 2,050, high 3,074, total 5,124. At w = 3: low 3,075, high 2,050, total 5,125.

One bit.

That the set lands at n/m = 7.993 rather than 8.000 is itself worth a sentence: the index has 8,193 rows for 8,192 characters, because of the sentinel, and the marks are the rows whose suffix-array value is a multiple of eight — of which there are 1,025 rather than 1,024. Two off-by-ones in opposite directions putting the ratio a hundredth under a power of two, which is exactly where the floor and the ceiling disagree.

A test comparing the two roundings on a set whose n/m was 8.5 would have found them agreeing. This one found them differing, by one bit, which is the most informative possible outcome: the parameters differ and the answer does not.

What the flatness means for a reader #

Two practical consequences and one general one.

A size model can round either way. A structure priced with ⌈log₂(n/m)⌉ rather than the floor is priced correctly to a bit per thousand. This collection’s own model does exactly that and has been right for several strands.

A width computed from stale parameters is nearly harmless. A structure built with w chosen for a set of a slightly different size — a common enough situation when the width is fixed at compile time — pays a second-order penalty rather than a first-order one.

And a parameter’s forgiveness is a property worth measuring. This collection has parameters that are not forgiving — a Bloom filter’s bit count, a Count–Min sketch’s width, a merge’s run length — where being off by a factor of two costs a factor of two. Knowing which kind a parameter is decides how much effort its tuning deserves, and the sweep that says so costs one plate.

Parameters that are not like this one #

Setting this parameter beside the collection’s others makes the classification concrete, and the contrast is sharper than “some parameters are forgiving”.

A Bloom filter’s bit count. Halving it does not halve the false-positive rate; it raises it by a power. A filter allowed to be wrong draws that curve and it has no flat region at all.

A merge’s minimum run length. The sort the library ships measured a shipped value of thirty-two costing 39.6% on nearly sorted input at one size — a first-order penalty for a value that is right elsewhere.

A compressed vector’s block size. Rank is the only thing it does found an optimum and a curve either side of it, and the curve is shallow near the bottom for the same reason as this one — two terms moving oppositely — but its two terms are compression and directory rather than a line and an exponential, and the bottom is correspondingly less flat.

The pattern across those: a parameter balancing a linear cost against an exponential one has a very flat optimum; one balancing two linear costs has a corner; one appearing in an exponent has no flat region anywhere.

That is a rule of thumb rather than a theorem and it says where to spend tuning effort, which is the practical question a parameter raises.

Why a model can be right for the wrong reason #

There is a general lesson underneath the one-bit result and it is uncomfortable enough to be worth stating plainly.

A model that has been right for several strands was right by accident of the curve’s shape. Its width was wrong; the total it produced was right; nobody could have told the difference from its outputs.

That is a well-behaved failure — a wrong parameter on a flat curve produces a right answer — and it is exactly the kind of thing that stops being well-behaved when circumstances change. A model rounding up would go wrong the moment somebody used it on a set where the curve is not flat, which is a dense set, which is a case the model was never meant for and which nothing prevents.

So the correct response to “the model has been right anyway” is not relief. It is to check why it has been right, which is what this essay is, and then to decide whether the reason is stable. Here it is: the flatness is a property of the encoding rather than of the data, so the model will keep being right for as long as it is used on sparse sets.

That is a conclusion a reader can act on, and it took a curve to reach. Without it the available conclusions were “the model agrees, so it is fine” and “the widths differ, so it is broken”, and both are wrong.

A price with no structure under it is where the model’s other problem is measured, and the contrast between the two is instructive: one is a wrong parameter on a flat curve and costs nothing, and the other is a missing term and costs ten per cent.

The one thing the curve cannot say #

The curve is about size and the strand’s other question is about time, and the width affects both.

A larger w means fewer, fuller buckets, so a rank’s scan is longer. A smaller w means more, emptier buckets, so the high vector is longer and its select’s search is over more bits.

At the chosen width the scan averages 1.25 accesses, and neither direction is measured here. The reason is that the size curve’s flatness means the interesting widths are all within one of each other, and the scan’s expected length changes by a factor of two across that range — from about 0.6 to about 2.5.

So a system that cared about the rank’s cost more than about a bit per thousand would choose w one below the size optimum, and the size would rise by one bit per thousand. That is a real option nobody would bother with, and it is the only sense in which this parameter has a trade at all.

The reason it is not worth bothering with is arithmetic rather than taste. A locate’s mark operations are a few per cent of its cost — the wavelet tree’s ranks dominate — so halving the bucket scan moves a locate by a fraction of a per cent, and the bit per thousand it costs is a fraction of a per cent of the structure. Two negligible quantities traded against each other.

Every occurrence at the same price is where a locate’s cost was broken down here, and it is the measurement that says which parts of this structure are worth tuning. The marks are not one of them.