Is recursive indexing lossless?

The integer representation is reversible when its rules are followed. Earlier rounding or quantization may already have changed the original measurements.

What happens with a two-symbol nonnegative alphabet?

With 1 as continuation and 0 as terminator, N becomes N ones followed by zero, which is a unary coding convention.

Is this a search-engine index?

No. This entry concerns numerical compression. Other fields use similar wording for different forms of hierarchical indexing.

AI Glossary / MLOps and deployment / Intermediate

Recursive indexing

Definition

Recursive indexing is a numerical encoding technique that represents a value outside a small symbol range as a sequence of in-range symbols. Reserved endpoint symbols indicate that another contribution follows; a final non-endpoint symbol completes the value. This entry uses the data-compression meaning of the term.

What it means

Many datasets contain mostly small integers and a few large ones. Giving every integer enough space for the largest possible value can be wasteful. Recursive indexing lets ordinary small values occupy one compact symbol while allowing exceptional values to occupy several.

The method does not remove those exceptional values or round them down. It decomposes them into contributions that the decoder adds back together. It is often one stage in a larger encoding pipeline, so its benefit must be assessed alongside transformations, metadata and any later entropy compression.

How it works

For a simple nonnegative version, choose an alphabet 0 through M and reserve M as a continuation symbol. While the remaining value is at least M, emit M and subtract M. Emit the final remainder, which is strictly smaller than M, to end the number.

The decoder accumulates symbols until it encounters one smaller than M, outputs the sum, and starts the next number. An exact multiple of M needs a final zero; otherwise the decoder cannot distinguish a finished value from an unfinished continuation.

Signed versions can reserve both lower and upper endpoints, subtracting the appropriate endpoint until the remainder lies strictly between them. Encoder and decoder must agree on the endpoint rules, signed representation and how the resulting symbols are stored.

Three practical examples

1. Predictive sensor data: after a predictor produces mostly small integer residuals, recursive indexing can place ordinary residuals in narrow storage units and represent occasional larger residuals with multiple units.

2. Coordinate storage: scientific data can use integer and difference transformations before packing. Recursive indexing is a documented packing option for macromolecular coordinate compression; exactness depends on the whole pipeline's precision choices.

3. Run lengths: a format with a small count alphabet can represent a long count through repeated continuation contributions. The surrounding run-length format still identifies the repeated symbol and the meaning of each count.

Think of it this way

Think of recording a total with vouchers worth at most seven units. A seven-unit voucher says “keep adding,” and a final voucher worth zero through six says “the total ends here.” A total of fourteen therefore needs seven, seven and zero.

The analogy stops at storage efficiency. Real vouchers have physical costs; encoded symbols have bit representations, and choosing a smaller alphabet may increase the number of symbols needed for large values.

Worked example

Use the nonnegative alphabet {0,1,2,3,4,5,6,7}, with 7 reserved for continuation. Encode the numbers 3, 7, 18 and 0.

The value 3 becomes [3]. The value 7 becomes [7,0], because subtracting seven leaves zero, which must terminate the number. The value 18 becomes [7,7,4]. Zero becomes [0]. The concatenated stream is therefore [3,7,0,7,7,4,0].

To decode, output 3 immediately. Then accumulate 7+0 and output 7. Next accumulate 7+7+4 and output 18. Finally output 0. The terminal symbols recover the four number boundaries without separate lengths.

If each alphabet symbol is packed into three bits, this example uses 7×3=21 payload bits. A hypothetical five-bit fixed-width representation for values 0 through 31 would use 4×5=20 bits. Recursive indexing is slightly larger here, before either format's overhead. Its value depends on the distribution, not merely on the presence of small numbers.

For a nonnegative value N, the number of emitted symbols in this convention is floor(N/7)+1. Very large outliers can therefore be expensive.

Illustrative case study

Fictional case: DeltaCrate narrows the integer residuals in an archive. Most fit into one symbol, and initial samples suggest useful savings. Its first decoder, however, treats an endpoint as a complete value when it reaches a record boundary.

A test containing an exact endpoint multiple reveals the problem: the encoder's required zero terminator was dropped during record assembly. The team fixes the framing rule and adds boundary cases for zero, endpoints, endpoint multiples and the largest supported residual.

It then measures full archived size on a broader sample containing long outliers. This fictional scenario shows why both boundary correctness and the actual value distribution matter when choosing a compact representation.

Common misconceptions and mistakes

“Recursive indexing is ordinary base conversion.” In the illustrated convention, repeated endpoint contributions are added. They are not digits with increasing positional weights.

“The endpoint can also terminate a number.” Not under this convention: it indicates continuation. Exact multiples require a non-endpoint terminator.

“It always reduces storage.” More output symbols can outweigh a narrower alphabet, especially for large values or unsuitable distributions.

“A recursive algorithm requires recursive function calls.” The repeated subtraction and accumulation can be implemented with loops. The encoding idea does not dictate the programming style.

Business use

Use recursive indexing when narrow symbols suit the bulk of a dataset and exceptional values are sufficiently uncommon. Compare it against fixed-width storage and other variable-length integer encodings on representative inputs, including extreme values.

For AI and analytics pipelines, retain clear rules for signed residuals, scaling and reconstruction. Validate exact round trips after all preprocessing stages, and measure complete bytes rather than only the packed array. Put limits on decoded counts and output sizes so a malformed or unexpectedly long continuation sequence cannot cause uncontrolled allocation or arithmetic overflow in the implementation.

Check your understanding

With endpoint 7, why does the value 14 require [7,7,0] rather than [7,7]?

Answer: Both sevens signal continuation. The zero contributes nothing to the sum but tells the decoder that the number is complete.

Related terms

Unary coding
Run-length encoding
Delta encoding
Entropy coding
variable-length quantity
predictive coding
integer packing

Learn next

Implement the small unsigned convention on paper, including zero and exact multiples. Then compare a signed endpoint convention with variable-length quantities and Golomb-style codes on a histogram of actual residuals.

Sources

Primary research: “Towards an efficient compression of 3D coordinates of macromolecular structures,” Packing section, describes signed endpoint recursive indexing used in the authors' experiments: https://pmc.ncbi.nlm.nih.gov/articles/PMC5376293/ . The unsigned seven-unit convention, calculations and fictional case here are original teaching illustrations.

Previous: Recursive feature elimination Next: Recursive Language Model