Reportable Shortcuts with RLBWTs
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Reportable Shortcuts with RLBWTs".
Jane: Here's the gist of the paper. We show how to modify Baier’s tunnelling for the case in which we have a non-repetitive and relatively short reference for a highly repetitive and much longer text Given a pattern that mostly matches only one substring of the reference, we can use fairly small auxiliary data structures to speed up backward searching with an r-index for the whole text Pruning redundant reasoning tokens The paper introduces a method to modify Baier’s tunnelling technique for indexing highly repetitive texts by utilizing a reference string This modification allows for speeding up backward searching when the pattern mostly matches only one substring of the reference.
Tom: The core idea involves using fairly small auxiliary data structures to accelerate backward searching with an r-index for the entire text.
Jane: How the training signal is built The process begins by storing the reference R packed into O(n log σ / log N) words For each character R
j: in R, an interval in the BWT of T is considered based on conditions related to the longest common prefix between suffixes of T and substrings of R.
Tom: These intervals are called "tunnel entrances" and are stored using two sparse N-bit bit vectors marking starting and ending positions.
Title and authors: Tom: So, we're looking at this paper called Reportable Shortcuts with RLBWTs. It sounds really technical, but basically, they are trying to speed up searching in these massive text datasets that have a lot of repetition.
Jane: That makes sense. The title says "Reportable Shortcuts," which suggests they found some kind of trick or shortcut to make the search faster than what we usually do with standard indexing methods like FM-indexes or compressed suffix arrays.
Lu: Exactly, and the authors are tackling this by modifying an existing technique called Baier's tunnelling, specifically for cases where you have a non-repetitive reference string against a highly repetitive main text.
Meng: So it’s about using that small reference to make the search quicker when the main text is huge and repeating, right? I need to know if this actually helps with deployment costs at scale.
Lalam: The paper focuses on how to use this reference string to build auxiliary data structures that help speed up backward searching when a pattern mostly matches only one substring of that reference.
The paper's summary: Tom: Okay, so the core idea they present is using fairly small auxiliary data structures to accelerate backward searching with an r-index for the whole text. This seems like they are trying to get better query times than those standard FM-indexes provide in these highly repetitive scenarios.
Jane: What does that mean for a listener who isn't reading? It means when you search through a huge document, if you have this reference string, the system can use clever little lookup tables instead of doing all that heavy backward stepping repeatedly.
Lu: The methodology involves storing the reference packed into some words and then defining "tunnel entrances" in the Burrows-Wheeler Transform based on how long the common prefix between text suffixes and substrings of the reference is.
Meng: So they are essentially pre-calculating where things *might* match before you even start searching, which sounds like a lot of upfront processing. What is the complexity for building all these structures?
Lalam: The paper details building these structures by storing sparse N-bit bitvectors for the tunnel entrances and an L-bit bitvector for specific characters in those tunnels that don't satisfy certain conditions related to suffix arrays and the main text.
The paper's improvements: Tom: The gains come from using these auxiliary data structures to speed up pattern matching by checking sparse N-bit bitvectors in log log N time, which is a big improvement over what we might expect from just using the r-index alone.
Jane: They show that if a BWT interval for a suffix of your pattern is contained within one of these tunnel entrances, and you have some length L greater than l, you can compare parts of the pattern directly against the reference string in time proportional to l times log sigma divided by log N.
Lu: That comparison is fast because they use those bitvectors to narrow things down quickly, and if they match, they use rank queries on an L-bit bitvector to find the specific subinterval for your next step in O log log N time.
Meng: So if we are looking at a pattern that has a long substring matching only one substring of the reference, this whole system allows us to complete the search much faster than just falling back on backward stepping with an r-index alone.
Lalam: The main result is Theorem two, which states that you can store an r-index for the main text in O r log N bits along with all these auxiliary data structures totaling O n log N plus N p l over log one plus p l bits <ref:2609.06596#pg1,an r-index for the>.
Conclusion: Tom: So to wrap up, the main improvement is that backward searching in highly repetitive texts can be accelerated by checking sparse bitvectors in log log N time to see if a BWT interval is contained within a tunnel entrance.
Jane: They also show an algorithm to find the length of the longest suffix of a pattern that occurs in T and its position using total time proportional to b times log sigma plus m minus b times log sigma divided by n times log n plus log one plus epsilon n, where b is related to the number of backward steps <ref:2609.06596#pg1>.
Lu: They also manage to find the lexicographic rank for a suffix of T starting with a unique occurrence in O log one plus epsilon n time using an inverse suffix array query <ref:2609.06596#pg1>.
Meng: It seems like this approach provides a new pattern matching capability that allows finding the BWT interval for a long substring of the pattern in total time proportional to m minus s max plus l times log sigma plus s min times log sigma divided by n times log n plus m times log sigma divided by n.
Lalam: And they achieve this with auxiliary data structures that have a total size of O n log N plus N p l over p l bits, which is very efficient when the probability p l is close to zero, which it should be for certain conditions on the reference string.
Tom: So we've seen how using a non-repetitive reference can dramatically speed up r-index searches for highly repetitive texts by introducing these specific lookup structures.
Jane: It’s a powerful way to use auxiliary data to make those backward searches much more efficient when the underlying text has repeating patterns.
Lu: This work shows how combining Baier's tunnelling with an r-index can yield better query times when the pattern is mostly matching one substring of the reference string.
Meng: For production, it means we have a way to handle those massive datasets without needing impossibly large standard indexes for every possible repetition.
Lalam: This paper, Reportable Shortcuts with RLBWTs, provides a concrete way to use these methods for indexing highly repetitive texts and speeding up pattern matching significantly.
cs.DS
Submitted: 2026-09-06
Updated: 2026-11-04
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 74/100
The gist: We show how to modify Baier’s tunnelling for the case in which we have a non-repetitive and relatively short reference for a highly repetitive and much longer text Given a pattern that mostly…
Key concepts
- Baier’s Tunnelling
- This is an indexing technique adapted for highly repetitive texts by using a reference string. The modification allows the search to skip large parts of the text by leveraging specific matches found in the reference, speeding up backward searching.
- Tunnel Entrances
- These are intervals in the Burrows-Wheeler Transform (BWT) associated with characters from a short reference string R. They are defined based on conditions related to the longest common prefix between suffixes of T and substrings of R, helping to identify regions where matches might occur.
- Auxiliary Data Structures
- These are specialized structures, including sparse N-bit bitvectors and L-bit bitvectors, used to speed up the search. They allow checking if a pattern's BWT interval is contained in a tunnel entrance in logarithmic time, avoiding slow suffix array queries.
Terminology
Summary
We show how to modify Baier’s tunnelling for the case in which we have a non-repetitive and relatively short reference for a highly repetitive and much longer text Given a pattern that mostly matches only one substring of the reference, we can use fairly small auxiliary data structures to speed up backward searching with an r-index for the whole text
Pruning redundant reasoning tokens
The paper introduces a method to modify Baier’s tunnelling technique for indexing highly repetitive texts by utilizing a reference string This modification allows for speeding up backward searching when the pattern mostly matches only one substring of the reference. The core idea involves using fairly small auxiliary data structures to accelerate backward searching with an r-index for the entire text. p. 0
How the training signal is built
The process begins by storing the reference R packed into O(n log σ / log N) words For each character R[j] in R, an interval in the BWT of T is considered based on conditions related to the longest common prefix between suffixes of T and substrings of R. These intervals are called tunnel entrances
and are stored using two sparse N-bit bit vectors marking starting and ending positions. Additionally, a value j is stored with the tunnel entrance for R[j] to avoid SA queries. p. 1 Furthermore, a sparse L-bit bitvector is used to store information about characters BWT[i] in tunnel entrances that do not satisfy certain conditions related to SA and T. p. 2 Finally, for each character R[j], the endpoints of the corresponding tunnel exits
are stored as subintervals of the tunnel entrance for R[j-l].
Where the gains come from
The gains stem from using these auxiliary data structures to speed up pattern matching by checking sparse N-bit bitvectors in O(log log N) time If a BWT interval is contained within a tunnel entrance for some character R[j] and i > l, the comparison between R[j - l] and P[i - l] is performed in O(l log σ / log N) time. If they match, rank queries on the L-bit bitvector find the relevant subinterval of the tunnel exit for R[j] in O(log log N) time. p. 2 This process continues until a mismatch is found or a sufficiently long prefix of the suffix matches a single match in R. p. 3
Theorem and complexity
The paper concludes with Theorem 2, which states that given the specified conditions on R and T, one can store an r-index for T in O(r log N) bits along with auxiliary data structures totaling O(n log N + N pl / log 1pl) bits. This setup allows for pattern matching to be completed in total time O((m - smax + l) log σ + (smin + l)(log σ + log log N) + m log σ / log N), where smax and smin relate to the longest and shortest suffixes occurring exactly once in R. p. 3 This demonstrates how the structures can speed up pattern matching when a long substring of the pattern matches a single long substring of the reference. p. 3 The complexity analysis shows that this approach is effective even when a sufficiently long prefix of the suffix has a single match in R. p. 3 The paper also mentions that more sophisticated techniques can be used to speed up the search even when the suffix of P has no matches in R. p. 3
REFERENCES
[1] Lorraine A. K. Ayad, Gabriele Fici, Ragnar Groot Koerkamp, Grigorios Loukides, Rob Patro, Giulio Ermanno Pibiri, and Solon P. p. 3 Pissis. U-index: A universal indexing framework for matching long patterns. p. 3 In Proc. 23rd Symposium on Experimental Algorithms (SEA), 2025. p. 3
[2] Uwe Baier. p. 3 On undetected redundancy in the Burrows-Wheeler Transform. p. 3 In Proc. 29th Symposium on Combinatorial Pattern Matching (CPM), 2018. p. 3
[3] Andrej Bal´aˇz, Travis Gagie, Adri´an Goga, Simon Heumos, Gonzalo Navarro, Alessia Petescia, and Jouni Sir´en. p. 3 Wheeler maps. p. 3 In Proc. 16th Latin American Symposium on Theoretical Informatics (LATIN), 2024. p. 3
[4] Ruben Becker, Davide Cenzato, Travis Gagie, Ragnar Groot Koerkamp, Sung-Hwan Kim, Giovanni Manzini, and Nicola Prezza. p. 3 Compressing suffix trees by path decompositions. p. 3 In Proc. 53rd International Colloquium on Automata, Languages, and Programming (ICALP), 2026. p. 3
[5] Lore Depuydt, Travis Gagie, Ben Langmead, Giovanni Manzini, and Nicola Prezza. p. 3 Suffixient sets. p. 0 arXiv:2312. p. 301359, 2023. p. 3
[6] Parsa Eskandar, Benedict Paten, and Jouni Sir´en. p. 3 Lossless pangenome indexing using tag arrays. p. 3 Algorithms for Molecular Biology, 2026. p. 3
[7] Paolo Ferragina and Giovanni Manzini. p. 3 Indexing compressed text. p. 3 Journal of the ACM, 2005. p. 3
[8] Paolo Ferragina and Rossano Venturini. p. 3 A simple storage scheme for strings achieving entropy bounds. p. 3 Theoretical Computer Science, 2007. p. 3
[9] Travis Gagie, Gonzalo Navarro, and Nicola Prezza. p. 3 Fully functional suffix trees and optimal text searching in BWT-runs bounded space. p. 3 Journal of the ACM, 2020. p. 3
[10] Roberto Grossi and Jeffrey Scott Vitter. p. 4 Compressed suffix arrays and suffix trees with applications to text indexing and string matching. p. 4 SIAM Journal on Computing, 2005. p. 4
[11] Takaaki Nishimoto and Yasuo Tabei. p. 4 Optimal-time queries on BWT-runs compressed indexes. p. 4 In Proc. 48th International Colloquium on Automata, Languages, and Programming (ICALP), 2021. p. 4
[12] Jannik Olbrich and Enno Ohlebusch. p. 4 The TAG array of a multiple sequence alignment. p. 4 In Proc. 37th Symposium on Combinatorial Pattern Matching (CPM), 2026. p. 4
[13] Kunihiko Sadakane. p. 4 New text indexing functionalities of the compressed suffix arrays. p. 4 Journal of Algorithms, 2003. p. 4
[14] Mohsen Zakeri, Nathaniel K Brown, Travis Gagie, and Ben Langmead. p. 4 Movi 2: fast and space-efficient queries on pangenomes. p. 4 Bioinformatics, 2026. p. 4
--- Page 1 ---
Tunnelling with a reference
Travis Gagie
September 9, 2026
Abstract
We show how to modify Baier’s tunnelling for the case in which we have a non-repetitive and relatively short reference for a highly repetitive and much longer text Given a pattern that mostly matches only one substring of the reference, we can use fairly small auxiliary data structures to speed up backward searching with an r-index for the whole text
1 Introduction
Perhaps the most surprising thing about Gagie, Navarro and Prezza’s [9] r-index was that it supported locating in O(log log n) time, whereas the fastest locating time with a standard FM-index [7] or compressed suffix array (CSA) [10, 13] is O(logϵ σ n). In other words, we can achieve not only better compression when working with highly repetitive datasets, but also better query times Their result was quickly followed by Nishimoto and Tabei’s [11] proof that r-indexes can use table lookup instead of bitvectors, resulting in better locality and even faster queries (see also, e. p. 0g., [14]) Bal´aˇz et al. p. 0 [3] introduced tag arrays (see also [6, 12]) to allow r-indexes to quickly find all the columns in a multiple alignment where occurrences of a pattern start, rather than listing all the starting positions of those occurrences Finally, Depuydt et al. p. 0 [5] introduced suffixient sets (see also e. p. 0g., [4]) to replace backward stepping in the r-index by sequential scanning in the text None of these ideas make sense for non-repetitive texts Suffixient sets are just the latest way to gain an advantage by switching back and forth between the order of characters as they appear in a text, and the order of the suffixes that follow them CSAs use this switching more than textbook FM-indexes, which use it only during locating to find characters’ text positions from their positions in the Burrows-Wheeler Transform (BWT), but practical implementations of FM-indexes often switch earlier once they have found there are at most a few occurrences of a pattern As an illustration of this idea, we include the following lemma. p. 0 It is not meant to be competitive with the state of the art and could easily be improved with more sophisticated data structures, such as Ferragina and Venturini’s [8] data structure for supporting fast access to a compressed string but we hope it gives the flavour of how switching between text order and BWT order can be advantageous. p. 0
Lemma 1. Given a text T[1…n] over an alphabet of size σ ≤ n and a constant ϵ > 0, we can store T in O(n log σ) bits such that, when given a pattern P[1…m] packed into O(m log σ / log n) words with a suffix P[m − s + 1…m] that occurs only once in T, we can • find the length of the longest suffix of P that occurs in T (which may be m), • find the position in T of the unique occurrence of that suffix of P, • find the lexicographic rank of the suffix of T starting with that occurrence among all in O(s log σ + (m−s) log σ / log n + log1+ϵ n) time. p. 0 We need not be given s. p. 1
Proof. We store an FM-index for T with O(log1+ϵ n)-time access to the suffix array (SA) and inverse suffix array (ISA) of T, and a copy of T packed into O(n log σ / log n) words. p. 1 This takes a total of O(n log σ) bits When given P, we backward search for it until the BWT interval shrinks to a single character, after b ≤ s backward steps and O(b log σ) time We then perform an O(log1+ϵ n)-time SA query to find the position i in T of the unique occurrence of P[m − b + 1…m] We compare T[i − m + b…i − 1] to P[1…m - b] from right to left in blocks of O(log σ / log n) characters until we have determined that they are equal or found the rightmost character where they differ, in O(m-b) log σ / log n time This tells us the length of the longest suffix of P that occurs in T and the position in T of the unique occurrence of P[m − b + 1…m] We use an O(log1+ϵ n)-time ISA query to find the lexicographic rank of the suffix of T starting with that occurrence among all in O(log1+ϵ n) time This takes a total of O(b log σ + (m-b) log σ / log n + log1+ϵ n) time and, since b ≤ s and σ ≤ n, that is O(s log σ + (m-s) log σ / log n + log1+ϵ n)
Ayad et al. [1] already applied a more sophisticated version of Lemma 1 in their U-index for highly repetitive texts, but in this paper we will consider how Lemma 1 can be combined with Baier’s [2] idea of tunnelling (modified to use a reference and to allow substrings to leave tunnels in the middle) to give a new result for indexing highly repetitive texts
--- Page 2 ---
Suppose we have a reference R[1…n] for a highly repetitive text T[1…N] over an alphabet of size σ, with σ ≤ n ≪ N, such as a reference genome and a collection of genomes from the same species. Another genome from that species is likely to mostly match R, so a pattern P[1…m] drawn uniformly at random (with a low error rate) from that other genome is likely also to mostly match R We want to use this property to build a structure that speeds up r-indexes like the structure in Lemma 1 speeds up FM-indexes, but whose size is closer to n than N. p. 1 We start by storing R packed into O(n log σ / log N) words For each character R[j] in R we consider the interval in the BWT of T such that, for each character BWT[i] in the interval, • if d is the length of the longest common prefix of T[SA[i]…N] and R[j…n] then the length of the longest common prefix of T[SA[i]…N] and R[j′’…n] is strictly less than d for every j′ ≠ j, • T[SA[i]…SA[i]+l − 1] = R[j…j + l − 1] for a length l we will discuss later Such an interval for a character R[i] can be empty but, by the first constraint, the n intervals for the characters in R are disjoint. p. 1 We call these intervals tunnel entrances We store two sparse N-bit bit vectors, with the 1s in the first marking the starting positions of tunnel entrances, and the 1s in the other marking the ending positions of the tunnel entrances These take O(n log N) bits and let us check in O(log log N) time whether the BWT interval for a suffix of a pattern is contained within a tunnel entrance We also store the value j with the tunnel entrance for R[j], which will avoid the need for SA queries For 1 ≤ l ≤ N, let 1 − pl be the probability that a character BWT[i] in the tunnel entrance for R[j] has • SA[i] − l, j − l ≥ 1, • T[SA[i] − l…SA[i] - 1] = R[j - l…j - 1], taken over all the characters in all the tunnel entrances Assuming R is not itself repetitive, 1 − pl should be close to 1 and thus pl close to 0 for logσ n << l << n For the rest of this paper we consider l to be some such value. p. 1 Let L ≤ N be the total length of the tunnel entrances. p. 2 We store a sparse L-bit bitvector with 1s marking each character BWT[i] in a tunnel entrance for a character R[j] of R that does not have • SA[i] − l, j − l ≥ 1, • T[SA[i] − l…SA[i] - 1] = R[j - l…j - 1]. p. 2 Since exactly a pl fraction of the bitvector consists of 1s, by the definition of pl, this bitvector takes O(N pl / log 1pl) bits Finally, for each character R[j] in R we store the endpoints of the interval of the BWT containing characters l characters to the left in T of the BWT characters marked by 0s in the part of the L-bit bitvector covering the tunnel entrance for R[j]. p. 2 We call these intervals tunnel exits, and the tunnel exit for R[j] is a subinterval of the tunnel entrance for R[j - l] Storing the endpoints of all the tunnel exits takes a total of O(n log N) bits, and will avoid the need for ISA queries Considering all these data structures, we use O(n log N + N pl / log 1pl) bits (This is on top of the O(r log N) bits we need for an r-index for T that our data structures will speed up, where r is the number of runs in the BWT of T. p. 2) In the next section we explain how we use the tunnel entrances and exits to speed up pattern matching
--- Page 3 ---
Given a pattern P[1…m] packed into O(m log σ / log N) words, we perform a standard backward search for P with the r-index for T, except that after finding the BWT interval for each suffix P[i…m] of P we check the sparse N-bit bitvectors in O(log log N) time to see if that interval is contained in the tunnel entrance for some character R[j] in R If so and i > l, we compare R[j - l…j - 1] to P[i - l…m-1] in O(l log σ / log N) time If they are equal then we use the rank queries on the L-bit bitvector to find the subinterval of the tunnel exit for R[j] that is the BWT interval for P[i - l…m] in O(log log N) time Since the tunnel exit for R[j] is a subinterval of the tunnel entrance for R[j - l], we can continue like this until we find a mismatch between P and R. At that point we fall back on backward stepping with the r-index (now without checking for tunnel entrances) After some calculation, this gives us the following theorem. p. 2
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Backward searching for patterns in highly repetitive texts can be accelerated by checking sparse bitvectors in O(log log N) time to see if a BWT interval is contained within a tunnel entrance, as described in Section 3.
-
The improved system can find the length of the longest suffix of a pattern that occurs in T and its position in T using an algorithm with total time O (b log sigma + (m-b) log sigma / log n + log1+epsilon n), where b is related to the number of backward steps.
-
The system can find the lexicographic rank of a suffix of T starting with a unique occurrence among all suffixes of T in O(log1+epsilon n) time, utilizing an ISA query.
-
A new pattern matching capability allows finding the BWT interval for a long substring P[i-lmax+1 to i] in total time O ((m - smax + l) log sigma + (smin + l)(log sigma + log log N) + m log sigma / log N), when a long substring of the pattern matches a single long substring of the reference.
-
The system can speed up r-index searches by using auxiliary data structures that have a total size of O n log N + N p l log 1 / p l bits, where p l is usually close to 0, when working with highly repetitive texts and a reference R.
Sources
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time