Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.19482 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912674658385920 |
|---|---|
| author | Nishimoto, Takaaki Tabei, Yasuo |
| author_facet | Nishimoto, Takaaki Tabei, Yasuo |
| contents | A self-index is a compressed data structure that supports locate queries -- reporting all positions where a given pattern occurs in a string while maintaining the string in compressed form. While many self-indexes have been proposed, developing dynamically updatable ones supporting string insertions and deletions remains a challenge. The r-index (Gagie et al., JACM'20) is a representative static self-index based on the run-length Burrows-Wheeler transform (RLBWT), designed for highly repetitive strings. We present the dynamic r-index, a dynamic extension of the r-index that achieves updates in LCP-bounded time. The dynamic r-index supports count queries in $O(m \log r / \log \log r)$ time and locate queries in $O(m \log r / \log \log r + \mathsf{occ} \log r)$ time, using $O(r)$ words of space, where $m$ is the length of a query with $\mathsf{occ}$ occurrences and $r$ is the number of runs in the RLBWT. Crucially, update operations are supported in $O((m + L_{\mathsf{max}}) \log n)$ time for a substring of length $m$, where $L_{\mathsf{max}}$ is the maximum LCP value; the average running time is $O((m + L_{\mathsf{avg}}) \log n)$, where $L_{\mathsf{avg}}$ is the average LCP value. This LCP-bounded complexity is particularly advantageous for highly repetitive strings where LCP values are typically small. We experimentally demonstrate the practical efficiency of the dynamic r-index on various highly repetitive datasets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_19482 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Dynamic r-index: An Updatable Self-Index in LCP-bounded Time Nishimoto, Takaaki Tabei, Yasuo Data Structures and Algorithms A self-index is a compressed data structure that supports locate queries -- reporting all positions where a given pattern occurs in a string while maintaining the string in compressed form. While many self-indexes have been proposed, developing dynamically updatable ones supporting string insertions and deletions remains a challenge. The r-index (Gagie et al., JACM'20) is a representative static self-index based on the run-length Burrows-Wheeler transform (RLBWT), designed for highly repetitive strings. We present the dynamic r-index, a dynamic extension of the r-index that achieves updates in LCP-bounded time. The dynamic r-index supports count queries in $O(m \log r / \log \log r)$ time and locate queries in $O(m \log r / \log \log r + \mathsf{occ} \log r)$ time, using $O(r)$ words of space, where $m$ is the length of a query with $\mathsf{occ}$ occurrences and $r$ is the number of runs in the RLBWT. Crucially, update operations are supported in $O((m + L_{\mathsf{max}}) \log n)$ time for a substring of length $m$, where $L_{\mathsf{max}}$ is the maximum LCP value; the average running time is $O((m + L_{\mathsf{avg}}) \log n)$, where $L_{\mathsf{avg}}$ is the average LCP value. This LCP-bounded complexity is particularly advantageous for highly repetitive strings where LCP values are typically small. We experimentally demonstrate the practical efficiency of the dynamic r-index on various highly repetitive datasets. |
| title | Dynamic r-index: An Updatable Self-Index in LCP-bounded Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.19482 |