CS Paper Radar

Revisiting (Bijective) Burrows-Wheeler Transform Space-Time Trade-Off Constructions

Dominik Köppl, Tomohiro I

cs.DS ·submitted 2026-11-02 11:37 UTC · v1

Abstract

The bijective Burrows-Wheeler transform (BBWT) replaces the delimiter of the ordinary BWT by a Lyndon factorization and sorts factor conjugates in $ω$-order. It admits quadratic-time constant-workspace algorithms and linear-time linear-space algorithms. We extend the small-space BWT trade-off of Crochemore et al. [JDA,'15] to the BBWT and accelerate both constructions. For $τ\in [3..n]$, let $σ_τ\le\min(σ,τ+1)$ be the maximum construction-batch alphabet size. We construct either transform in $ O\!\left( \frac{n^2}τ \frac{\logτ}{\log\logτ} \right) $ time and $O(τσ_τ)$ additional space, assuming $τσ_τ=O(n)$. This improves the transferred $O((n^2/τ)\logτ)$ bound by a $\log\logτ$ factor. If $σ_τ\in w^{O(1)}$, where $w\inΩ(\log n)$ is the word size, the time improves to $ O\!\left( \frac{n^2}τ + \frac{n\logτ}{\log\logτ} \right). $ For inversion, the same bounds hold with the global alphabet size $σ$ in place of $σ_τ$.

Closest papers

Nearest neighbours by meaning across the whole index.

Substring Complexity in BWT-Runs Bounded Space

cs.DS ·2026-10-29 ·Johannes Fischer
similarity 0.69
Abstract

Given a string $T[1..n]$, its substring complexity is defined as $δ=\max_k d_k/k$, where $d_k$ is the number of its distinct substrings of length $k$ in $T$. We show how to compute it in $O(n+r\log r)$ time, using only $O(r)$ words of space, where $r$ denotes the number of runs in the Burrows-Wheeler transform.

0.30

Reportable Shortcuts with RLBWTs

cs.DS ·2026-09-06 ·Travis Gagie
similarity 0.65
Abstract

Backward search over a run-length compressed Burrows-Wheeler transform (RLBWT) takes one step per pattern character, even when long stretches of the pattern match material that recurs throughout a highly repetitive collection. We describe shortcuts: for a precomputed set of pairs $(α,β)$ of strings, a backward search that has just matched $β$ and finds $α$ immediately to its left in the pattern can cross $α$ in one step. Since a shortcut is taken only after its pair has been recognized in the pattern, the search returns a report of the shortcuts it took along with the usual BWT interval. Our motivation is pangenome graphs, where such pairs mark the places where a pattern passes through a vertex, so the report gives the path a match takes through the graph. We work out the case of a single linear reference $R$, with $β$ ranging over the length-$\ell$ windows of $R$ starting at multiples of $\ell$, and $α$ over the $2^t \ell$ characters preceding such a window. We show that the search counts correctly, that under stated conditions it crosses a stretch of the pattern matching $m$ consecutive windows of $R$ with $O(\log m + m / 2^τ)$ shortcuts, where $2^τ\ell$ is the longest shortcut, and that the shortcuts can be built efficiently from the RLBWT. On the Pizza&Chili cere collection of 37 genomes, shortcuts make backward search 2.3 to 4.2 times faster on exact patterns of length 200 to 1000, and 1.7 to 2.0 times faster with 1% of the characters substituted, for 86% more space. On 11 gigabases of genomes of seven bacterial species, they make it 1.6 to 1.9 times faster on exact patterns for 32% more space. On whole chromosome 19 haplotypes against 16 to 64 others from the Human Pangenome Reference Consortium, shortcuts in both directions make Boyer-Moore-Li search for maximal exact matches of length at least 1000 about 8 times faster.

0.26

Efficient Lempel-Ziv Prediction with the Run-Length BWT

cs.DS cs.LG ·2026-11-01 ·Ohad Avnery
similarity 0.65
Abstract · 21 pages, 1 table

Lempel-Ziv Plurality (LZP) is an algorithm of Kosoy that predicts the next symbol of a string by using its Lempel-Ziv factorization, and makes at most $O(z\log n)$ mistakes on every string of length $n$ with $z$ LZ77 phrases. We give efficient online implementations of LZP and of a new variant of it. Our first implementation maintains a run-length encoded Burrows-Wheeler transform (RLBWT) of the reversed history. It implements LZP, uses $O(z\log z\log^2 n)$ bits, and has worst-case update and prediction times $O(\log z+\log\log n)$ and $O(σ(\log z+\log\log n))$, respectively, where $σ$ is the size of the alphabet. This is an exponential improvement over Kosoy's implementation, whose update time is $O(z\log^7 n)$. We then introduce the Lempel-Ziv Majority (LZM) predictor, which has the same mistake bound and update time, and predicts in $O(1)$ time independently of $σ$. These two predictors accept new symbols at any time, without knowing the alphabet in advance. For an alphabet known in advance, a different data structure gives $O(σ(1+\log z/\log\log n))$ time per symbol, which is constant when $σ=O(1)$ and $z=\mathrm{polylog}(n)$.

0.25

Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries

cs.DS ·2026-08-19 ·Dominik Kempa, Tomasz Kociumaka
publishedtheory similarity 0.64
Abstract · Full version of a SODA 2027 paper

For a text $T$ of length $n$ over an alphabet of size $σ$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix array in 2000, both queries have been supported in $O((\log_σn)^ε)$ time using $O(n\logσ)$ bits, for any constant $ε>0$. Yet no nontrivial time-space lower bound for suffix-array queries in compact space was known. We give the first such lower bound: in the cell-probe model with $Θ(\log n)$-bit words, every deterministic $S$-bit data structure with $S\ge n$ answering suffix-array queries on binary strings of length at most $n$ has worst-case query time $Ω(\log\log n/\log((S/n)\log\log n))$. Hence, structures with $O(n(\log\log n)^{O(1)})$ bits need $Ω(\log\log n/\log\log\log n)$ query time, while constant query time requires $Ω(n\log^εn)$ bits for some constant $ε>0$, matching known upper bounds. In particular, no such $O(n)$-bit structure supports constant-time queries, answering the 25-year-old question of Grossi and Vitter. We also give exact complexity-preserving equivalences between suffix-array access and simpler prefix queries on short strings. For every $2\leqσ\leq n$, suffix-array queries are equivalent to prefix-select queries, and inverse-suffix-array queries are equivalent to prefix-special-rank queries. The reductions in both directions preserve all four standard measures up to constant factors: space, query time, preprocessing time, and preprocessing space. Unlike previous reductions, they incur no additive $O(\log\log n)$ query-time term. Thus, the corresponding prefix-query problems capture suffix-array and inverse-suffix-array access without asymptotic loss in any of the four measures.

0.47

Constant-Time Inverse Suffix Array Queries in Compact Space and Sublinear-Time Construction of Suffix Array Indexes

cs.DS ·2026-08-19 ·Dominik Kempa, Tomasz Kociumaka
theory similarity 0.63
Abstract

For a text $T\in[0..σ)^n$ with $2\leqσ\leq n$, its suffix array orders the suffix starting positions lexicographically, while its inverse suffix array maps each position to its suffix's rank. Since compressed suffix arrays and FM-indexes appeared in 2000, a central goal has been to support both queries in $O(n\logσ)$ bits. Thankachan recently reduced inverse suffix array query time to $O(\log\log n/\log\logσ)$, but constant time remained open. We give the first inverse suffix array structure with optimal space and query time: $O(n\logσ)$ bits and $O(1)$ time. For binary texts, this unconditionally separates the two queries for deterministic structures, since every $O(n)$-bit suffix array structure in the cell-probe model with $Θ(\log n)$-bit cells has worst-case query time $Ω(\log\log n/\log\log\log n)$. Construction is a second challenge: linear time can take $Θ(\log_σ n)$ times as long as reading the input or writing a compact index. Previously, sublinear construction was known for only one such index supporting both queries. In the word RAM with $Θ(\log n)$-bit words, we deterministically construct the new structure and two suffix array families from the packed text in $O(n\min(1,\logσ/\sqrt{\log n}))$ time. For $B\geq2$, the first family uses $O(n\logσ(1+\log_B\log_σn))$ bits and has query time $O(B(1+\log_B\log_σn))$, whereas the second uses $O(Bn\logσ(1+\log_B\log_σn))$ bits and has query time $O(1+\log_B\log_σn)$. Each has peak preprocessing space bounded by its index size. For binary texts, the second family matches the deterministic cell-probe time-space lower bound whenever $B\geq(\log\log n)^{Ω(1)}$, and, outside the slowest-query regimes, improving the deterministic construction time to $o(n/\sqrt{\log n})$ would yield an equally fast Dictionary Matching algorithm.

0.44

Concatenation Locality under Successive Adjacent Transpositions

cs.IT ·2026-11-01 ·Adelin Ataba, Aryeh Lev Zabokritskiy
theory similarity 0.61
Abstract · 32 pages

We study codes correcting up to $t\geq1$ successive adjacent transpositions, using block concatenation to support blockwise encoding and decoding. A fixed set $P$ of words of length $b$ over a $q$-symbol alphabet generates, for every $m$, the length-$mb$ code of all concatenations of $m$ words from $P$. For our explicit constructions, the prepared encoder and decoder depend only on the block parameters and are reused at every concatenation length. We first prove that correction at every concatenation length is certified by a single finite test at $2t+1$ blocks, and this test is tight over a $q$-symbol alphabet exactly when $\binom q2\geq2t$. For binary words and $b\geq2t+1$, we give an explicit construction with total redundancy at most $mt\log_2 b+O_t(m)$, matching the optimal per-block redundancy $t\log_2 b+O_t(1)$ among block sets correcting at every concatenation length. Among all binary $t$-correcting codes of length $mb$, the optimal total redundancy is $t\log_2(mb)+O_t(1)$. Using all concatenations of one block set makes our total redundancy grow linearly in $m$ and buys independent block encoding, with one encoder and decoder at every length. The construction encodes and decodes in time linear in $mb$ for fixed $b,t$, and recovers the $j$-th source block from the first $jb$ received symbols. We also prove that, whenever the length-$mb$ code corrects $t$ transpositions, the $j$-th source block is determined within $2tb$ received symbols beyond position $jb$, and that explicit binary block sets with rates tending to one as $b$ grows with $t$ fixed attain this bound in the worst case. Finally, we prove that every ordinary correcting code contains a constant fraction of its words whose arbitrary concatenations retain correction, for fixed $q,t$.

0.28

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.60
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

More RLBWT Tricks

cs.DS ·2026-09-30 ·Travis Gagie
theory similarity 0.59
Abstract

Backward search over the run-length compressed Burrows-Wheeler transform (RLBWT) of a pangenome takes one step per character of the pattern, even when long stretches of the pattern match material that occurs many times in the collection. Two-level indexing also indexes a parse of the collection, so that a search can take one step per phrase. We parse at closed syncmers, whose phrases are prefix-free, and add blocks of continuations: when each phrase of a stretch of the pattern is the smallest phrase that follows the previous one anywhere in the collection, the search crosses the whole stretch in one step, on the BWT of a sequence of block symbols. We prove that the three BWTs stay in the same order, so the search still returns exactly the BWT interval of every match, and we bound the extra space by terms that depend on the length of the collection only through the number of distinct closed syncmers. On chromosome 19 haplotypes from the Human Pangenome Reference Consortium, finding the maximal exact matches of length at least 1000 of two haplotypes, on both strands, takes 5.5 to 5.7 seconds with 16, 32 or 64 other individuals, while backward search on a run-length compressed suffix array of the same collection takes 40 to 60 seconds and grows with the collection. We compare this with suffix-tree path decompositions (STPDs): over the parse, an STPD is no faster and needs about twice the memory; over the text it is about 1.7 times faster but needs the whole text in memory, about five times the space; and the published STPD-index, which compresses its text with relative Lempel-Ziv, is 8 to 10 times slower. Keeping a toehold through all three kinds of steps lets the search also list every occurrence of every MEM, for about 2 more seconds.

0.10