A research paper by Takaaki Nishimoto, Research Scientist, and Yasuo Tabei, Team Director, of the Succinct Information Processing Team at the RIKEN Center for Advanced Intelligence Project (RIKEN AIP) has been accepted at the Data Compression Conference (DCC) 2026, a major international conference in the field of data compression.
Overview
This research presents a new data structure called the dynamic r-index, designed for large-scale string data with repetitive structures, such as genomic sequences and document edit histories, where the same patterns appear repeatedly. With existing technologies, it has been difficult to achieve both searching over compressed data and updating the data contents (i.e., insertions and deletions). The proposed approach enables efficient operation with data insertions and deletions while maintaining a highly compressed representation.
Significance of the Research
- Effective utilization of large-scale data:
The proposed method provides a memory-efficient and fast search mechanism for large repetitive datasets that continuously grow and evolve, such as document histories and biological sequences. - Applicability to low-resource environments:
By reducing the amount of memory required to store the data, this technology is expected to be applicable to data processing—including search and matching — on resource-constrained platforms and edge devices.
Future Outlook
This technology aims to contribute to data processing in edge computing environments where privacy protection and low latency are required, as well as to the management of large-scale biological data that are continuously accumulated over time.
Paper Information
- Conference: Data Compression Conference (DCC) 2026
- Paper Title: Dynamic r-index: An Updatable Self-Index in LCP-bounded Time
- Authors: Takaaki Nishimoto, Yasuo Tabei
- arXiv Preprint: https://arxiv.org/abs/2504.19482
