Metraipolis › archive › dc_3bb6574941a1
Move-rb: Faster Bi-Directional r-indexes and Approximate Pattern Matching — arXiv:2609.30089
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.30089
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T07:26:44.758Z
- SHA-256 of the archived text
e2a577364ccc62d108d32f9b420d59f0b0f293ef5e7aaafd0cefaadf7a3b46fa- Stable URL of this page
https://metraipolis.com/documento/dc_3bb6574941a1
How to cite
Move-rb: Faster Bi-Directional r-indexes and Approximate Pattern Matching — arXiv:2609.30089 — arXiv (en), https://arxiv.org/abs/2609.30089 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3bb6574941a1 (Metraipolis archive dc_3bb6574941a1, sha256 e2a577364ccc62d108d32f9b420d59f0b0f293ef5e7aaafd0cefaadf7a3b46fa)
BibTeX
@misc{dc3bb6574941a1,
title = {Move-rb: Faster Bi-Directional r-indexes and Approximate Pattern Matching — arXiv:2609.30089},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.30089},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3bb6574941a1; sha256 e2a577364ccc62d108d32f9b420d59f0b0f293ef5e7aaafd0cefaadf7a3b46fa},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.30089. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Approximate pattern matching (APM) on highly repetitive texts is a central task in bioinformatics. Bi-directional r-indexes support left- and right-extension of a pattern and thereby accelerate APM algorithms based on search schemes, but existing variants -- br-index and b-move -- suffer from two bottlenecks: $O(\sigma)$ character-predecessor/-successor queries on the run-length-encoded BWT per extension, and predecessor queries on sparse bit vectors to maintain a value in the suffix array interval and to access the PLCP array while locating. We present Move-rb, a bi-directional r-index built on the optimized r-index Move-r. Although Move-rb is 2x larger than br-index, it is up to 24% smaller than b-move, answers APM queries 1-4 orders of magnitude faster than br-index, 1.9-10x faster than b-move and up to 5.5x faster than the state-of-the-art bi-directional (uncompressed) FM-index columba, which is 36-42x larger. Memory usage (including index size) during APM locate queries is reduced by 1.5x (up to 6.5x) for Hamming distance and 2.5x (up to 7.4x) for edit distance. Move-rb can be constructed 3-14x faster while using 19-141x less memory than br-index, b-move and columba. A variant using a relative Lempel-Ziv-encoded suffix array locates up to 10x faster while being 1.2-2.4x larger. We achieve these speedups by optimizing index operations and search scheme APM algorithms: Without a direction switch, Move-rb computes an all-$k$-character extension in output-optimal $O(k)$ time and a single-character extension in the same time. Augmenting Move-rb with $O((r+\overleftarrow{r})\log(n/r_{\min})\log\sigma)$ bits reduces a single-character extension to $O(\log\sigma)$ time, where $r$ and $\overleftarrow{r}$ are the numbers of runs in the BWT of the text and its reverse, and $r_{\min}=\min(r,\overleftarrow{r})$. A direction switch incurs only $O(\log\log_\omega(n/r_{\min}))$ additional time.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-25 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.30089 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T06:44:29.095Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).