A paper by Research Scientist Takaaki Nishimoto and Team Director Yasuo Tabei of the Compressed Information Processing Team at the RIKEN Center for Advanced Intelligence Project（RIKEN AIP）,
“Dynamic Grammar-Compressed Self-Index in δ-Optimal Space”,
has been accepted to
European Symposium on Algorithms（ESA 2026）,
a major international conference in the field of algorithms.
Overview
This study proposes a new compressed data structure that can efficiently search large-scale string data while keeping it compressed, and that also supports insertions and deletions.
In recent years, large-scale string data with many repeated substrings has been rapidly increasing. Examples include collections of genome sequences, web archives, and version-controlled document collections. Such data is highly repetitive and can therefore be stored in much less space when compressed appropriately. At the same time, real-world string data is not static: it is continuously updated. Therefore, it is important not only to store data compactly, but also to search it efficiently while it remains compressed and to handle updates efficiently.
Compressed data structures for string search allow strings to be stored in compressed form while supporting search without fully decompressing the original data. However, many high-performance methods are designed for static data, meaning that the entire data structure must be rebuilt when the data changes. Existing dynamic methods that support updates have struggled to achieve high compression, fast search, and efficient updates at the same time.
Research Methods and Findings
To address this challenge, this study proposes a new grammar-compressed data structure called
dynamic RR-index.
The dynamic RR-index represents repetitive structures in strings compactly using grammar compression, while maintaining the information needed for search in an updatable form. This makes it possible to search the data and perform insertions and deletions while keeping the data compressed.
From a theoretical perspective, the proposed method achieves δ-optimal space in expectation. This means that, for highly repetitive strings, the data structure stores the data in nearly optimal space while supporting both search and updates. To the best of the authors’ knowledge, this is the first dynamic compressed data structure of this kind to achieve δ-optimal space.
In benchmark experiments using datasets including a 37 GB Wikipedia edit-history dataset and a 59 GB human chromosome dataset, the dynamic RR-index was up to 77 times faster than the existing dynamic r-index for update operations, and up to 11 times faster than other dynamic methods for search operations.
Future Outlook
This result is expected to serve as a foundational technology for efficiently handling continuously updated large-scale string data, such as genome databases, web archives, and version-controlled document collections. In addition to advancing the theory of compressed data structures, it may also contribute to applications in large-scale data management and search systems.
