Compressed and still mutable: a dynamic compressed self-index

The Compression Information Processing team at RIKEN AIP has a paper accepted to ESA 2026:

Dynamic Grammar-Compressed Self-Index in δ-Optimal Space Takaaki Nishimoto, Yasuo Tabei

The three terms in the title are three constraints: dynamic (it can change), grammar-compressed (it stays small), and δ-optimal space (it sits near the theoretical lower bound). The problem has been that you could only ever have two of the three at once.

The shape of the problem

Some data is naturally, enormously repetitive:

• Collections of genome sequences (the same region across many individuals is nearly identical)
• Web archives (hundreds of snapshots of the same site)
• Document collections under version control (consecutive revisions differ by a few lines)

Repetitiveness means the data compresses extremely well. A compressed self-index goes further: it stores the compressed form and supports pattern matching without decompressing — fusing two things that used to conflict.

The trouble is that real string data is not static. Genome repositories gain samples, archives gain snapshots, repositories gain commits.

• Most high-performance compressed self-indexes are designed for static data — change anything and you rebuild the whole thing
• Methods that do support updates struggle to combine a high compression ratio, fast search, and efficient updates

What dynamic RR-index trades

The proposed structure is the dynamic RR-index, built on grammar compression: recurring structure in the string is expressed as a set of grammar rules, and the rule set is the compressed representation.

The key move is to keep the information search needs in a form that can be updated. Compression, search, and insertion/deletion then coexist.

The theoretical result is reaching δ-optimal space in expectation. The quantity δ measures how repetitive the data is — the more repetitive, the lower the theoretical bound. Being δ-optimal means storage is close to that bound while exploiting the repetition.

The authors state that, to their knowledge, this is the first dynamic compressed data structure to achieve δ-optimal space.

The abstract also mentions validation on Wikipedia data at 37 GB scale. My copy of the abstract was truncated at that point, so I am not quoting the specific figures.

Why this is hard

There is a tension that gets underestimated:

Compression exploits repetition, and repetition changes when the data changes.

A small example: if abc occurs a million times, the compressor hoists it into one rule, so a million occurrences cost one. Now delete a hundred thousand of them — is the rule still worth having? And if that rule embeds another rule, how far does the disturbance reach?

A static algorithm can read the entire input, decide the grammar, and freeze. A dynamic one must repair the grammar locally after every edit while guaranteeing:

• The grammar does not grow (or the ratio quietly degrades)
• The index stays valid (or queries degenerate into scans)
• The repair is sublinear (or one insert costs as much as a rebuild)

Those three pull against each other, and δ-optimal space means even the constant factors are tight.

How far this is from daily work

Honestly: far. You will not use it in application code tomorrow.

The audience for this kind of result is not application developers but:

• Genome databases — huge, highly repetitive, continuously growing. All three conditions.
• Web archives — Internet Archive scale.
• Low-level indexes in version control — if you want history searches like git log -S to be faster.

What these have in common: the data is large enough that rebuilding an index costs hours to days, and it never stops changing. For them, mutability is not a nice-to-have; it decides whether the thing is usable at all.

Where I land

The value of a theory paper is usually not “you can use this now” but which pair of constraints it proves is not actually a contradiction.

Before this, the engineering folklore was “compression or updatability, pick one”. This paper says: under a precisely stated measure — δ-optimal space — both hold at once. Whether the constants and implementation difficulty make it practical is a question for the next few years. But the claim that it is impossible has been refuted, and that is exactly what theory is for.