# Text indexing for long patterns using locally consistent anchors

Lorraine A. K. Ayad  Brunel University London, London, UK  Grigorios Loukides
King’s College London, London, UK  Solon P. Pissis  CWI, Amsterdam, The
Netherlands  Vrije Universiteit, Amsterdam, The Netherlands

###### Abstract

In many real-world database systems, a large fraction of the data is
represented by strings: sequences of letters over some alphabet. This is
because strings can easily encode data arising from different sources. It is
often crucial to represent such string datasets in a compact form but also to
_simultaneously_ enable fast pattern matching queries. This is the classic
text indexing problem. The four absolute measures anyone should pay attention
to when designing or implementing a text index are: (i) index space; (ii)
query time; (iii) construction space; and (iv) construction time.
Unfortunately, however, most (if not all) widely-used indexes (e.g., suffix
tree, suffix array, or their compressed counterparts) are not optimized for
all four measures simultaneously, as it is difficult to have the best of all
four worlds. Here, we take an important step in this direction by showing that
text indexing with sampling based on locally consistent anchors (lc-anchors)
offers remarkably good performance in all four measures, when we have at hand
a lower bound $\ell$ on the length of the queried patterns — which is arguably
a quite reasonable assumption in practical applications. Specifically, we
improve on a recently proposed index that is based on _bidirectional string
anchors_ (bd-anchors), a new type of lc-anchors, by: (i) introducing a
randomized counterpart of bd-anchors which outperforms bd-anchors; (ii)
designing an average-case linear-time algorithm to compute (the randomized)
bd-anchors; and (iii) developing a semi-external-memory implementation and an
internal-memory implementation to construct the index in _small space_ using
near-optimal work. Our index offers average-case guarantees. In our
experiments using real benchmark datasets, we show that it compares favorably
based on the four measures to all classic indexes: (compressed) suffix tree;
(compressed) suffix array; and the FM-index. Notably, we also present a
counterpart of our index with worst-case guarantees based on the lc-anchors
notion of _partitioning sets_. To the best of our knowledge, this is the first
index achieving the best of all worlds in the regime where we have at hand a
lower bound $\ell$ on the length of the queried patterns.

##  1 Introduction

In many real-world database systems, including bioinformatics systems [92],
Enterprise Resource Planning (ERP) systems [85], or Business Intelligence (BI)
systems [97], a large fraction of the data is represented by strings:
sequences of letters over some alphabet. This is because strings can easily
encode data arising from different sources such as: nucleic acid sequences
read by sequencing machines (e.g., short or long DNA reads); natural language
text generated by humans (e.g., description or comment fields); or identifiers
generated by machines (e.g., URLs, email addresses, IP addresses). Given the
ever increasing size of such datasets, it is crucial to represent them
compactly [17] but also to _simultaneously_ enable fast pattern matching
queries. This is the classic text indexing problem [52, 28, 88]. More
formally, _text indexing_ asks to preprocess a string $S$ of length $n$ over
an alphabet $\Sigma$ of size $\sigma$, known as the _text_ , into a compact
data structure that supports efficient pattern matching queries; i.e.,
_decide_ if a _pattern_ $P$ occurs or not in $S$ or _report_ the set of all
positions in $S$ where an occurrence of $P$ starts.

###  1.1 Motivation and related work

A considerable amount of algorithmic research has been devoted to text indexes
over the past decades [98, 81, 32, 64, 34, 50, 54, 8, 27, 86, 67, 9, 41, 77].
This is mainly due to the fact that myriad string processing tasks (see [52,
2] for comprehensive reviews) require fast access to the substrings of $S$.
These tasks rely on such text indexes, which typically arrange the suffixes of
$S$ lexicographically in an ordered tree or in an ordered array. The former is
known as the _suffix tree_ [98] and the latter is known as the _suffix array_
[81]. These are classic data structures, which occupy $\Theta(n)$ words of
space (or, equivalently, $\Theta(n\log n)$ bits) and can count the number of
occurrences of $P$ in $S$ in $\mathcal{\tilde{O}}(|P|)$ time111The
$\mathcal{\tilde{O}}(\cdot)$ notation suppresses polylogarithmic factors.. The
time for reporting is $\mathcal{O}(1)$ per occurrence for both structures.
Thus, if a pattern $P$ occurs occ times in $S$, the total query time for
reporting is $\mathcal{\tilde{O}}(|P|+\textsf{occ})$.

From early days, and in contrast to the traditional data structure literature,
where the focus is on space-query time trade-offs, the main focus in text
indexing has been on the construction time. That was until the breakthrough
result of Farach [32], who showed that suffix trees (and thus suffix arrays,
indirectly) can be constructed in $\mathcal{O}(n)$ time when $\Sigma$ is an
integer alphabet of size $\sigma=n^{\mathcal{O}(1)}$. After Farach’s result,
more and more attention had been given to reducing the space of the index via
compression techniques. This is due to the fact that, although the space is
linear in the number of words, there is an $\mathcal{O}(\log_{\sigma}n)$
factor blowup when we consider the actual text size, which is
$n\lceil\log\sigma\rceil$ bits. This factor is not negligible when $\sigma$ is
considerably smaller than $n$. For instance, the space occupied by the suffix
tree of the whole human genome, even with a very efficient implementation [71]
is about $40$GB, whereas the genome occupies less than $1$GB. To address the
above issue, Grossi and Vitter [50] and Ferragina and Manzini [34], and later
Sadakane [93], introduced, respectively, the _compressed suffix array_ (CSA),
the _FM-index_ , and the _compressed suffix tree_ (CST). These data structures
occupy $\mathcal{O}(n\log\sigma)$ bits, instead of $\mathcal{O}(n\log n)$
bits, at the expense of a factor of $\mathcal{O}(\log^{\epsilon}n)$ penalty in
the query time, where $\epsilon>0$ is an arbitrary predefined constant. These
indexes have the dominant role in some of the most widely used bioinformatics
tools [73, 74, 72]; while mature and highly engineered implementations of
these indexes are available through the sdsl-lite library of Gog et al. [44].

Nowadays, as the data volume grows rapidly, construction space is as well
becoming crucial for several string processing tasks [9, 68]. Suffix arrays
can be constructed in optimal time using $\mathcal{O}(1)$ words of extra space
with the algorithm of Franceschini and Muthukrishnan [38] for general
alphabets or with the algorithms of Goto [47] or Li et al. [75] for integer
alphabets. _Extra_ refers to the required space except for the space of $S$
and the output. Grossi and Vitter’s [50] original algorithm for constructing
the CSA takes $\mathcal{O}(n\log\sigma)$ time using $\mathcal{O}(n\log n)$
bits of construction space. Hon et al. [54] showed an
$\mathcal{O}(n\log\log\sigma)$-time construction reducing the construction
space to $\mathcal{O}(n\log\sigma)$ bits. More recently, Belazzougui [8] and,
independently, Munro et al. [86], improved the time complexity of the CSA/CST
construction to $\mathcal{O}(n)$ using $\mathcal{O}(n\log\sigma)$ bits of
construction space. Recently, Kempa and Kociumaka [68] have presented a new
data structure that occupies $\mathcal{O}(n\log\sigma)$ bits, can be
constructed in $\mathcal{O}(n\log\sigma/\sqrt{\log n})$ time using
$\mathcal{O}(n\log\sigma)$ bits of construction space, and has the same query
time as the CSA and the FM-index.

This completes the four absolute measures anyone should pay attention to when
designing or implementing a text index: space (index size); query time;
construction time; and construction space.

Unfortunately, however, most (if not all) widely-used indexes are not
optimized for all four measures _simultaneously_ , as it is difficult to have
the best of all four worlds; e.g.:

The _suffix array_ [81] supports very fast pattern matching queries; it can be
constructed very fast using very little construction space; but then it
occupies $\Theta(n\log n)$ bits of space and that _in any case_.

The _CSA_ [96], the _CST_ [93], or the _FM-index_ [34] occupy
$\mathcal{O}(n\log\sigma)$ bits of space; they can be constructed very fast
using $\mathcal{O}(n\log\sigma)$ bits of construction space; but then they
answer pattern matching queries much less efficiently than the suffix array.

###  1.2 Our contributions

The purpose of this paper is to show that text indexing with _locally
consistent anchors_ (lc-anchors, in short) offers remarkably good performance
in all four measures, when we have at hand a lower bound $\ell$ on the length
of the queried patterns. This is arguably a quite reasonable assumption in
practical applications. For instance, in bioinformatics [57, 99, 76], the
length of sequencing reads (patterns) ranges from a few hundreds to 30
thousand [76]. Even when at most $k$ errors must be accommodated for matching,
at least one out of $k+1$ fragments must be matched exactly. In natural
language processing, the queried patterns can also be long [95]. Examples of
such patterns are queries in question answering systems [51], _description
queries_ in TREC datasets [13, 3], and representative phrases in documents
[83]. Similarly, a query pattern can be long when it encodes an entire
document (e.g., a webpage in the context of deduplication [53]), or machine-
generated messages [58].

Informally, given a string $S$ and an integer $\ell>0$, the goal is to sample
some of the positions of $S$ (the lc-anchors), so as to simultaneously satisfy
the following:

  * •

_Property 1 (approximately uniform sampling):_ Every fragment of length at
least $\ell$ of $S$ has a representative position sampled. This ensures that
any pattern $P$, $|P|\geq\ell$, will not be missed during search.

  * •

_Property 2 (local consistency):_ Exact matches between fragments of length at
least $\ell$ of $S$ are preserved unconditionally by having the same
(relative) representative positions sampled. This ensures that similarity
between similar strings of length at least $\ell$ will be preserved during
search.

Loukides and Pissis [77] have recently introduced _bidirectional string
anchors_ (bd-anchors, in short), a new type of lc-anchors. The set
$\mathcal{A}_{\ell}(S)$ of bd-anchors of order $\ell$ of a string $S$ of
length $n$ is the set of starting positions of the leftmost lexicographically
smallest rotation of every length-$\ell$ fragment of $S$ (see Section 2 for a
formal definition). The authors have shown that bd-anchors are
$\mathcal{O}(n/\ell)$ in expectation [77, 78] and that can be constructed in
$\mathcal{O}(n)$ worst-case time [77]. Loukides and Pissis have also proposed
a text index, which is based on $\mathcal{A}_{\ell}(S)$ and occupies linear
extra space in the size $|\mathcal{A}_{\ell}(S)|$ of the sample; the index can
be constructed in $\mathcal{\tilde{O}}(n)$ time and can report all occ
occurrences of any pattern $P$ of length $|P|\geq\ell$ in $S$ in
$\mathcal{\tilde{O}}(|P|+\textsf{occ})$ time (see Section 2 for a formal
theorem). The authors of [77] have also implemented their index and presented
some very promising experimental results (see also [78]).

We identify here two important aspects for improving the construction of the
bd-anchors index: (i) for computing the set $\mathcal{A}_{\ell}(S)$, which is
required to construct the index, Loukides and Pissis implement a simple
$\Theta(n\ell)$-time algorithm, because their $\mathcal{O}(n)$-time worst-case
algorithm seems too complicated to implement and unlikely to be efficient in
practice [77]; (ii) their index construction implementation uses $\Theta(n)$
construction space _in any case_ , which is much larger than the expected size
$|\mathcal{A}_{\ell}(S)|=\mathcal{O}(n/\ell)$ of the index.

Here, we improve on the index proposed by Loukides and Pissis [77] by
addressing these aspects as follows:

  * •

We introduce the notion of randomized bd-anchors; the randomized counterpart
of bd-anchors. Informally, the set $\mathcal{A}^{\text{ran}}_{\ell}(S)$ of
_randomized bd-anchors_ of order $\ell$ of a string $S$ of length $n$ is the
set of starting positions of the leftmost “smallest” rotation of every
length-$\ell$ fragment of $S$ (see Section 4 for a formal definition). The
order of rotations is defined based on a random hash function _and_ ,
additionally, on the standard lexicographic order. We show that randomized bd-
anchors are $\mathcal{O}(n/\ell)$ in expectation.

  * •

We design a novel average-case $\mathcal{O}(n)$-time algorithm to compute
either $\mathcal{A}_{\ell}(S)$ or $\mathcal{A}^{\text{ran}}_{\ell}(S)$. To
achieve this, we use minimizers [94, 91], another well-known type of lc-
anchors, as anchors to compute $\mathcal{A}_{\ell}(S)$ (or
$\mathcal{A}^{\text{ran}}_{\ell}(S)$) after carefully setting the sampling
parameters. We employ longest common extension (LCE) queries [67] on $S$ to
compare anchored rotations (i.e., rotations of $S$ starting at minimizers) of
fragments of $S$ efficiently. The fact that minimizers are
$\mathcal{O}(n/\ell)$ in expectation lets us realize the average-case
$\mathcal{O}(n)$-time computation of $\mathcal{A}_{\ell}(S)$ (or
$\mathcal{A}^{\text{ran}}_{\ell}(S)$).

  * •

We propose a semi-external-memory and an internal-memory implementation to
construct the index in small space using near-optimal work when the set of bd-
anchors is given. We first compute $\mathcal{A}_{\ell}(S)$ (or
$\mathcal{A}^{\text{ran}}_{\ell}(S)$) using $\mathcal{O}(\ell)$ space using
the aforementioned algorithm. For the semi-external-memory implementation, we
show that if we have $\mathcal{A}_{\ell}(S)$ (or
$\mathcal{A}^{\text{ran}}_{\ell}(S)$) in internal memory and the suffix array
of $S$ in external memory, it suffices to scan the suffix array sequentially
to deduce the information required to construct the index thus using
$\mathcal{O}(\ell+|\mathcal{A}_{\ell}(S)|)$ space. For the internal-memory
implementation, we use _sparse suffix sorting_ [5] on $\mathcal{A}_{\ell}(S)$
(or $\mathcal{A}^{\text{ran}}_{\ell}(S)$) to construct the index in
$\mathcal{O}(\ell+|\mathcal{A}_{\ell}(S)|)$ space.

  * •

We present an extensive experimental evaluation using real benchmark datasets.
First, we show that our new algorithm for computing $\mathcal{A}_{\ell}(S)$
(or $\mathcal{A}^{\text{ran}}_{\ell}(S)$) is _more than two orders of
magnitude faster_ as $\ell$ increases than the simple $\Theta(n\ell)$-time
algorithm, while using a very similar amount of memory. We also show that
randomized bd-anchors outperform bd-anchors _in all measures_ : construction
time, construction space, and sample size. We then go on to examine the index
construction based on the above four measures. The results show that, for long
patterns, the index constructed using randomized bd-anchors and our improved
construction algorithms compares favorably to all classic indexes (implemented
using sdsl-lite): (compressed) suffix tree; (compressed) suffix array; and the
FM-index. For instance, our index offers about $27\%$ faster query time, for
all datasets on average, for all $\ell\in[32,1024]$, compared to the suffix
array (which performs best among the competitors in this measure), while
occupying up to two orders of magnitude less space. Also, our index occupies
up to $5\times$ less space on average over all datasets, for $\ell=1024$,
compared to the FM-index (which performs best among the competitors in this
measure), while being up to one order of magnitude faster in query time. As
another example, our index on the full human genome occupies 11MB for
$\ell=2^{14}$ and answers queries more than $72\times$ faster than the FM-
index, which occupies more than 1GB.

  * •

The above algorithms are based on an _average-case_ analysis. In the worst
case, however, $|\mathcal{A}_{\ell}(S)|$ (or
$|\mathcal{A}^{\text{ran}}_{\ell}(S)|$) are in $\Theta(n)$. This implies that
our index does not offer satisfactory worst-case guarantees. Motivated by
this, we also present a counterpart of our index with _worst-case_ guarantees
based on the lc-anchors notion of _partitioning sets_ [70]. This construction
is mainly of theoretical interest. However, we stress that, to the best of our
knowledge, it is the first index achieving the best of all worlds in the
regime where we have at hand a lower bound $\ell$ on the length of the queried
patterns. Specifically, this index occupies $\mathcal{O}(n/\ell)$ space, it
can be constructed in near-optimal time using $\mathcal{O}(n/\ell)$ space, and
it supports near-optimal pattern matching queries.

###  1.3 Other related work

The connection of lc-anchors to text indexing and other string-processing
applications is not new. The perhaps most popular lc-anchors in practical
applications are _minimizers_ , which have been introduced independently by
Schleimer et al. [94] and by Roberts et al. [91] (see Section 2 for a
definition). Although minimizers have been mainly used for sequence comparison
[57], Grabowski and Raniszewski [48] showed how minimizers can be used to
sample the suffix array – see also [26], which uses an alphabet sampling
approach. Another well-known notion of lc-anchors is _difference covers_ ,
which have been introduced by Burkhardt and Kärkkäinen [19] for suffix array
construction in small space (see also [79]). Difference covers play also a
central role in the elegant linear-time suffix array construction algorithm of
Kärkkäinen et al. [64]; and they have been used in other string processing
applications [21, 12]. Another very powerful type of lc-anchors is _string
synchronizing sets_ , which have been recently proposed by Kempa and Kociumaka
[67], for constructing, among others, an optimal data structure for LCE
queries (see also [31]). String synchronizing sets have applications in
designing sublinear-time algorithms for classic string problems [22, 24],
whose textbook linear-time solutions rely on suffix trees. Another type of lc-
anchors, very much related to string synchronizing sets, is the notion of
_partitioning sets_ [16, 70].

###  1.4 Paper organization and differences from the conference version

In Section 2, we present the necessary definitions and notation, a brief
overview of classic text indexes, as well as some existing results on
minimizers and bd-anchors. In Section 3, we present a brief overview of the
index proposed by Loukides and Pissis [77]. In Section 4, we describe
randomized bd-anchors, our new sampling mechanism, in detail. In Section 5, we
improve the construction of the index of Section 3 by presenting: (i) our fast
algorithm for (randomized) bd-anchors computation (see Section 5.1); and (ii)
the index construction in small space using near-optimal work (see Section
5.2). In Section 6, we present the counterpart of our index offering worst-
case guarantees. In Section 7, we provide the full details of our
implementations, and in Section 8, we present our extensive experimental
evaluation. We conclude this paper in Section 9.

A preliminary version of this paper was announced at PVLDB 2023 [4]. Therein
we identified two ways for potentially improving the _construction time_ of
the index: (i) design a new sampling mechanism that reduces the number of
minimizers to potentially improve the construction of bd-anchors; (ii) plug
sparse suffix sorting in the semi-external-memory implementation to make it
work fully in internal memory thus potentially improving the construction of
the index. In response (to (i)), we introduce here the notion of randomized
bd-anchors (see Section 4). It is well-known than randomized minimizers have
usually a lower density than their lexicographic counterparts [100]; the
former can also be computed faster and using less space as they can be
computed using a rolling hash function [65]. Unfortunately, for bd-anchors, it
does not make sense to maintain the hash value of the rotations in every
window. Consider the hash value of the rotation starting at position $i$ in
the window starting at position $j<i$; and consider that this $i$ is the
smallest rotation in $S[j\mathinner{.\,.}j+\ell-1]$ according to the hash
function used. The hash value of the prefix $S[i\mathinner{.\,.}j+\ell-1]$ of
the rotation is in general completely different than the one of
$S[i\mathinner{.\,.}j+\ell]$: the substring obtained by appending the next
letter. Thus when shifting from window $S[j\mathinner{.\,.}j+\ell-1]$ to
window $S[j+1\mathinner{.\,.}j+\ell]$, the hash value of
$S[i\mathinner{.\,.}j+\ell]$ changes completely and thus _the minimizer
position will likely change at the next window_. This is why we partition the
rotations in two parts: the first one is of length $r$; and the second one is
of length $\ell-r$. We compute the _hash value_ of the former and the
_lexicographic rank_ of the latter. These two integers form a pair. The
rotation sampled is the rotation with the smallest such pair (in lexicographic
order). This lets us _simultaneously_ exploit the benefits of randomized
minimizers (small sample, small space, and fast computation) and bd-anchors
(effective tie-breaking). For (ii), we plug the sparse suffix sorting
implementation of Ayad et al. [5] in our semi-external-memory implementation
(see Section 5).

Since our new implementations (see Section 7) based on the aforementioned two
changes (randomized bd-anchors and internal-memory implementation) have
dramatically improved the construction in the preliminary version [4] (which
was based on lexicographic bd-anchors and on external memory), _the
experimental section is also completely new_ (see Section 8): we have re-
conducted all experiments from scratch; we have re-plotted the results, and a
new description has been added.

Section 6, presenting the counterpart of our index with worst-case guarantees,
is also completely new.

##  2 Preliminaries

An _alphabet_ $\Sigma$ is a finite set of elements called _letters_ ; we
denote by $\sigma$ the size $|\Sigma|$ of $\Sigma$. A _string_
$S=S[1\mathinner{.\,.}n]$ is a sequence of letters over some alphabet
$\Sigma$; we denote by $|S|=n$ the length of $S$. The fragment
$S[i\mathinner{.\,.}j]$ of $S$ is an _occurrence_ of the underlying
_substring_ $P=S[i]\ldots S[j]$. We also write that $P$ occurs at _position_
$i$ in $S$ when $P=S[i]\ldots S[j]$. A prefix of $S$ is a fragment of $S$ of
the form $S[1\mathinner{.\,.}j]$ and a suffix of $S$ is a fragment of $S$ of
the form $S[i\mathinner{.\,.}n]$. Given a string $S$ and an integer $1\leq
i\leq|S|$, we define $S[i\mathinner{.\,.}|S|]S[1\mathinner{.\,.}i-1]$ to be
the _$i$ th rotation_ of $S$. Given a string $S$ of length $n$, we denote by
$\overleftarrow{S}$ the _reverse_ $S[n]\ldots S[1]$ of $S$.

Text Indexing
Preprocess: A string $S$ of length $n$ over an integer alphabet of size
$\sigma=n^{\mathcal{O}(1)}$. Query: Given a string $P$ of length $m$, report
all positions $i\iff P=S[i\mathinner{.\,.}i+m-1]$.

#### Classic text indexes

For a string $S$ of length $n$ over an ordered alphabet of size $\sigma$, the
_suffix array_ $\textsf{SA}[1\mathinner{.\,.}n]$ stores the permutation of
$\\{1,\ldots,n\\}$ such that $\textsf{SA}[i]$ is the starting position of the
$i$th lexicographically smallest suffix of $S$. The standard application of SA
is text indexing, in which we consider $S$ to be the _text_ : given any string
$P[1\mathinner{.\,.}m]$, known as the _pattern_ , the suffix array of $S$
allows us to report all occ occurrences of $P$ in $S$ using only
$\mathcal{O}(m\log n+\textsf{occ})$ operations [81]. We perform binary search
in SA resulting in a range $[s,e)$ of suffixes of $S$ having $P$ as a prefix.
Then, $\textsf{SA}[s\mathinner{.\,.}e-1]$ contains the starting positions of
all occurrences of $P$ in $S$. The SA is often augmented with the LCP array
[81] storing the length of longest common prefixes of lexicographically
adjacent suffixes (i.e., consecutive entries in the SA). In this case,
reporting all occ occurrences of $P$ in $S$ can be done in $\mathcal{O}(m+\log
n+\textsf{occ})$ time by avoiding to compare $P$ with suffixes of $S$ from
scratch during binary search [81] (see [27, 36, 89] for subsequent
improvements). The suffix array occupies $\Theta(n)$ space and it can be
constructed in $\mathcal{O}(n)$ time, when $\sigma=n^{\mathcal{O}(1)}$, using
$\mathcal{O}(n)$ space [32]. Given SA of $S$, we can compute the LCP array of
$S$ in $\mathcal{O}(n)$ time [66].

Given a set $\mathcal{F}$ of strings, the _compacted trie_ of these strings is
the trie obtained by compressing each path of nodes of degree one in the trie
of the strings in $\mathcal{F}$, which takes $\mathcal{O}(|\mathcal{F}|)$
space [84]. Each edge in the compacted trie has a label represented as a
fragment of a string in $\mathcal{F}$. The _suffix tree_ of $S$, which we
denote by $\textsf{ST}(S)$, is the compacted trie of the suffixes of $S$ [98].
Assuming $S$ ends with a unique terminating symbol, every leaf in
$\textsf{ST}(S)$ represents a suffix $S[i\mathinner{.\,.}n]$ and is decorated
by index $i$. The set of indices stored at the leaf nodes in the subtree
rooted at node $v$ is the _leaf-list_ of $v$, and we denote it by $LL(v)$.
Each edge in $\textsf{ST}(S)$ is labelled with a nonempty substring of $S$
such that the path from the root to the leaf annotated with index $i$ spells
the suffix $S[i\mathinner{.\,.}n]$. The substring of $S$ spelled by the path
from the root to node $v$ is the _path-label_ of $v$, and we denote it by
$L(v)$. Given any pattern $P[1\mathinner{.\,.}m]$, $\textsf{ST}(S)$ allows us
to report all occ occurrences of $P$ in $S$ using only
$\mathcal{O}(m\log\sigma+\textsf{occ})$ operations. We simply spell $P$ from
the root of $\textsf{ST}(S)$ (to access edges by the first letter of their
label, we use binary search) until we arrive (if possible) at the first node
$v$ such that $P$ is a prefix of $L(v)$. Then all occ occurrences (starting
positions) of $P$ in $S$ are $LL(v)$. The suffix tree occupies $\Theta(n)$
space and it can be constructed in $\mathcal{O}(n)$ time, when
$\sigma=n^{\mathcal{O}(1)}$, using $\mathcal{O}(n)$ space [32]. To improve the
query time to the optimal $\mathcal{O}(m+\textsf{occ})$ we can use
randomization to construct a perfect hash table [39] to access edges by the
first letter of their label in $\mathcal{O}(1)$ time.

Let $S$ be a string of length $n$. Given two integers $1\leq i,j\leq n$, we
denote by $\textsf{LCP}_{S}(i,j)$ the length of the longest common prefix
(LCP) of $S[i\mathinner{.\,.}n]$ and $S[j\mathinner{.\,.}n]$. When $S$ is over
an integer alphabet of size $\sigma=n^{\mathcal{O}(1)}$, we can construct a
data structure in $\mathcal{O}(n/\log_{\sigma}n)$ time that answers
$\textsf{LCP}_{S}(i,j)$ queries in $\mathcal{O}(1)$ time [67].

#### Lc-anchors

Given a string $S$ of length $n$, two integers $w,k>0$, and the $i$th
length-$(w+k-1)$ fragment $F=S[i\mathinner{.\,.}i+w+k-2]$ of $S$, the _$(w,k)$
-minimizers_ of $F$ are defined as the positions $j\in[i,i+w)$ where a
lexicographically minimal length-$k$ substring of $F$ occurs [91]. The set
$\mathcal{M}_{w,k}(S)$ of $(w,k)$-minimizers of $S$ is defined as the set of
$(w,k)$-minimizers of each fragment $S[i\mathinner{.\,.}i+w+k-2]$, for all
$i\in[1,n-w-k+2]$.

######  Example 1 (Minimizers).

Let $S=\texttt{aacaaacgcta}$ and $w=k=3$. We consider fragments of length
$w+k-1=5$. The first fragment is aacaa. The lexicographically minimal
length-$k$ substring is aac, starting at position $1$, so we add position $1$
to $\mathcal{M}_{3,3}(S)$. The second fragment is acaaa. The lexicographically
minimal length-$k$ substring is aaa, starting at position $4$,so we add
position $4$ to $\mathcal{M}_{3,3}(S)$. The third fragment, caaac, and fourth
fragment, aaacg, have aaa as the lexicographically minimal length-$k$
substring, so $\mathcal{M}_{3,3}(S)$ does not change. The fifth fragment is
aacgc. The lexicographically minimal length-$k$ substring is aac, starting at
position $5$, and so we add position $5$ to $\mathcal{M}_{3,3}(S)$. The sixth
fragment is acgct. The lexicographically minimal length-$k$ substring is acg,
starting at position $6$, and so we add position $6$ to
$\mathcal{M}_{3,3}(S)$. The seventh fragment is cgcta. The lexicographically
minimal length-$k$ substring is cgc, starting at position $7$, and so we add
position $7$ to $\mathcal{M}_{3,3}(S)$. Thus
$\mathcal{M}_{3,3}(S)=\\{1,4,5,6,7\\}$.

######  Lemma 1 ([100]).

If $S$ is a string of length $n$, randomly generated by a memoryless source
over an alphabet of size $\sigma\geq 2$ with identical letter probabilities,
then the expected size of $\mathcal{M}_{w,k}(S)$ is $\mathcal{O}(n/w)$ if and
only if $k\geq\log_{\sigma}w+\mathcal{O}(1)$.

######  Lemma 2 ([77]).

For any string $S$ of length $n$ over an integer alphabet of size
$n^{\mathcal{O}(1)}$ and integers $w,k>0$, the set $\mathcal{M}_{w,k}$ can be
computed in $\mathcal{O}(n)$ time.

Loukides and Pissis defined the following alternative notion of lc-anchors
[77].

######  Definition 1 (Bidirectional anchor).

Given a string $F$ of length $\ell>0$, the _bidirectional anchor_ (bd-anchor)
of $F$ is the lexicographically minimal rotation $j\in[1,\ell]$ of $F$ with
minimal $j$. The set of order-$\ell$ bd-anchors of a string $S$ of length
$n>\ell$, for some integer $\ell>0$, is defined as the set
$\mathcal{A}_{\ell}(S)$ of bd-anchors of $S[i\mathinner{.\,.}i+\ell-1]$, for
all $i\in[1,n-\ell+1]$.

######  Example 2 (Bd-anchors).

Let $S=\texttt{aacaaacgcta}$ and $\ell=5$. We consider fragments of length
$\ell=5$. The first fragment is aacaa. We need to consider all of its
rotations and select the leftmost lexicographically minimal. All rotations of
aacaa are: aacaa, acaaa, caaaa, aaaac, and aaaca. We thus select aaaac, which
starts at position $4$, and add position $4$ to $\mathcal{A}_{5}(S)$. The
second fragment is acaaa. All rotations of acaaa are: acaaa, caaaa, aaaac,
aaaca, and aacaa. We thus select aaaac, which starts at position $4$, and so
we do not need to add position $4$ to $\mathcal{A}_{5}(S)$. The third fragment
is caaac. All rotations of caaac are: caaac, aaacc, aacca, accaa, and ccaaa.
We thus select aaacc, which starts at position $4$, and so we do not need to
add position $4$ to $\mathcal{A}_{5}(S)$. The fourth fragment is aaacg, which
is also the lexicographically minimal rotation. This rotation starts at
position $4$, and so we do not need to add position $4$ to
$\mathcal{A}_{5}(S)$. The fifth fragment is aacgc, which is also the
lexicographically minimal rotation. This rotation starts at position $5$, and
so we add position $5$ to $\mathcal{A}_{5}(S)$. The sixth fragment is acgct,
which is also the lexicographically minimal rotation. This rotation starts at
position $6$, and so we add position $6$ to $\mathcal{A}_{5}(S)$. The seventh
fragment is cgcta. The lexicographically minimal rotation of this fragment is
acgct, which starts at position $11$, and so we add position $11$ to
$\mathcal{A}_{5}(S)$. Thus $\mathcal{A}_{5}(S)=\\{4,5,6,11\\}$.

The bd-anchors notion was also parameterized by Loukides et al. [78] according
to the following definition.

######  Definition 2 (Reduced bidirectional anchor).

Given a string $F$ of length $\ell>0$ and an integer $0\leq r\leq\ell-1$, we
define the _reduced bidirectional anchor_ of $F$ as the lexicographically
minimal rotation $j\in[1,\ell-r]$ of $F$ with minimal $j$. The set of
order-$\ell$ reduced bd-anchors of a string $S$ of length $n>\ell$ is defined
as the set $\mathcal{A}_{\ell,r}(S)$ of reduced bd-anchors of
$S[i\mathinner{.\,.}i+\ell-1]$, for all $i\in[1,n-\ell+1]$.

Informally, when using the reduced bd-anchor mechanism, we neglect the $r$
rightmost rotations from the sampling process.

######  Example 3 (Reduced bd-anchors).

Let $S=\texttt{aacaaacgcta}$, $\ell=5$, and $r=1$. Recall from Example 2 that
$\mathcal{A}_{5}(S)=\\{4,5,6,11\\}$. To see the difference between bd-anchors
and reduced bd-anchors, consider the seventh (last) fragment of length
$\ell=5$ of $S$. This fragment is cgcta and its rotations are: cgcta, gctac,
ctacg, tacgc, and acgct. The lexicographically minimal rotation is acgct and
this is why $11\in\mathcal{A}_{5}(S)$. In the case of reduced bd-anchors we
are asked to neglect the $r=1$ rightmost rotations, and so the only candidates
are: cgcta, gctac, ctacg, and tacgc. Out of these, the lexicographically
minimal rotation is cgcta, which starts at position $7$, and this is why
$\mathcal{A}_{5,1}(S)=\\{4,5,6,7\\}$.

######  Lemma 3 ([77, 78]).

If $S$ is a string of length $n$, randomly generated by a memoryless source
over an alphabet of size $\sigma\geq 2$ with identical letter probabilities,
then, for any integer $\ell>0$, the expected size of $\mathcal{A}_{\ell,r}(S)$
with $r=\lceil 4\log\ell/\log\sigma\rceil$ is in $\mathcal{O}(n/\ell)$.

######  Lemma 4 ([77, 78]).

For any string $S$ of length $n$ over an integer alphabet of size
$n^{\mathcal{O}(1)}$ and integers $\ell,r>0$, the set
$\mathcal{A}_{\ell,r}(S)$ can be computed in $\mathcal{O}(n)$ time.

##  3 The index

(a) The $\mathcal{I}_{\ell,r}(S)$ index for $S=\texttt{aacaaacgcta}$,
$\ell=5$, and $r=1$.

(b) Querying $P=\texttt{acaaa}$.

Figure 1: Let $S=\texttt{aacaaacgcta}$, $\ell=5$, and $r=1$. We have that
$\mathcal{A}_{5,1}(S)=\\{4,5,6,7\\}$, and thus the indexed suffixes and
reversed suffixes of $S$ are as shown in (a). Assume that we have a query
pattern $P=\texttt{acaaa}$. We first find the reduced bd-anchor of
$P[1\mathinner{.\,.}\ell]$ for $\ell=5$ and $r=1$, which is $j=3$: the minimal
lexicographic rotation is aaaac. We then split $P$ in
$\overleftarrow{P[1\mathinner{.\,.}3]}=\texttt{aca}$ and
$P[3\mathinner{.\,.}|P|]=\texttt{aaa}$, and search
$\overleftarrow{P[1\mathinner{.\,.}3]}=\texttt{aca}$ in
$\mathcal{T}^{L}_{\ell,r}$ and $P[3\mathinner{.\,.}|P|]=\texttt{aaa}$ in
$\mathcal{T}^{R}_{\ell,r}$. The search induces a rectangle, which encloses all
the occurrences of $P$ in $S$, as shown in (b). Indeed,
$P=S[2\mathinner{.\,.}6]=\texttt{acaaa}$: the fragment $S[2\mathinner{.\,.}6]$
is anchored at position $4$.

Loukides and Pissis [77] proposed the following text index, which is based on
(reduced [78]) bd-anchors. Fix string $S$ of length $n$ over an integer
alphabet of size $n^{\mathcal{O}(1)}$ as well as $\ell$ (and $r$). Given
$\mathcal{A}_{\ell,r}(S)$ we construct two compacted tries: one for strings
$S[i\mathinner{.\,.}n]$, for all $i\in\mathcal{A}_{\ell,r}(S)$, which we
denote by $\mathcal{T}^{R}_{\ell,r}(S)$; and one for strings
$\overleftarrow{S[1\mathinner{.\,.}i]}$, for all
$i\in\mathcal{A}_{\ell,r}(S)$, which we denote by
$\mathcal{T}^{L}_{\ell,r}(S)$. We also construct a 2D range reporting data
structure [20] over $|\mathcal{A}_{\ell,r}(S)|$ points $(x,y)$, where $x$ is
the lexicographic rank of $S[i\mathinner{.\,.}n]$ and $y$ is the lexicographic
rank of $\overleftarrow{S[1\mathinner{.\,.}i]}$, for all
$i\in\mathcal{A}_{\ell,r}(S)$. Upon a query $P$ of length $|P|\geq\ell$, we
find the (reduced) bd-anchor of $P[1\mathinner{.\,.}\ell]$, say $j$, which
gives $P[j\mathinner{.\,.}|P|]$ and $\overleftarrow{P[1\mathinner{.\,.}j]}$.
We search the former in $\mathcal{T}^{R}_{\ell,r}$ and the latter in
$\mathcal{T}^{L}_{\ell,r}$. This search induces a rectangle (inspect Figure 1,
for an example), which we use to query the 2D range reporting data structure.
The reported points are all occurrences of $P$ in $S$. We denote the resulting
index by $\mathcal{I}_{\ell,r}(S)$. Loukides and Pissis showed the following
result [77, 78].

######  Theorem 1 ([77, 78]).

Given any string $S$ of length $n$ over an integer alphabet of size
$n^{\mathcal{O}(1)}$ and integers $\ell,r>0$, the index
$\mathcal{I}_{\ell,r}(S)$ occupies $\mathcal{O}(|\mathcal{A}_{\ell,r}(S)|)$
extra space and reports all occ occurrences of any pattern $P$ of length
$|P|\geq\ell$ in $S$ in $\mathcal{\tilde{O}}(|P|+\textsf{occ})$ time.
Moreover, the index $\mathcal{I}_{\ell,r}(S)$ can be constructed in
$\mathcal{\tilde{O}}(n)$ time.

_Extra_ refers to the $n\lceil\log\sigma\rceil$ bits required to store $S$.
Alternatively one could use $nH_{0}(S)+o(nH_{0}(S))+o(n)$ bits without any
penalty [6, 10], where $H_{0}(S)$ is the _zeroth-order entropy_ of $S$. Note
that the same index can be constructed for any lc-anchors; e.g., for
minimizers.

##  4 Randomized reduced bidirectional string anchors

We introduce the notion of randomized reduced bd-anchors by injecting Karp-
Rabin (KR) fingerprints [65] to the notion of reduced bd-anchors [78]. This is
analogous to the idea of using randomization to select minimizers [94] instead
of using the standard lexicographic total order [91]. In practice,
implementing a randomized minimizers mechanism is straightforward via using a
hash function (e.g., KR fingerprints). The other benefit of randomized
minimizers is that they usually have lower density than their lexicographic
counterparts [100].

Unfortunately, it is not as straightforward to inject randomization to
(reduced) bd-anchors. Intuitively, this is because bd-anchors wrap around the
window. We next explain how this can be achieved by using a mix of
lexicographic total order and KR fingerprints. Importantly, our experiments
show a clear superiority (lower density) of this new randomized notion over
the deterministic (lexicographic) counterpart.

Let us start by introducing KR fingerprints. Let $S$ be a string of length $n$
over an integer alphabet. Let $p$ be a prime and choose $r\in[0,p-1]$
uniformly at random. The KR fingerprint of $S[i\mathinner{.\,.}j]$ is defined
as:

$\phi_{S}(i,j)=\sum^{j}_{k=i}S[k]r^{j-k}\mod p.$

Clearly, if $S[i\mathinner{.\,.}i+\ell]=S[j\mathinner{.\,.}j+\ell]$ then
$\phi_{S}(i,i+\ell)=\phi_{S}(j,j+\ell)$. On the other hand, if
$S[i\mathinner{.\,.}i+\ell]\neq S[j\mathinner{.\,.}j+\ell]$ then
$\phi_{S}(i,i+\ell)\neq\phi_{S}(j,j+\ell)$ with probability at least
$1-\ell/p$ [29]. Since we are comparing only substrings of equal length, the
number of different possible substring comparisons is less than $n^{3}$. Thus,
for any constant $c\geq 1$, we can set $p$ to be a prime larger than
$\max(|\Sigma|,n^{c+3})$ to make the KR fingerprint function perfect (i.e., no
collisions) with probability at least $1-n^{-c}$ (with high probability). Any
KR fingerprint of $S$ or $p$ fits in one machine word of $\Theta(\log n)$
bits. In our methods, the length $j-i+1$ of the substrings of $S$ considered
will be fixed, hence the quantity $r^{j-i+1}\mod p$ needs to be computed only
once.

The definition of randomized reduced bd-anchors (Definition 3) is a bit
involved. We will thus start with some intuition to facilitate the reader’s
comprehension. Given $\ell$ and $r$ (exactly as in the reduced bd-anchors
case) and a fragment $F$ of $S$, we select as _candidates_ , the
$(\ell-r,r+1)$-minimizers of $F$ based on the total order induced by the KR
fingerprints. If there exists only one candidate selected, then this is the
randomized reduced bidirectional anchor of $F$. If there are many candidates,
then we select the leftmost lexicographically smallest rotation out of all the
rotations starting right after the last position of the candidates. The
candidate whose rotation is selected is then selected as the randomized
reduced bidirectional anchor of $F$. We next formalize this intuition.

######  Definition 3 (Randomized reduced bidirectional anchor).

Given a string $F$ of length $\ell>0$ and an integer $0\leq r\leq\ell-1$, we
define the _randomized reduced bidirectional anchor_ of $F$ as the starting
position of the length-$(r+1)$ fragment of $F$ with the minimal KR
fingerprint. If there are $h>1$ such fragments
$F[i_{1}\mathinner{.\,.}j_{1}],\ldots,F[i_{h}\mathinner{.\,.}j_{h}]$ in $F$
(i.e., $h$ fragments that share the same minimal KR fingerprint), then we
resolve the ties by choosing $j-(r+1)$ as the randomized reduced bidirectional
anchor of $F$, where $j$ is the lexicographically minimal rotation from
$\\{j_{1}+1,\ldots,j_{h}+1\\}$ with minimal $j$. The set of order-$\ell$
randomized reduced bidirectional anchors of a string $S$ of length $n>\ell$ is
defined as the set $\mathcal{A}^{\text{ran}}_{\ell,r}(S)$ of randomized
reduced bd-anchors of $S[i\mathinner{.\,.}i+\ell-1]$, for all
$i\in[1,n-\ell+1]$.

######  Example 4 (Randomized reduced bd-anchor).

Let $F=\texttt{aacaaacgcta}$ of length $\ell=11$ and $r=2$. We need to
consider the following set of length-$3$ substrings of $F$:

$\\{\texttt{aac},\texttt{aca},\texttt{caa},\texttt{aaa},\texttt{acg},\texttt{cgc},\texttt{gct},\texttt{cta}\\}.$

Assume that $\phi_{F}(1,3)$, that is, the KR fingerprint of
$F[1\mathinner{.\,.}3]=F[5\mathinner{.\,.}7]=\texttt{aac}$, is the smallest
one among the KR fingerprints of all length-$3$ substrings of $F$. We have
that $h=2$ because aac occurs at two positions: $1$ and $5$. To resolve the
tie, we need to consider the rotations starting at positions in $\\{4,8\\}$.
These are: aaacgctaaac and gctaaacaaac. The former $(j=4)$ is the
lexicographically smallest, and so we select $j-(r+1)=4-(2+1)=1$ as the
randomized reduced bd-anchor of $F$.

Randomized reduced bd-anchors are a new type of lc-anchors (see Section 2).
Indeed, like minimizers [101] and (reduced) bd-anchors [78], it is
straightforward to prove that randomized reduced bd-anchor samples enjoy the
following two useful properties (see Section 1):

  * •

_Property 1 (approximately uniform sampling)_

  * •

_Property 2 (local consistency)_

We denote by $\mathcal{M}^{\text{ran}}_{w,k}(S)$ the set of $(w,k)$-minimizers
of $S$ when the underlying total order on length-$k$ substrings is determined
randomly (e.g., by a random hash function). The following lemma is known.

######  Lemma 5 ([100]).

If $S$ is a string of length $n$, randomly generated by a memoryless source
over an alphabet of size $\sigma\geq 2$ with identical letter probabilities,
then the expected size of $\mathcal{M}^{\text{ran}}_{w,k}(S)$ with
$k>(3+\epsilon)\log_{\sigma}(w+1)$ is in $\mathcal{O}(n/w)$, for any
$\epsilon>0$.

The following lemma follows directly from Lemma 5 and the fact that by
construction
$|\mathcal{A}^{\text{ran}}_{\ell,r}(S)|\leq|\mathcal{M}^{\text{ran}}_{w,k}(S)|$,
where $k=r+1$ and $w=\ell-r$.

######  Lemma 6.

If $S$ is a string of length $n$, randomly generated by a memoryless source
over an alphabet of size $\sigma\geq 2$ with identical letter probabilities,
then, for any integer $\ell>0$, the expected size of
$\mathcal{A}^{\text{ran}}_{\ell,r}(S)$ with $r=\lceil
4\log\ell/\log\sigma\rceil$ is in $\mathcal{O}(n/\ell)$.

Comparing Lemma 6 with Lemma 3, we see that this new notion of bd-anchors has
the same expected size in the worst case as reduced bd-anchors. However, as
mentioned before, our experiments show a clear superiority (lower density) of
this new randomized notion over the deterministic (lexicographic) counterpart.
In the next section, we show that both notions can be computed in linear time
with the same technique.

##  5 Improving the index

In this section, we improve the construction of the index
$\mathcal{I}_{\ell,r}(S)$ (Theorem 1) focusing on two aspects: (i) the fast
computation of (randomized) reduced bd-anchors (see Section 5.1); and (ii) the
index construction in small space using near-optimal work (see Section 5.2).
With _small_ , we mean space that is close to the index size.

###  5.1 Computing bd-anchors in linear time

Recall that the first step to construct the $\mathcal{I}_{\ell,r}(S)$ index is
to compute the set $\mathcal{A}_{\ell,r}(S)$ of reduced bd-anchors of $S$.
Loukides and Pissis [77, 78] showed a worst-case linear-time algorithm to
compute $\mathcal{A}_{\ell,r}(S)$ (Lemma 4). Although this algorithm is
optimal in the worst case, it seems quite complex to implement and it is
unlikely to be efficient in practice. The worst-case linear-time algorithm for
computing $\mathcal{A}_{\ell,r}(S)$ relies on a data structure introduced by
Kociumaka in [69]. The latter data structure relies heavily on the
construction of _fusion trees_ [40], and hence it is mostly of theoretical
interest: it is widely accepted that naive solutions can be more practical
than such sophisticated data structures – see [30] and references therein.
That is why Loukides and Pissis have instead proposed and implemented a simple
$\Theta(n\ell)$-time algorithm to compute $\mathcal{A}_{\ell,r}(S)$ in their
experiments [77]. Here we give a novel average-case linear-time algorithm to
compute $\mathcal{A}_{\ell,r}(S)$. In the worst case, the algorithm runs in
$\mathcal{O}(n\ell)$ time as the simple algorithm from [77] does.

Let us remark that the same technique (with very small differences) can be
used to compute $\mathcal{A}^{\text{ran}}_{\ell,r}(S)$, the set of randomized
reduced bd-anchors of $S$. We will highlight these differences at the end of
this section.

#### Main idea

We use $(w,k)$-minimizers as anchors to compute reduced bd-anchors of order
$\ell$ after carefully setting parameters $w$ and $k$. We employ
$\textsf{LCP}_{S}(i,j)$ queries to compare anchored rotations (i.e., rotations
of $S$ starting at $(w,k)$-minimizers) of fragments of $S$ efficiently. The
fact that $(w,k)$-minimizers are $\mathcal{O}(n/\ell)$ in expectation lets us
realize $\mathcal{O}(n)$ time on average.

Let us start with the following simple fact.

######  Fact 1.

For any string $F$ of length $\ell>0$, the reduced bd-anchor of $F$, for any
$1\leq r\leq\ell-1$, is an $(\ell-r,r+1)$-minimizer of $F$.

###### Proof.

Let $j$ be the reduced bd-anchor of $F$: the lexicographically smallest
rotation of $F$ with minimal $j\in[1,\ell-r]$. By definition,
$F[j\mathinner{.\,.}|F|]$ is of length at least $r+1$ and there cannot be
another $j^{\prime}$ such that $F[j^{\prime}\mathinner{.\,.}j^{\prime}+r]$ is
lexicographically smaller than $F[j\mathinner{.\,.}j+r]$. Since
$\ell=w+k-1\implies w=\ell-r$, $j$ is an $(\ell-r,r+1)$-minimizer of $F$. ∎

######  Example 5 (Cont’d from Example 3).

The set $\mathcal{M}_{w,k}(S)$ of minimizers for $w=\ell-r=4$ and $k=r+1=2$ is
$\mathcal{M}_{4,2}(S)=\\{1,4,5,6,7\\}$. Since any reduced bd-anchor for
$\ell=5$ and $r=1$ is a $(4,2)$-minimizer of $S$,
$\mathcal{A}_{5,1}(S)=\\{4,5,6,7\\}\subseteq\mathcal{M}_{4,2}(S)$.

In particular, Fact 1 implies that, for any string $S$ of length $n$ and
integers $w,k>0$, the set of $(w,k)$-minimizers in $S$ is a superset of the
set of reduced bd-anchors of order $\ell=w+k-1$ with $r=k-1$. Thus, we will
use $(w,k)$-minimizers (computed by means of Lemma 2) to compute reduced bd-
anchors by setting $w=\ell-r$ and $k=r+1$. The following lemma is crucial for
the efficiency of our algorithm. The main idea is to use LCP queries to
quickly identify suitable substrings (of the input rotations) that are then
compared, in order to determine the lexicographically smallest rotation.

######  Lemma 7.

For any string $F$ and two positions $i$ and $j$ on $F$, we can determine
which of the rotations $i$ or $j$ is the smaller lexicographically in the time
to answer three $\textsf{LCP}_{F}$ queries and three letter comparisons in
$F$.

Figure 2: Illustration of Lemma 7.

###### Proof.

Assume without loss of generality that $i<j$ (inspect Figure 2). We first ask
for the length $\lambda_{1}$ of the LCP of $F[i\mathinner{.\,.}|F|]$ and
$F[j\mathinner{.\,.}|F|]$. If $\lambda_{1}<|F|-j+1$, then we simply compare
$F[i\mathinner{.\,.}i+\lambda_{1}]$ and $F[j\mathinner{.\,.}j+\lambda_{1}]$ to
find the answer. If $\lambda_{1}=|F|-j+1$ (see top part (a)), we ask for the
length $\lambda_{2}$ of the LCP of $F[i+\lambda_{1}\mathinner{.\,.}|F|]$ and
$F$. If $\lambda_{2}<j-i$, then we simply compare
$F[i+\lambda_{1}\mathinner{.\,.}i+\lambda_{1}+\lambda_{2}]$ and
$F[1\mathinner{.\,.}1+\lambda_{2}]$ to find the answer. If $\lambda_{2}=j-i$
(see middle part (b)), we ask for the length $\lambda_{3}$ of the LCP of $F$
and $F[j-i+1\mathinner{.\,.}|F|]$. If $\lambda_{3}<j-i$, then we simply
compare $F[1\mathinner{.\,.}1+\lambda_{3}]$ and
$F[j-1\mathinner{.\,.}j-1+\lambda_{3}]$ to find the answer. Otherwise,
rotation $i$ of $F$ is equal to rotation $j$ of $F$ (see bottom part (c)). ∎

We next use Lemma 7 as a building block to obtain Lemma 8, the main lemma used
by our algorithm.

######  Lemma 8.

Let $D$ be a string of length $|D|\geq\ell$. Let $A$ be a set of $d$ positions
on $D$ such that for every range $[i,i+\ell-1]\subseteq[1,|D|]$, $1\leq
i\leq|D|-\ell+1$, there exists at least one element $j\in A:j\in[i,i+\ell-1]$.
Given a data structure for answering $\textsf{LCP}_{D}$ queries in
$\mathcal{O}(1)$ time, we can find the smallest lexicographic rotation $j$ in
every length-$\ell$ fragment of $D$, such that $j\in A$ and $j$ is minimal in
$\mathcal{O}(d|D|)$ total time.

###### Proof.

First we sort the elements of $A$ in increasing order using radix sort in
$\mathcal{O}(|D|)$ time. Then for every fragment
$F=D[i\mathinner{.\,.}i+\ell-1]$ of length $\ell$ of $D$,
$i\in[1,|D|-\ell+1]$, we consider pairs of elements from $A$ that are in
$[i,i+\ell-1]$. We can consider these pairs from left to right because the
elements of $A$ have been sorted. For any two elements, we perform an
application of Lemma 7, which takes $\mathcal{O}(1)$ time, and maintain the
leftmost smallest rotation. Inspect Figure 3.

Figure 3: Illustration of three applications of Lemma 7 on $F$. We mark the
elements of $A$ in red circles.

Since we have at most $|D|$ length-$\ell$ fragments in $D$ and at most $d-1$
pairs that we consider per fragment, the total time to process all fragments
is $\mathcal{O}(d|D|)$. ∎

Figure 4: Illustration of the decomposition of $S$. We mark the
$(w,k)$-minimizers in red circles.

######  Theorem 2.

Given a string $S$ of length $n$, randomly generated by a memoryless source
over an alphabet $\Sigma$ of size $\sigma\geq 2$ with identical letter
probabilities, and an integer $\ell>0$, the expected number of reduced bd-
anchors of order $\ell$ for $r=\lceil 4\log\ell/\log\sigma\rceil$ in $S$ is
$\mathcal{O}(n/\ell)$. Moreover, if $\Sigma$ is an integer alphabet of size
$\sigma=n^{\mathcal{O}(1)}$, $\mathcal{A}_{\ell,r}(S)$ can be computed in
$\mathcal{O}(n)$ time on average.

###### Proof.

The first part is merely Lemma 3 from [78].

For the second part, we employ the so-called standard trick to conceptually
decompose $S$ in $q$ fragments $F$ each of length $|F|=2\ell$ overlapping by
$\ell$ positions (apart perhaps from the last one). Inspect Figure 4. We
compute $\mathcal{M}_{w,k}(S)$ for $w=\ell-r$ and $k=r+1$. This can be done in
$\mathcal{O}(n)$ time by Lemma 2 [77]. We also construct an $\textsf{LCP}_{S}$
data structure in $\mathcal{O}(n)$ time [67]. Let us denote by $d_{i}$ the
number of $(w,k)$-minimizers in the $i$th fragment $F_{i}$ of $S$ as per the
above decomposition of $S$. We apply Lemma 8 with $D=F_{i},d=d_{i}$ and
$A=\mathcal{M}_{w,k}(F_{i})$. This takes $d_{i}|F_{i}|=\mathcal{O}(d_{i}\ell)$
time. Note that $q=\Theta(n/\ell)$. Then the total work of the algorithm, by
Lemma 8, is bounded _on average_ by:

$n+\ell d_{1}+\ell d_{2}+\ldots+\ell d_{q}=n+\ell(d_{1}+d_{2}+\ldots+d_{q})$

$\leq n+2\ell\cdot\mathcal{M}_{w,k}(S)=\mathcal{O}(n)$.

The last inequality holds by the fact that the fragments overlap by $\ell$
positions, which means that $d_{i}$ will generally be considered twice (see
Figure 4), and by Lemma 1, which gives an expected asymptotic upper bound on
the number of $(w,k)$-minimizers in $S$. The algorithm is correct by Fact 1. ∎

In the worst case (e.g., $S=\texttt{a}^{n}$),
$\mathcal{M}_{w,k}(S)=\Theta(n)$, and so the algorithm of Theorem 2 takes
$\Theta(n\ell)$ time.

Let us now highlight the differences for computing the set of randomized
reduced bd-anchors. The following lemma follows directly from Lemma 2 and the
fact that the KR fingerprints for all fixed-length fragments of $S$ can be
computed in $\mathcal{O}(n)$ time [65].

######  Lemma 9.

For any string $S$ of length $n$ over an integer alphabet and integers
$w,k>0$, the set $\mathcal{M}^{\text{ran}}_{w,k}(S)$ can be computed in
$\mathcal{O}(n)$ time.

Theorem 3 follows directly from Theorem 2 by making the following two changes
in the proof of Theorem 2:

  * •

Replace Lemma 3 by Lemma 6.

  * •

Replace Lemma 2 by Lemma 9.

######  Theorem 3.

Given a string $S$ of length $n$, randomly generated by a memoryless source
over an alphabet $\Sigma$ of size $\sigma\geq 2$ with identical letter
probabilities, and an integer $\ell>0$, the expected number of randomized
reduced bd-anchors of order $\ell$ for $r=\lceil 4\log\ell/\log\sigma\rceil$
in $S$ is $\mathcal{O}(n/\ell)$. Moreover,
$\mathcal{A}^{\text{ran}}_{\ell,r}(S)$ can be computed in $\mathcal{O}(n)$
time on average.

###  5.2 Index construction in small space

In this section, we show the index construction in small space using near-
optimal work. Similar to the previous section, the same technique (with very
small differences) can be used to construct the index for reduced bd-anchors
and for randomized reduced bd-anchors of $S$. We will highlight these
differences appropriately.

Note that a _straightforward_ implementation of the index
$\mathcal{I}_{\ell,r}(S)$ (see also [77]) requires $\Theta(n)$ space in any
case. In particular, this is because the SA and LCP array of $S$ (and
$\overleftarrow{S}$) are required for: (i) the implementation of Lemma 2 [77]
(reduced bd-anchors); and (ii) the construction of
$\mathcal{T}^{R}_{\ell,r}(S)$ and $\mathcal{T}^{L}_{\ell,r}(S)$ [77].

However, the size of $\mathcal{I}_{\ell,r}(S)$ can be asymptotically smaller
than $\Theta(n)$. In fact, Theorem 1 tells us that the size of
$\mathcal{I}_{\ell,r}(S)$ is $\mathcal{O}(|\mathcal{A}_{\ell,r}(S)|)$, which
is expected to be $\mathcal{O}(n/\ell)$. Note that
$|\mathcal{A}_{\ell,r}(S)|=\Omega(n/\ell)$ in any case [77], so we cannot hope
for less memory. The goal of this section is to show that we can construct
$\mathcal{I}_{\ell,r}(S)$ _efficiently_ using only
$\mathcal{O}(\ell+|\mathcal{A}_{\ell,r}(S)|)$ space (and external memory).
(Note that in practical applications $\ell$ never exceeds $n/\ell$ and so
$\ell$ is negligible.) We will show two constructions: one utilizing internal
and external memory; and another one utilizing only internal memory.

In the standard _external memory_ (EM) model [96], with internal memory (RAM)
size $M$ and disk block size $B$, the standard I/O complexities are:
$\textsf{scan}(n)=n/B$, which is the complexity of scanning $n$ elements
sequentially; and $\textsf{sort}(n)=(n/B)\log_{M/B}(n/B)$, which is the
complexity of sorting $n$ elements [96]. _Semi-EM_ model is a relaxation of
the EM model, in which we are allowed to store some of the data in internal
memory [1]. We proceed in four steps: In Step 1, we compute the set
$\mathcal{A}_{\ell,r}(S)$ using $\mathcal{O}(\ell)$ extra space; in Step 2, we
compute the SA and LCP array of $S$ in the EM model using existing algorithms;
in Step 3, we construct $\mathcal{T}^{R}_{\ell,r}(S)$ and
$\mathcal{T}^{L}_{\ell,r}(S)$ in the semi-EM model (by having
$\mathcal{A}_{\ell,r}(S)$ in internal memory); in Step 4, we construct the 2D
range reporting data structure in internal memory using existing algorithms.
The only difference of the second construction is that it skips Step 2, and
directly constructs $\mathcal{T}^{R}_{\ell,r}(S)$ and
$\mathcal{T}^{L}_{\ell,r}(S)$ utilizing only internal memory.

We next describe in detail how every step is implemented using near-optimal
work.

#### Step 1

We make use of $\mathcal{O}(\ell)$ extra space. Specifically, we use Theorem 2
to construct $\mathcal{A}_{\ell,r}(S)$ via considering fragments of $S$ of
length-$2\ell$ (apart perhaps from the last one), overlapping by $\ell$
positions, without significantly increasing the time. If the size of the
alphabet of a fragment $F$ is not polynomial in $\ell$ (i.e., $F$ consists of
large integers), we use $\mathcal{\tilde{O}}(\ell)$ time instead of
$\mathcal{O}(\ell)$ by first sorting the letters of $F$, and then assigning
each letter to a rank in $\\{1,\ldots,2\ell\\}$. This clearly does not affect
the lexicographic rank of rotations. Thus the total time to construct
$\mathcal{A}_{\ell,r}(S)$ is $\mathcal{\tilde{O}}(n)$: there are
$\mathcal{O}(n/\ell)$ fragments and each one is processed in
$\mathcal{\tilde{O}}(\ell)$ time. We finally implement
$\mathcal{A}_{\ell,r}(S)$ as a perfect hash table [39], denoted by
$\mathcal{H}_{\ell,r}(S)$, which we keep in RAM. This is done in
$\mathcal{O}(|\mathcal{A}_{\ell,r}(S)|)$ time; and so the total time is
$\mathcal{\tilde{O}}(n)$. The only difference for randomized reduced bd-
anchors is that we use Theorem 3 instead to construct
$\mathcal{A}^{\text{ran}}_{\ell,r}(S)$. (The alphabet size plays no role in
Theorem 3.)

#### Step 2

We compute the SA and LCP array of $S$ in external memory using $M$ words of
internal memory and disk block size $B$. To this end we can use existing
algorithms, which compute the two arrays simultaneously [64, 15]; these
algorithms are optimal with respect to internal work
$\mathcal{O}(n\log_{M/B}(n/B))$ and I/O complexity
$\mathcal{O}((n/B)\log_{M/B}(n/B))$—see also [62, 59, 60, 63, 61]. We also
compute the SA and LCP array of $\overleftarrow{S}$, the reverse of $S$,
analogously. Clearly this step is the same for randomized reduced bd-anchors.
For the internal memory construction, this step is omitted.

#### Step 3

We construct the two compacted tries $\mathcal{T}^{R}_{\ell,r}(S)$ and
$\mathcal{T}^{L}_{\ell,r}(S)$ with the aid of four arrays, each of size
$|\mathcal{A}_{\ell,r}(S)|$: RSA; RLCP; LSA; and LLCP. Specifically, RSA
(Right SA) stores a permutation of $\mathcal{A}_{\ell,r}(S)$ such that
$\textsf{RSA}[i]$ is the starting position of the $i$th lexicographically
smallest suffix of $S$ with $\textsf{RSA}[i]\in\mathcal{A}_{\ell,r}(S)$.
$\textsf{RLCP}[i]$ array (Right LCP array) stores the length of the LCP of
$\textsf{RSA}[i-1]$ and $\textsf{RSA}[i]$. LSA and LLCP array are defined
analogously for $\overleftarrow{S}$. Let us show how we construct RSA and
RLCP; the other case for LSA and LLCP array is symmetric. To compute these
arrays we use the SA and the LCP array of $S$ constructed in Step 2. We scan
the SA and the LCP array of $S$ sequentially and sample them using the hash
table $\mathcal{H}_{\ell,r}(S)$ constructed in Step 1. Let us suppose that we
want to sample the $k$th value after reading $\textsf{SA}[i]$ and
$\textsf{LCP}[i]$. This is possible using $\mathcal{O}(1)$ words of memory. If
$\textsf{SA}[i]$ is in $\mathcal{H}_{\ell,r}(S)$, which we check in
$\mathcal{O}(1)$ time, we set $\textsf{RSA}[k]=\textsf{SA}[i]$. It is also
well known that for any $i_{1}<j_{2}$ the length of the LCP between
$S[\textsf{SA}[i_{1}]\mathinner{.\,.}n]$ and
$S[\textsf{SA}[i_{2}]\mathinner{.\,.}n]$ is the minimum value lying in
$\textsf{LCP}[i_{1}+1],\ldots,\textsf{LCP}[i_{2}]$. Since we scan also the LCP
array simultaneously, we maintain the value we need to store in
$\textsf{RLCP}[k]$. Finally we increment $k$ and $i$ by one. Scanning RSA and
RLCP takes $\mathcal{O}(n/B)$ I/Os. Using RSA and RLCP we can construct
$\mathcal{T}^{R}_{\ell,r}(S)$ in $\mathcal{O}(|\mathcal{A}_{\ell,r}(S)|)$ time
using a folklore algorithm (cf. [66]). We construct
$\mathcal{T}_{\ell,r}^{L}(S)$ analogously from LSA and LLCP. For the internal-
memory construction, Step 3 can be implemented in $\mathcal{\tilde{O}}(n)$
time using $\mathcal{O}(|\mathcal{A}_{\ell,r}(S)|)$ space assuming read-only
random access to $S$. This can be achieved by using any algorithm for _sparse
suffix sorting_ [55, 43, 16, 5, 70]. Clearly for randomized reduced bd-
anchors, we use $\mathcal{A}^{\text{ran}}_{\ell,r}(S)$ instead of
$\mathcal{A}_{\ell,r}(S)$.

#### Step 4

By using RSA and LSA, we construct the 2D range reporting data structure in
$\mathcal{\tilde{O}}(|\mathcal{A}_{\ell,r}(S)|)$ time using
$\mathcal{O}(|\mathcal{A}_{\ell,r}(S)|)$ space [20, 80, 11, 42].

This completes the construction: we have shown how to construct
$\mathcal{I}_{\ell,r}(S)$ in near-optimal work using only
$\mathcal{O}(\ell+|\mathcal{A}_{\ell,r}(S)|)$ space (and external memory).
This is good because the size of $\mathcal{I}_{\ell,r}(S)$ is
$\mathcal{O}(|\mathcal{A}_{\ell,r}(S)|)$ (Theorem 1) and the
$\mathcal{O}(\ell)$ factor is negligible in practice.

##  6 Index with worst-case guarantees

The index based on bd-anchors has $\mathcal{O}(|\mathcal{A}_{\ell,r}(S)|)$
size, and supports pattern matching queries in
$\mathcal{\tilde{O}}(|P|+\textsf{occ})$ time. Moreover, it can be constructed
in $\mathcal{\tilde{O}}(n)$ time using
$\mathcal{O}(\ell+|\mathcal{A}_{\ell,r}(S)|)$ space. Unfortunately, while in
many real-world datasets we have $|\mathcal{A}_{\ell,r}(S)|=\Theta(n/\ell)$,
there are worst cases with $|\mathcal{A}_{\ell,r}(S)|=\Theta(n)$; e.g., for
$S=a_{1}a_{2}\ldots a_{n}$, where all $n$ letters are different.

In this section, we combine some ideas presented in [7] with the bd-anchors
index to prove the following.

######  Theorem 4.

For any string $S$ of length $n$ over an integer alphabet of size
$n^{\mathcal{O}(1)}$ and any integer $\ell>0$, we can construct an index that
occupies $\mathcal{O}(n/\ell)$ extra space and reports all occ occurrences of
any pattern $P$ of length $|P|\geq\ell$ in $S$ in
$\mathcal{\tilde{O}}(|P|+\textsf{occ})$ time. The index can be constructed in
$\mathcal{\tilde{O}}(n)$ time and $\mathcal{O}(n/\ell)$ working space.

We define one of the most basic string notions. An integer $p>0$ is a _period_
of a string $P$ if $P[i]=P[i+p]$ for all $i\in[1,|P|-p]$. The smallest period
of $P$ is referred to as _the period_ of $P$ and is denoted by
$\textsf{per}(P)$.

######  Example 6.

For $P=\texttt{abaaabaaabaaaba}$, $\textsf{per}(P)=4$; $p=8$ is also a period
of $P$ but it is not the smallest.

We are now in a position to define the following powerful notion of locally
consistent anchors.

######  Definition 4 ($\tau$-partitioning set [70]).

For any string $S$ of length $n$ and any integer $\tau\in[4,n/2]$, a set of
positions $\mathcal{P}\subseteq[1,n]$ is called a _$\tau$ -partitioning set_
if it satisfies the following properties:

  1. 1.

if $S[i-\tau\mathinner{.\,.}i+\tau]=S[j-\tau\mathinner{.\,.}j+\tau]$, for
$i,j\in[\tau,n-\tau)$, then $i\in\mathcal{P}$ if and only if
$j\in\mathcal{P}$;

  2. 2.

if $S[i\mathinner{.\,.}i+\ell]=S[j\mathinner{.\,.}j+\ell]$, for
$i,j\in\mathcal{P}$ and some $\ell\geq 0$, then, for each $d\in[0,\ell-\tau)$,
$i+d\in\mathcal{P}$ if and only if $j+d\in\mathcal{P}$;

  3. 3.

if $i,j\in[1,n]$ with $j-i>\tau$ and $(i,j)\cap\mathcal{P}=\emptyset$, then
$S[i\mathinner{.\,.}j]$ has period at most $\tau/4$.

Let us explain these properties. Property 1 tells us that for any two equal
sufficiently long fragments of $S$, we either pick no anchor or we pick an
anchor having the same relative position in both (local consistency). Property
2 tells us that for any two equal sufficiently long fragments of $S$, the
anchors we pick from both are in sync (forward synchronization). Property 3
tells us that for a sufficiently long fragment of $S$, if no anchor is picked,
then this fragment is highly periodic (approximately uniform sampling).

######  Theorem 5 ([70]).

For any string $S$ of length $n$ over an integer alphabet of size
$n^{\mathcal{O}(1)}$ and any integer $\tau\in[4,\mathcal{O}(n/\log^{2}n)]$, we
can construct a $\tau$-partitioning set $\mathcal{P}$ of size
$\mathcal{O}(n/\tau)$. The set $\mathcal{P}$ can be constructed in
$\mathcal{\tilde{O}}(n)$ time using $\mathcal{O}(n/\tau)$ working space. The
set $\mathcal{P}$ additionally satisfies the property that if a fragment
$S[i\mathinner{.\,.}j]$ has period at most $\tau/4$, then
$\mathcal{P}\cap[i+\tau,j-\tau]=\emptyset$.

We now define the notion of $\tau$-runs: sufficiently long maximal fragments
with the same periodic structure.

######  Definition 5 ($\tau$-run [7]).

A fragment $F$ of a string $S$ is a _$\tau$ -run_ if and only if $|F|>3\tau$,
$\textsf{per}(F)\leq\tau/4$, and $F$ cannot be extended in either direction
without its period changing. The _Lyndon root_ of a $\tau$-run $F$ is the
lexicographically smallest rotation of $F[1\mathinner{.\,.}\textsf{per}(F)]$.
String $F$ can be expressed by $L$ and three non-negative integers
$x_{F},e_{F},y_{F}$:

$F=L[|L|-x_{F}+1\mathinner{.\,.}|L|]\cdot L^{e_{F}}\cdot
L[1\mathinner{.\,.}y_{F}].$

######  Example 7.

For $F=\texttt{abaaabaaabaaaba}$ with $\textsf{per}(F)=4$, the Lyndon root is
$L=\texttt{aaab}$. Specifically, we have $x_{F}=2$, $e_{F}=3$, and $y_{F}=1$:

$F=\texttt{ab}\cdot\texttt{aaab}^{3}\cdot\texttt{a}.$

We also state a few combinatorial and algorithmic results on $\tau$-runs that
are crucial in our construction.

######  Lemma 10 ([23]).

Two $\tau$-runs can overlap by at most $\tau/2$ positions. The number of
$\tau$-runs in a string of length $n$ is $\mathcal{O}(n/\tau)$.

######  Lemma 11 ([7]).

For any string $S$ of length $n$ over an integer alphabet of size
$n^{\mathcal{O}(1)}$ and any integer $\tau\in[4,\mathcal{O}(n/\log^{2}n)]$,
all $\tau$-runs in $S$ can be computed and grouped by Lyndon root in
$\mathcal{\tilde{O}}(n)$ time using $\mathcal{O}(n/\tau)$ space. Within the
same complexities, we can compute the first occurrence of the Lyndon root in
each $\tau$-run.

#### Data structure

Let $\ell$ be an integer in $[20,\lfloor n/\log^{2}n\rfloor]$ and let
$\tau=\lfloor\ell/5\rfloor$. We use Theorem 5 and Lemma 11 with parameter
$\tau$ to compute a partitioning set $\mathcal{P}$ of size
$\mathcal{O}(n/\tau)$ and all $\tau$-runs in $S$. For every $\tau$-run $T$ of
group $L$, we have the first occurrence of its Lyndon root. We can thus
compute the non-negative integers $x_{T},y_{T}<|L|$ and $e_{T}$, such that
$T=L[|L|-x_{T}+1\mathinner{.\,.}|L|]\cdot L^{e_{T}}\cdot
L[1\mathinner{.\,.}y_{T}]$, in constant time. We maintain the lists of pairs
$(e_{T},x_{T})$ and $(e_{T},y_{T})$ for all $T$, sorted, for every $L$
separately. This can be done in $\mathcal{\tilde{O}}(n)$ time and
$\mathcal{O}(n/\tau)$ space using merge sort. To access the lists of $L$, we
index the collection of lists by the KR fingerprint of $L$. We also maintain a
priority search tree [82] over points $(x_{T},y_{T})$, for every $(L,e_{T})$
separately, on the grid $[1,|L|]^{2}$. This can be done in
$\mathcal{\tilde{O}}(n/\tau)$ time and $\mathcal{O}(n/\tau)$ space. To access
a specific priority search tree for $L$, we further index the collection of
trees by $e_{T}$. For every $i\in\mathcal{P}$ we also store the KR fingerprint
(see Section 4) of $S[i-\tau\mathinner{.\,.}i+\tau]$ in a hash table $H$. This
can be done in $\mathcal{O}(n)$ time using $\mathcal{O}(|\mathcal{P}|)$ space.
Let $\mathcal{L}$ be a set that contains the starting and ending position of
each $\tau$-run. We construct $\mathcal{A}:=\mathcal{P}\cup\mathcal{L}$ and
construct the index of Section 3 over string $S$ and $\mathcal{A}$. By Lemma
10 and Theorem 5 the size of $\mathcal{A}$ is $\mathcal{O}(n/\tau)$ in the
worst case. By Theorem 5 and Theorem 11, $\mathcal{A}$ is constructed in
$\mathcal{\tilde{O}}(n)$ time. By Theorem 1, the index over string $S$ and
$\mathcal{A}$ is constructed in $\mathcal{\tilde{O}}(n)$ time and occupies
$\mathcal{O}(|\mathcal{A}|)=\mathcal{O}(n/\tau)$ extra space. The working
space for the two compacted tries is also
$\mathcal{O}(|\mathcal{A}|)=\mathcal{O}(n/\tau)$ by employing the following
result on sparse suffix sorting.

######  Theorem 6 ([16, 70]).

For any string $S$ of length $n$ over an integer alphabet of size
$n^{\mathcal{O}(1)}$, we can construct the compacted trie of $b$ arbitrary
suffixes of $S$ in $\mathcal{\tilde{O}}(n)$ time using $\mathcal{O}(b)$ space.

The working space for the accompanying 2D range reporting data structure is
also $\mathcal{O}(|\mathcal{A}|)=\mathcal{O}(n/\tau)$ by using the data
structure of Mäkinen and Navarro [80].

This completes the construction of the index.

#### Querying

We are given a query $P$, $|P|\geq\ell$. Let us give an overview of the
querying part: if $P$ occurs in $S$, then it should be because it contains a
sufficiently long aperiodic fragment, for which we have an anchor stored in
$\mathcal{P}\subseteq\mathcal{A}$, or because it has a sufficiently long
periodic fragment, which occurs also in $S$. The latter case is split in the
following two subcases: (i) $P$ has a periodic fragment shorter than $P$, in
which case, we use one of its endpoints as an anchor stored in
$\mathcal{L}\subseteq\mathcal{A}$; or the whole of $P$ is periodic, in which
case, we have no anchor to use, but we can use the Lyndon root of $P$ to find
its occurrences in $S$. We thus start by computing $\textsf{per}(P)$ in
$\mathcal{O}(|P|)$ time [28] and proceed as follows:

Aperiodic case:

If $\textsf{per}(P)>\tau/4$, we compute the KR fingerprint of every fragment
$P[j-\tau\mathinner{.\,.}j+\tau]$ of $P$. If a KR fingerprint is found in $H$,
we spell $P[j\mathinner{.\,.}|P|]$ and $\overleftarrow{P[1\mathinner{.\,.}j]}$
in the two compacted tries, and obtain the occurrences of $P$ in $S$ by using
a 2D range reporting query just as in Section 3. The total query time is
$\mathcal{\tilde{O}}(|P|+\textsf{occ})$.

Fully-periodic case:

In this case, $\textsf{per}(P)\leq\tau/4$. We start by computing the Lyndon
root $L$ of $P$ and the non-negative integers $x_{P},y_{P}<|L|$ and $e_{P}$
such that $P=L[|L|-x_{P}+1\mathinner{.\,.}|L|]\cdot L^{e_{P}}\cdot
L[1\mathinner{.\,.}y_{P}]$ in $\mathcal{O}(|P|)$ time [7]. Let $T$ be a
$\tau$-run in $S$ with the same $L$. Further let $x_{T},y_{T}<|L|$ and $e_{T}$
such that $T=L[|L|-x_{T}+1\mathinner{.\,.}|L|]\cdot L^{e_{T}}\cdot
L[1\mathinner{.\,.}y_{T}]$. $P$ occurs in $T$ if and only if at least one of
the following conditions is met [7]: (1) $e_{P}=e_{T}$, $x_{P}\leq x_{T}$, and
$y_{P}\leq y_{T}$; or (2) $e_{P}+1=e_{T}$ and $x_{P}\leq x_{T}$; or (3)
$e_{P}+1=e_{T}$ and $y_{P}\leq y_{T}$; or (4) $e_{P}+2\leq e_{T}$. We first
locate the sorted lists for the $\tau$-runs $T$ with Lyndon root $L$ in $S$,
in $\mathcal{O}(|L|)$ time, by computing the KR fingerprint of $L$, as well as
the corresponding priority search trees. Each valid $T$ is located in
$\mathcal{\tilde{O}}(1)$ time with binary search on the stored lists or with
one of the priority search trees. For instance, for checking the first
condition, we locate the priority search tree for $L$ and $e_{P}$ and search
for the points included in the axis-aligned rectangle
$[x_{P},\infty)\times[y_{P},\infty)$. All $s$ such points are found in
$\mathcal{O}(\log n+s)$ time [82]. Let $(x_{T},y_{T})$ be a retrieved point
corresponding to $\tau$-run $T$ of $S$. This ensures that $e_{P}=e_{T}$,
$x_{P}\leq x_{T}$, and $y_{P}\leq y_{T}$. The other three conditions are
trivially checked with binary search. Since the length of $T$ is
$x_{T}+|L|\cdot e_{T}+y_{T}$; we know the length of $P$; and we also know the
first occurrence of $L$ in both $T$ and $P$, we can easily report all $k$
occurrences of $P$ in $T$ in $\mathcal{O}(k)$ extra time. The total query time
is $\mathcal{\tilde{O}}(|P|+\textsf{occ})$.

Quasi-periodic case:

It could be the case that $P$ is not highly-periodic itself (i.e.,
$\textsf{per}(P)>\tau/4$) but contains a long highly-periodic fragment that
prevents us from finding a fragment $P[j-\tau\mathinner{.\,.}j+\tau]$ with a
KR fingerprint in $H$ (see Property 3, Definition 4). Inspect Figure 5. By the
properties of $\mathcal{P}$, we know that if $P$ occurs in $S$ then
$\textsf{per}(P[\tau\mathinner{.\,.}|P|-\tau+1])\leq\tau/4$; note that,
otherwise, we would have found at least one fragment of length $2\tau+1$ whose
KR fingerprint is in $H$.

Figure 5: The quasi-periodic case: in this setting, the long highly-periodic
fragment is neither a prefix nor a suffix, and so we can use any of its
endpoints as an anchor.

######  Example 8.

Let $\ell=20$, $\tau=4$, and $|P|=\ell$. Further assume that $P$ occurs in $S$
but $P[i-\tau\mathinner{.\,.}i+\tau]$, for all $i\in[5,16]$ was not found in
$H$. Property 3 of set $\mathcal{P}$ tells us that if $P$ occurs in $S$ then
$P[4\mathinner{.\,.}17]=P[\tau\mathinner{.\,.}|P|-\tau+1]$ has period at most
$\tau/4$.

In $\mathcal{O}(|P|)$ time, we check if
$\textsf{per}(P[\tau\mathinner{.\,.}|P|-\tau+1])\leq\tau/4$ [28], and if so,
we extend periodicity on both sides as much as possible, hence computing a
periodic fragment $P[i\mathinner{.\,.}j]$, $i\leq\tau$ and $j\geq|P|-\tau+1$.
If $i>1$, we construct $P[i\mathinner{.\,.}|P|]$ and
$\overleftarrow{P[1\mathinner{.\,.}i]}$; otherwise, if $j<|P|$, we construct
$P[j\mathinner{.\,.}|P|]$ and $\overleftarrow{P[1\mathinner{.\,.}j]}$. Note
that it cannot be that both $i=1$ _and_ $j=|P|$, because then we would be in
the previous case (fully-periodic case). We then spell the two sub-patterns in
the two compacted tries, and obtain the occurrences of $P$ in $S$ by using a
2D range reporting query just as in Section 3. The total query time is
$\mathcal{\tilde{O}}(|P|+\textsf{occ})$.

Note that if any of the above three cases is successful in finding occurrences
of $P$ in $S$ we stop, because we would in fact have found _all_ the
occurrences of $P$ in $S$. On the other hand, if none of the above cases is
successful, then it means that $P$ does not occur in $S$.

Finally, let us handle the edge cases. Recall that, in the above, we have
assumed that $\ell$ is an integer in $[20,\lfloor n/\log^{2}n\rfloor]$. If
$\ell<20=\mathcal{O}(1)$, we simply construct the suffix tree of $S$ (as our
only index) in $\mathcal{O}(n)$ time [32]. The space occupied by the suffix
tree is $\mathcal{O}(n)$, which for any $\ell=\mathcal{O}(1)$, is in
$\mathcal{O}(n/\ell)$. If $\ell>\lfloor n/\log^{2}n\rfloor$ then we do not
construct any text index. Upon a query $P$, with $|P|>\lfloor
n/\log^{2}n\rfloor$, we use a real-time constant-space string matching
algorithm [18] to report all occurrences of $P$ in $S$ in $\mathcal{O}(n)$
time, in which case we have that
$\mathcal{O}(n)=\mathcal{\tilde{O}}(|P|+\textsf{occ})$. We have arrived at
Theorem 4.

Our construction is randomized (correct with high probability) due to the use
of KR fingerprints.

##  7 Implementations

In this section, we provide the full details of our implementations, which
have all been written in C++. In addition to the classic text indexes referred
to in Section 1, we have considered the r-index [41], a text index, which
performs specifically well for highly repetitive text collections. We did not
consider: (i) the suffix tree, as it is not competitive at all with respect to
space; or (ii) sampling the suffix array with minimizers [48], as their number
is generally greater than (reduced) bd-anchors; see the results of [77, 78].
As we show later in experiments (Section 8), the set of randomized reduced bd-
anchors can be computed _faster_ and using _less space_ than the set of
reduced bd-anchors. Moreover, we show that the former set is _always smaller_
than the latter. We have thus used randomized reduced bd-anchors instead of
reduced bd-anchors to construct our indexes. We have also not implemented our
index with worst-case guarantees (Section 6) as it relies on partitioning sets
[70], an extremely intricate sampling scheme, which is highly unlikely to be
efficient in practice,222Personal communication with Dmitry Kosolobov. as well
as on the involved querying scheme consisting of many cases, which is also
highly unlikely to be efficient in practice.

Since our focus is on algorithmic ideas (not on low-level code optimization)
and to ensure fairness across different implementations, we have re-used the
same algorithm or code whenever it was possible. For instance, although many
other engineered implementations for classic text indexes exist, e.g. [45] for
FM-index or [14] for suffix array, we have based our implementations on sdsl-
lite [44] as much as possible for fairness:

SA:

The construct SA we used the divsufsort class, written by Yuta Mori, as
included in sdsl-lite. To report all occurrences of a pattern, we implemented
the algorithm of Manber and Myers [81] that uses as well the LCP array [66]
augmented with a succinct RMQ data structure [37] (rmq_succinct_sct class).

CSA:

The CSA was constructed using the csa_sada class of sdsl-lite. To report all
occurrences of a pattern, we used the SA method.

CST:

The CST was constructed using the cst_sct3 class [90] of sdsl-lite. To report
all occurrences of a pattern, we traverse the tree (see Section 2) by using
its supported functionality.

FM-index:

The FM-index was implemented using the csa_wt class of sdsl-lite. To report
all occurrences of a pattern, the supported count and locate methods of sdsl-
lite were used.

r-index:

The r-index is not part of sdsl-lite and so we had to resort to the open-
source implementation provided by Gagie et al. in [41]. The binary ri-build
was used to build the index (using the divsufsort class of the sdsl-lite) and
then ri-locate was used to locate all occurrences of the patterns.

rBDA-compute:

We implemented the algorithm for computing the set of reduced bd-anchors as
described in Section 5.1. To improve construction space, we implemented the
algorithm in fragments as described in Step 1 of the space-efficient algorithm
presented in Section 5.2. The implementation takes the fragment length $b$ as
input. We call these fragments _blocks_ henceforth.

rrBDA-compute:

Similar to the above, we implemented the algorithm for computing the set of
randomized reduced bd-anchors as described in Section 5.1. The implementation
takes the block length $b$ as input. As we will show in Section 8.2,
randomized reduced bd-anchors performed consistently better than reduced bd-
anchors. Therefore, we have based our index construction implementations,
presented right below, on the notion of randomized reduced bd-anchors.

rrBDA-index I (ext):

The construction was implemented using Steps 1 to 3 as described in Section
5.2. For Step 2, we used the pSAscan algorithm of Kärkkäinen et al. [62] to
construct the SA in EM and the EM-SparsePhi algorithm of Kärkkäinen and Kempa
[61] to compute the LCP array in EM. For Step 3, instead of constructing the
compacted tries, we used the arrays LSA, LLCP, RSA, and RLCP directly. The
LLCP and RLCP arrays were augmented each with an RMQ data structure (similar
to SA). For Step 4, we implemented the 2D range reporting data structure of
Mäkinen and Navarro [80]. To report all occurrences of a pattern, we
implemented the algorithm of Loukides and Pissis [77] (see Section 3).

rrBDA-index I (int):

For the internal-memory construction, we implemented Step 3 using the PA
algorithm for sparse suffix sorting of Ayad et al. from [5]. Sparse suffix
sorting is not included in sdsl-lite, and so we had to resort to PA, being the
state of the art.

rrBDA-index II (ext):

The construction was implemented using Steps 1 to 3 as in rrBDA-index I (ext).
Unlike rrBDA-index I (ext), however, no 2D range reporting data structure was
used. We instead used the bidirectional search algorithm presented by Loukides
and Pissis in [77]. This algorithm reports all occurrences of a pattern $P$,
by first searching for either $P[j\mathinner{.\,.}|P|]$ or
$\overleftarrow{P[1\mathinner{.\,.}j]}$ using the four arrays, where $j$ is
the reduced bd-anchor of $P[1\mathinner{.\,.}\ell]$; and then using letter
comparisons to verify the remaining part of candidate occurrences. This index
was the most efficient one in practice in [77]; however, the query time is not
bounded in the worst case.

rrBDA-index II (int):

Similar to rrBDA-index I, for the internal-memory construction, we implemented
Step 3 using the PA algorithm of Ayad et al. from [5].

##  8 Experiments

###  8.1 Experimental setup

We downloaded five datasets (texts) from the Pizza&Chili corpus [33] – see
Table 1 for their characteristics. We generated patterns of length 32, 64,
128, 256, 512, and 1024 for all datasets with 500,000 distinct patterns
created per length. The patterns were generated by selecting occurrences
uniformly at random from the datasets. We also downloaded the _Homo sapiens_
genome (version GRCh38.p14), which we denote by HUMAN. Its length $n$ is
3,136,819,257 and the alphabet size $\sigma$ is 15. We generated patterns of
length 64, 256, 1,024, 4,096, and 16,384 for HUMAN with 500,000 distinct
patterns created per length. Similar to the Pizza&Chili datasets, these
patterns were generated by selecting occurrences uniformly at random from
HUMAN.

The experiments ran on an Intel Xeon Gold 648 at 2.5GHz with 192GB RAM. All
programs were compiled with g++ version 10.2.0 at the -O3 optimization level.
Our code and datasets are freely available at
https://github.com/lorrainea/rrBDA-index.

Dataset | Length $n$ | Alphabet size $\sigma$
---|---|---
DNA | 209,714,087 | 15
PROTEINS | 209,006,085 | 24
XML | 204,198,133 | 95
SOURCES | 166,552,125 | 225
ENGLISH | 205,627,746 | 222
HUMAN | 3,136,819,257 | 15

Table 1: Datasets characteristics.

#### Parameters

For rBDA-compute, rrBDA-compute, rrBDA-index I (int and ext) and rrBDA-index
II (int and ext), we set $\ell$ to the pattern length, $b$ to $25$K, unless
stated otherwise, and $r$ to $\lceil 4\log\ell/\log\sigma\rceil$. We also set
$M$ (RAM), used in rrBDA-index I (ext) and rrBDA-index II (ext), to
$\Theta(|\mathcal{A}_{\ell,r}|)$ as this is the final size of index
$\mathcal{I}_{\ell,r}(S)$.

#### Measures

Four measures were used: index size; query time; construction space; and
construction time; (see Section 1). To measure the query and construction
time, the steady_clock class of C++ was used with the elapsed time measured in
nanoseconds (ns). To measure the index size for each implementation as
accurately as possible, the data structures required for querying the patterns
were output to a file in secondary memory. The text size was not counted as
part of the index size for any implementation. The construction space was
measured by recording the maximum resident set size in kilobytes (KB) using
the /usr/bin/time -v command.

#### Results

In Sections 8.2 to 8.7, we present the results for the datasets of Table 1. To
avoid cluttering the figures, we omit the results of rrBDA-index I (resp., int
and ext), as they were consistently outperformed by rrBDA-index II (resp., int
and ext) in all four measures used.

###  8.2 Comparing reduced bd-anchors to randomized reduced bd-anchors

In the following, we compare reduced bd-anchors (rBDA-compute) to our new
notion of randomized reduced bd-anchors (rrBDA-compute) along three dimensions
(density, construction time, and construction space) using the first five
datasets of Table 1.

Figure 6 shows that the number of bd-anchors in both schemes, rBDA-compute and
rrBDA-compute, decreases as $\ell$ increases, as expected. Furthermore, the
trends of both schemes are the same. However, the randomized reduced bd-
anchors are fewer than the reduced bd-anchors (and thus their density, i.e.,
their number divided by the string length $n$, is smaller), for every tested
$\ell$ value and every tested dataset. Specifically, the number of randomized
reduced bd-anchors is $17.8\%$ lower on average (over all datasets) and up to
$46.8\%$ lower. The fact that randomized reduced bd-anchors are fewer is
encouraging, since it leads to indexes with lower construction space.

Figure 7 shows that it is much more efficient to compute our notion of
randomized reduced bd-anchors compared to reduced bd-anchors, and this is
consistent over all tested $\ell$ values and datasets. Specifically, the time
needed by rrBDA-compute was smaller than that of rBDA-compute by $32.4\%$ on
average (over all datasets) and up to $77.6\%$ lower. On the other hand, the
simple $\Theta(n\ell)$-time algorithm of [77], which computes reduced bd-
anchors and is represented by the $\Theta(n\ell)$ line, is even slower than
rBDA-compute. In particular, rBDA-compute becomes more than _two orders of
magnitude faster_ than the $\Theta(n\ell)$ algorithm as $\ell$ increases.

As suggested by Theorems 2 and 3, the runtime of rBDA-compute and of rrBDA-
compute should not be affected by $\ell$ in the case of a uniformly random
input string. Even if our datasets are real and thus not uniformly random, we
observe that the runtime of rBDA-compute and rrBDA-compute in Figure 7 is not
affected too much by the value of $\ell$; an exception to this is the case of
SOURCES, which is explained by the fact that this dataset, in particular, is
very far from being _uniformly random_ , which is assumed by our theoretical
findings. Specifically, in this dataset, the number of $(w,k)$-minimizers is
much larger than what is expected on average with increasing $\ell$, thus more
ties need to be broken (Lemma 8), and this is why the runtime increases with
$\ell$. Nevertheless, even in this bad case, rBDA-compute is up to $112\times$
faster than the implementation of the simple $\Theta(n\ell)$-time algorithm
[77], and rrBDA-compute is up to $177\times$ faster.

(a)

(b)

(c)

(d)

(e)

Figure 6: Number of bd-anchors output by rBDA-compute and rrBDA-compute for
varying $\ell$ (log-scale).

(a)

(b)

(c)

(d)

(e)

Figure 7: Elapsed time to construct the set of reduced and randomized bd-
anchors (seconds in log-scale) for varying $\ell$ (log-scale).

Figure 8 shows that, for all tested $\ell$ values and datasets, rBDA-compute
and rrBDA-compute have a _similar_ trend to the $\Theta(n\ell)$-time
implementation [77]. In particular, as $\ell$ increases the space required to
construct bd-anchors is reduced. This is expected since for increasing $\ell$
the size of the set of bd-anchors decreases. Also, note that the space for
rrBDA-compute is smaller by $12.8\%$ on average (over all datasets) compared
to that for rBDA-compute and by up to $49.1\%$ compared to that for rBDA-
compute. These space-time results establish the practical usefulness of our
Theorems 2 and 3.

(a)

(b)

(c)

(d)

(e)

Figure 8: Space required to construct the set of reduced and randomized bd-
anchors (MB in log-scale) for varying $\ell$ (log-scale).

###  8.3 Index size

Figure 9 shows the index size for the first five datasets of Table 1 when
using the rrBDA-compute implementation of Section 7 and rrBDA-index II (both
int and ext versions have the same index size). As expected, the index size
occupied by rrBDA-index II decreases with increasing $\ell$. Notably, for all
datasets and $\ell\geq 64$, rrBDA-index II is smaller than all other indexes
except for the FM-index. This is remarkable, given that our index is not
compressed and as we will show it allows much faster querying. When $\ell\geq
512$, rrBDA-index II _outperforms all indexes_ for all datasets. Specifically,
when $\ell=512$, rrBDA-index II requires $59.1\%$ less space than FM-index on
average (over all datasets), while when $\ell=1024$ our index requires
$77.9\%$ less space.

(a)

(b)

(c)

(d)

(e)

Figure 9: Size of different indexes (MB in log-scale) for varying $\ell$ (log-
scale).

###  8.4 Query time

Figure 10 shows the average query time (over all patterns) for the first five
datasets in Table 1 when $\ell=|P|$. Both rrBDA-index II (int) and rrBDA-index
II (ext) have the same query time, so we write rrBDA-index II to refer to
either. For all datasets and $\ell\geq 64$, rrBDA-index II is up to _several
orders of magnitude_ faster than the compressed indexes, especially for large
alphabets, which is consistent with the observations made in [35, 46].
Notably, rrBDA-index II is even faster than the SA, with the single exception
of $\ell=32$ in the XML dataset.

(a)

(b)

(c)

(d)

(e)

Figure 10: Average time for pattern matching (nanoseconds in log-scale) for
varying $|P|$ (log-scale).

###  8.5 Index construction space

Figure 11 shows the index construction space required for the first five
datasets of Table 1. Notably, for all datasets when $\ell\geq 128$, rrBDA-
index II (int) and rrBDA-index II (ext) outperform all other indexes. As
expected, the construction space required by rrBDA-index II (int) decreases
with increasing $\ell$. The construction space of rrBDA-index II (ext)
decreases with $\ell$ initially but remains almost the same for $\ell\geq
256$. This is because approximately 600MB of space (internal memory) are used
by the implementations constructing arrays SA and LCP in external memory.

(a)

(b)

(c)

(d)

(e)

Figure 11: Space required to construct different indexes (MB in log-scale) for
varying $\ell$ (log-scale).

###  8.6 Index construction time

Figure 12 shows the time needed to construct all indexes for the first five
datasets of Table 1. We set $b=25$K for rrBDA-index II (int) and rrBDA-index
II (ext). For all datasets and $\ell$ values, rrBDA-index II (ext) outperforms
CSA and is outperformed by the SA, FM-index, CST, and r-index. It also
outperforms rrBDA-index II (int) for $\ell=32$ but performs worse for all
larger $\ell$ values. This is because, as $\ell$ increases, the number of bd-
anchors decreases significantly, and thus rrBDA-index II (int) becomes faster
(e.g., it performs similarly to one or more of the competitors for
$\ell=1024$). On the other hand, as $\ell$ increases, rrBDA-index II (ext)
still needs to construct arrays SA and LCP in external memory, which is the
bottleneck for the construction time.

(a)

(b)

(c)

(d)

(e)

Figure 12: Elapsed time to construct different indexes (seconds in log-scale)
for varying $\ell$ (log-scale).

###  8.7 Results on the HUMAN dataset

Figure 13(a) shows that the number of randomized reduced bd-anchors (rrBDA-
compute) is much smaller than that of randomized bd-anchors (rBDA-compute)
($25.2\%$ on average) and that both of these numbers decrease as $\ell$
increases. This result is analogous to that of Figure 6.

Figure 13(b) shows that rrBDA-index II (both int and ext versions have the
same index size) outperforms both FM-index and r-index for $\ell\geq 64$ in
terms of index size (we excluded the other indexes as they were outperformed
by the latter two). For example, for $\ell=2^{14}=16,384$, rrBDA-index II
takes less than 16MB, while FM-index and r-index take 1GB and 16GB,
respectively.

(a)

(b)

(c)

(d)

(e)

Figure 13: (a) Number of bd-anchors for HUMAN and varying $\ell$ (log-scale).
(b) Size of different indexes (MB in log-scale) for HUMAN and varying $\ell$
(log-scale). (c) Average time for pattern matching (nanoseconds in log-scale)
on HUMAN and for varying $|P|$ (log-scale). (d) Space required to construct
different indexes (MB in log-scale) for HUMAN and varying $\ell$ (log-scale).
(e) Elapsed time to construct different indexes (seconds in log-scale) for
HUMAN and varying $\ell$ (log-scale).

Figure 13(c) shows the average query time for HUMAN with $\ell=|P|$. As $\ell$
increases, rrBDA-index II becomes more than one order of magnitude faster than
the FM-index and r-index. Note that for all $\ell$, rrBDA-index II is faster
than the FM-index and r-index.

Figure 13(d) shows that rrBDA-index II (int) outperforms all other indexes in
terms of construction space, and the difference between rrBDA-index II (int)
and these indexes becomes larger as $\ell$ increases. The results are
analogous to those in Figure 11. For example, for $\ell=2^{14}$ rrBDA-index II
(int) requires at least $2\times$ less space than rrBDA-index II (ext) and
more than $4\times$ less space than FM-index. At the same time, rrBDA-index II
(ext) substantially outperforms FM-index and r-index for all tested $\ell$
values.

Figure 13(e) shows that rrBDA-index II (int) performs better as $\ell$
increases, and even outperforms the best competitor, FM-index for
$\ell>2^{10}$.333We set $b=130K$, as this dataset is much larger than those
above [4]. At the same time, rrBDA-index II (ext) performs worse than FM-index
and r-index. The reason that rrBDA-index II (ext) performs worse is the
construction of SA and the LCP array, as explained before. The results are
analogous to those for DNA in Figure 12.

The presented results highlight the scalability of our construction algorithms
as well as the superiority of rrBDA-index II for long patterns.

##  9 Final remarks

We have shown that our implementation of the bd-anchors index should be the
practitioners’ choice for long patterns. When $\ell\geq 512$, our index
outperforms all indexes for all datasets in terms of index size. When
$\ell\geq 64$, our index outperforms all indexes for all datasets in terms of
query time. When $\ell\geq 64$, our index outperforms all indexes for all
datasets in terms of construction space. The construction time of our index is
up to $5\times$ slower than the state of the art. However, we believe that
this does not make our index less practical as in many cases of practical
interest our index can be constructed only once and queried multiple times.

An obvious criticism against the bd-anchors index is that its theoretical
guarantees rely on the average-case model and on the assumption that we have
at hand a lower bound on $\ell$. For the former, we have shown, using
benchmark datasets (and not using synthetic uniformly random ones), that our
index generally outperforms the state of the art for long patterns, which is
the main claim here. For the latter, in most real-world applications we can
think of, we do have a lower bound on the length of patterns (see Section
1.2). For example, in long-read alignment, this bound is in the order of
several hundreds. Finally, the state-of-the-art compressed indexes also have a
crucial assumption, which is implicit and thus oftentimes largely neglected.
The assumption is that the size $\sigma$ of the alphabet is much smaller than
the length $n$ of the text. In the worst case, i.e., when $\sigma=\Theta(n)$,
the state-of-the-art compressed indexes have no advantage compared to the
suffix array or the suffix tree: they occupy $n\log\sigma=\Theta(n\log n)$
bits.

The theoretical highlight of this paper is Theorem 4. The underlying index has
$\mathcal{O}(n/\ell)$ size, it can be constructed in near-optimal time using
$\mathcal{O}(n/\ell)$ working space, and it supports near-optimal pattern
matching queries. Since it works for any integer $\ell\in[1,n]$, it can be
seen as a parameterization of the classic suffix tree index [32]. Our
construction is currently randomized; it is an interesting open problem to
make it deterministic.

## Acknowledgments

The authors thank Panagiotis Charalampopoulos for helpful suggestions on
Theorem 4. This work is partially supported by the PANGAIA and ALPACA projects
that have received funding from the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie grant agreements No
872539 and 956229, respectively.

## References

  * [1] James Abello, Adam L. Buchsbaum, and Jeffery R. Westbrook.  A functional approach to external graph algorithms.  Algorithmica, 32(3):437–458, 2002.
  * [2] Alberto Apostolico, Maxime Crochemore, Martin Farach-Colton, Zvi Galil, and S. Muthukrishnan.  40 years of suffix trees.  Commun. ACM, 59(4):66–73, 2016.
  * [3] Mozhdeh Ariannezhad, Ali Montazeralghaem, Hamed Zamani, and Azadeh Shakery.  Improving retrieval performance for verbose queries via axiomatic analysis of term discrimination heuristic.  In Noriko Kando, Tetsuya Sakai, Hideo Joho, Hang Li, Arjen P. de Vries, and Ryen W. White, editors, Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, Shinjuku, Tokyo, Japan, August 7-11, 2017, pages 1201–1204. ACM, 2017.
  * [4] Lorraine A. K. Ayad, Grigorios Loukides, and Solon P. Pissis.  Text indexing for long patterns: Anchors are all you need.  Proc. VLDB Endow., 16(9):2117–2131, 2023.
  * [5] Lorraine A. K. Ayad, Grigorios Loukides, Solon P. Pissis, and Hilde Verbeek.  Sparse suffix and LCP array: Simple, direct, small, and fast.  In José A. Soto and Andreas Wiese, editors, LATIN 2024: Theoretical Informatics - 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024, Proceedings, Part I, volume 14578 of Lecture Notes in Computer Science, pages 162–177. Springer, 2024.
  * [6] Jérémy Barbay, Francisco Claude, Travis Gagie, Gonzalo Navarro, and Yakov Nekrich.  Efficient fully-compressed sequence representations.  Algorithmica, 69(1):232–268, 2014.
  * [7] Gabriel Bathie, Panagiotis Charalampopoulos, and Tatiana Starikovskaya.  Internal pattern matching in small space and applications.  In Inenaga and Puglisi [56], pages 4:1–4:20.
  * [8] Djamal Belazzougui.  Linear time construction of compressed text indices in compact space.  In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 148–193. ACM, 2014.
  * [9] Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen, and Veli Mäkinen.  Linear-time string indexing and analysis in small space.  ACM Trans. Algorithms, 16(2):17:1–17:54, 2020.
  * [10] Djamal Belazzougui and Gonzalo Navarro.  Optimal lower and upper bounds for representing sequences.  ACM Trans. Algorithms, 11(4):31:1–31:21, 2015.
  * [11] Djamal Belazzougui and Simon J. Puglisi.  Range predecessor and lempel-ziv parsing.  In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 2053–2071. SIAM, 2016.
  * [12] Stav Ben-Nun, Shay Golan, Tomasz Kociumaka, and Matan Kraus.  Time-space tradeoffs for finding a long common substring.  In Inge Li Gørtz and Oren Weimann, editors, 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, June 17-19, 2020, Copenhagen, Denmark, volume 161 of LIPIcs, pages 5:1–5:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [13] Michael Bendersky and W. Bruce Croft.  Discovering key concepts in verbose queries.  In Sung-Hyon Myaeng, Douglas W. Oard, Fabrizio Sebastiani, Tat-Seng Chua, and Mun-Kew Leong, editors, Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2008, Singapore, July 20-24, 2008, pages 491–498. ACM, 2008.
  * [14] Nico Bertram, Jonas Ellert, and Johannes Fischer.  Lyndon words accelerate suffix sorting.  In Mutzel et al. [87], pages 15:1–15:13.
  * [15] Timo Bingmann, Johannes Fischer, and Vitaly Osipov.  Inducing suffix and LCP arrays in external memory.  ACM J. Exp. Algorithmics, 21(1):2.3:1–2.3:27, 2016.
  * [16] Or Birenzwige, Shay Golan, and Ely Porat.  Locally consistent parsing for text indexing in small space.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 607–626. SIAM, 2020.
  * [17] Peter A. Boncz, Thomas Neumann, and Viktor Leis.  FSST: fast random access string compression.  Proc. VLDB Endow., 13(11):2649–2661, 2020.
  * [18] Dany Breslauer, Roberto Grossi, and Filippo Mignosi.  Simple real-time constant-space string matching.  Theor. Comput. Sci., 483:2–9, 2013.
  * [19] Stefan Burkhardt and Juha Kärkkäinen.  Fast lightweight suffix array construction and checking.  In Ricardo A. Baeza-Yates, Edgar Chávez, and Maxime Crochemore, editors, Combinatorial Pattern Matching, 14th Annual Symposium, CPM 2003, Morelia, Michocán, Mexico, June 25-27, 2003, Proceedings, volume 2676 of Lecture Notes in Computer Science, pages 55–69. Springer, 2003.
  * [20] Timothy M. Chan, Kasper Green Larsen, and Mihai Patrascu.  Orthogonal range searching on the ram, revisited.  In Ferran Hurtado and Marc J. van Kreveld, editors, Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011, pages 1–10. ACM, 2011.
  * [21] Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen.  Linear-time algorithm for long LCF with k mismatches.  In Gonzalo Navarro, David Sankoff, and Binhai Zhu, editors, Annual Symposium on Combinatorial Pattern Matching, CPM 2018, July 2-4, 2018 - Qingdao, China, volume 105 of LIPIcs, pages 23:1–23:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [22] Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski.  Faster algorithms for longest common substring.  In Mutzel et al. [87], pages 30:1–30:17.
  * [23] Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski.  Faster algorithms for longest common substring.  CoRR, abs/2105.03106, 2021.
  * [24] Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Radoszewski.  Longest palindromic substring in sublinear time.  In Hideo Bannai and Jan Holub, editors, 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, June 27-29, 2022, Prague, Czech Republic, volume 223 of LIPIcs, pages 20:1–20:9. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [25] Ferdinando Cicalese, Ely Porat, and Ugo Vaccaro, editors.  Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 - July 1, 2015, Proceedings, volume 9133 of Lecture Notes in Computer Science. Springer, 2015.
  * [26] Francisco Claude, Gonzalo Navarro, Hannu Peltola, Leena Salmela, and Jorma Tarhio.  String matching with alphabet sampling.  J. Discrete Algorithms, 11:37–50, 2012.
  * [27] Richard Cole, Tsvi Kopelowitz, and Moshe Lewenstein.  Suffix trays and suffix trists: Structures for faster text indexing.  Algorithmica, 72(2):450–466, 2015.
  * [28] Maxime Crochemore, Christophe Hancart, and Thierry Lecroq.  Algorithms on strings.  Cambridge University Press, 2007.
  * [29] Martin Dietzfelbinger, Joseph Gil, Yossi Matias, and Nicholas Pippenger.  Polynomial hash functions are reliable (extended abstract).  In Werner Kuich, editor, Automata, Languages and Programming, 19th International Colloquium, ICALP92, Vienna, Austria, July 13-17, 1992, Proceedings, volume 623 of Lecture Notes in Computer Science, pages 235–246. Springer, 1992.
  * [30] Patrick Dinklage, Johannes Fischer, and Alexander Herlez.  Engineering predecessor data structures for dynamic integer sets.  In David Coudert and Emanuele Natale, editors, 19th International Symposium on Experimental Algorithms, SEA 2021, June 7-9, 2021, Nice, France, volume 190 of LIPIcs, pages 7:1–7:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [31] Patrick Dinklage, Johannes Fischer, Alexander Herlez, Tomasz Kociumaka, and Florian Kurpicz.  Practical performance of space efficient data structures for longest common extensions.  In Grandoni et al. [49], pages 39:1–39:20.
  * [32] Martin Farach.  Optimal suffix tree construction with large alphabets.  In 38th Annual Symposium on Foundations of Computer Science, FOCS ’97, Miami Beach, Florida, USA, October 19-22, 1997, pages 137–143. IEEE Computer Society, 1997.
  * [33] Paolo Ferragina, Rodrigo González, Gonzalo Navarro, and Rossano Venturini.  Compressed text indexes: From theory to practice.  ACM J. Exp. Algorithmics, 13, 2008.
  * [34] Paolo Ferragina and Giovanni Manzini.  Indexing compressed text.  J. ACM, 52(4):552–581, 2005.
  * [35] Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, and Gonzalo Navarro.  An alphabet-friendly fm-index.  In Alberto Apostolico and Massimo Melucci, editors, String Processing and Information Retrieval, 11th International Conference, SPIRE 2004, Padova, Italy, October 5-8, 2004, Proceedings, volume 3246 of Lecture Notes in Computer Science, pages 150–160. Springer, 2004.
  * [36] Johannes Fischer and Pawel Gawrychowski.  Alphabet-dependent string searching with wexponential search trees.  In Cicalese et al. [25], pages 160–171.
  * [37] Johannes Fischer and Volker Heun.  Space-efficient preprocessing schemes for range minimum queries on static arrays.  SIAM J. Comput., 40(2):465–492, 2011.
  * [38] Gianni Franceschini and S. Muthukrishnan.  In-place suffix sorting.  In Lars Arge, Christian Cachin, Tomasz Jurdzinski, and Andrzej Tarlecki, editors, Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, volume 4596 of Lecture Notes in Computer Science, pages 533–545. Springer, 2007.
  * [39] Michael L. Fredman, János Komlós, and Endre Szemerédi.  Storing a sparse table with 0(1) worst case access time.  J. ACM, 31(3):538–544, 1984.
  * [40] Michael L. Fredman and Dan E. Willard.  BLASTING through the information theoretic barrier with FUSION TREES.  In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 1–7. ACM, 1990.
  * [41] Travis Gagie, Gonzalo Navarro, and Nicola Prezza.  Fully functional suffix trees and optimal text searching in BWT-runs bounded space.  J. ACM, 67(1):2:1–2:54, 2020.
  * [42] Younan Gao, Meng He, and Yakov Nekrich.  Fast preprocessing for optimal orthogonal range reporting and range successor with applications to text indexing.  In Grandoni et al. [49], pages 54:1–54:18.
  * [43] Pawel Gawrychowski and Tomasz Kociumaka.  Sparse suffix tree construction in optimal time and space.  In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 425–439. SIAM, 2017.
  * [44] Simon Gog, Timo Beller, Alistair Moffat, and Matthias Petri.  From theory to practice: Plug and play with succinct data structures.  In Joachim Gudmundsson and Jyrki Katajainen, editors, Experimental Algorithms - 13th International Symposium, SEA 2014, Copenhagen, Denmark, June 29 - July 1, 2014. Proceedings, volume 8504 of Lecture Notes in Computer Science, pages 326–337. Springer, 2014.
  * [45] Simon Gog, Juha Kärkkäinen, Dominik Kempa, Matthias Petri, and Simon J. Puglisi.  Fixed block compression boosting in fm-indexes: Theory and practice.  Algorithmica, 81(4):1370–1391, 2019.
  * [46] Simon Gog, Alistair Moffat, and Matthias Petri.  CSA++: fast pattern search for large alphabets.  In Sándor P. Fekete and Vijaya Ramachandran, editors, Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2017, Barcelona, Spain, Hotel Porta Fira, January 17-18, 2017, pages 73–82. SIAM, 2017.
  * [47] Keisuke Goto.  Optimal time and space construction of suffix arrays and LCP arrays for integer alphabets.  In Jan Holub and Jan Zdárek, editors, Prague Stringology Conference 2019, Prague, Czech Republic, August 26-28, 2019, pages 111–125. Czech Technical University in Prague, Faculty of Information Technology, Department of Theoretical Computer Science, 2019.
  * [48] Szymon Grabowski and Marcin Raniszewski.  Sampled suffix array with minimizers.  Softw. Pract. Exp., 47(11):1755–1771, 2017.
  * [49] Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors.  28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [50] Roberto Grossi and Jeffrey Scott Vitter.  Compressed suffix arrays and suffix trees with applications to text indexing and string matching.  SIAM J. Comput., 35(2):378–407, 2005.
  * [51] Manish Gupta and Michael Bendersky.  Information retrieval with verbose queries.  In Ricardo Baeza-Yates, Mounia Lalmas, Alistair Moffat, and Berthier A. Ribeiro-Neto, editors, Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, Santiago, Chile, August 9-13, 2015, pages 1121–1124. ACM, 2015.
  * [52] Dan Gusfield.  Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology.  Cambridge University Press, 1997.
  * [53] Monika Rauch Henzinger.  Finding near-duplicate web pages: a large-scale evaluation of algorithms.  In Efthimis N. Efthimiadis, Susan T. Dumais, David Hawking, and Kalervo Järvelin, editors, SIGIR 2006: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, Washington, USA, August 6-11, 2006, pages 284–291. ACM, 2006.
  * [54] Wing-Kai Hon, Kunihiko Sadakane, and Wing-Kin Sung.  Breaking a time-and-space barrier in constructing full-text indices.  SIAM J. Comput., 38(6):2162–2178, 2009.
  * [55] Tomohiro I, Juha Kärkkäinen, and Dominik Kempa.  Faster sparse suffix sorting.  In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of LIPIcs, pages 386–396. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014.
  * [56] Shunsuke Inenaga and Simon J. Puglisi, editors.  35th Annual Symposium on Combinatorial Pattern Matching, CPM 2024, June 25-27, 2024, Fukuoka, Japan, volume 296 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
  * [57] Chirag Jain, Arang Rhie, Nancy Hansen, Sergey Koren, and Adam M. Phillippy.  Long-read mapping to repetitive reference sequences using winnowmap2.  Nat Methods, 19:705–710, 2022.
  * [58] Jiaojiao Jiang, Steve Versteeg, Jun Han, Md. Arafat Hossain, Jean-Guy Schneider, Christopher Leckie, and Zeinab Farahmandpour.  P-gram: Positional n-gram for the clustering of machine-generated messages.  IEEE Access, 7:88504–88516, 2019.
  * [59] Juha Kärkkäinen and Dominik Kempa.  LCP array construction in external memory.  ACM J. Exp. Algorithmics, 21(1):1.7:1–1.7:22, 2016.
  * [60] Juha Kärkkäinen and Dominik Kempa.  LCP array construction using o(sort(n)) (or less) I/Os.  In Shunsuke Inenaga, Kunihiko Sadakane, and Tetsuya Sakai, editors, String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings, volume 9954 of Lecture Notes in Computer Science, pages 204–217, 2016.
  * [61] Juha Kärkkäinen and Dominik Kempa.  Better external memory LCP array construction.  ACM J. Exp. Algorithmics, 24(1):1.3:1–1.3:27, 2019.
  * [62] Juha Kärkkäinen, Dominik Kempa, and Simon J. Puglisi.  Parallel external memory suffix sorting.  In Cicalese et al. [25], pages 329–342.
  * [63] Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi, and Bella Zhukova.  Engineering external memory induced suffix sorting.  In Sándor P. Fekete and Vijaya Ramachandran, editors, Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2017, Barcelona, Spain, Hotel Porta Fira, January 17-18, 2017, pages 98–108. SIAM, 2017.
  * [64] Juha Kärkkäinen, Peter Sanders, and Stefan Burkhardt.  Linear work suffix array construction.  J. ACM, 53(6):918–936, 2006.
  * [65] Richard M. Karp and Michael O. Rabin.  Efficient randomized pattern-matching algorithms.  IBM J. Res. Dev., 31(2):249–260, 1987.
  * [66] Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park.  Linear-time longest-common-prefix computation in suffix arrays and its applications.  In Amihood Amir and Gad M. Landau, editors, Combinatorial Pattern Matching, 12th Annual Symposium, CPM 2001 Jerusalem, Israel, July 1-4, 2001 Proceedings, volume 2089 of Lecture Notes in Computer Science, pages 181–192. Springer, 2001.
  * [67] Dominik Kempa and Tomasz Kociumaka.  String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 756–767. ACM, 2019.
  * [68] Dominik Kempa and Tomasz Kociumaka.  Breaking the O(_n_)-barrier in the construction of compressed suffix arrays and suffix trees.  In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 5122–5202. SIAM, 2023.
  * [69] Tomasz Kociumaka.  Minimal suffix and rotation of a substring in optimal time.  In Roberto Grossi and Moshe Lewenstein, editors, 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, June 27-29, 2016, Tel Aviv, Israel, volume 54 of LIPIcs, pages 28:1–28:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
  * [70] Dmitry Kosolobov and Nikita Sivukhin.  Construction of sparse suffix trees and LCE indexes in optimal time and space.  In Inenaga and Puglisi [56], pages 20:1–20:18.
  * [71] Stefan Kurtz.  Reducing the space requirement of suffix trees.  Softw. Pract. Exp., 29(13):1149–1171, 1999.
  * [72] Ben Langmead, Cole Trapnell, Mihai Pop, and Steven L. Salzberg.  Ultrafast and memory-efficient alignment of short dna sequences to the human genome.  Genome Biology, 10(3):R25, 2009.
  * [73] Heng Li and Richard Durbin.  Fast and accurate short read alignment with burrows-wheeler transform.  Bioinform., 25(14):1754–1760, 2009.
  * [74] Ruiqiang Li, Chang Yu, Yingrui Li, Tak Wah Lam, Siu-Ming Yiu, Karsten Kristiansen, and Jun Wang.  SOAP2: an improved ultrafast tool for short read alignment.  Bioinform., 25(15):1966–1967, 2009.
  * [75] Zhize Li, Jian Li, and Hongwei Huo.  Optimal in-place suffix sorting.  Inf. Comput., 285(Part):104818, 2022.
  * [76] Glennis A. Logsdon, Mitchell R. Vollger, and Evan E. Eichler.  Long-read human genome sequencing and its applications.  Nat. Rev. Genet., 21(10):597–614, 2020.
  * [77] Grigorios Loukides and Solon P. Pissis.  Bidirectional string anchors: A new string sampling mechanism.  In Mutzel et al. [87], pages 64:1–64:21.
  * [78] Grigorios Loukides, Solon P. Pissis, and Michelle Sweering.  Bidirectional string anchors for improved text indexing and top-$k$ similarity search.  IEEE Trans. Knowl. Data Eng., 2023.
  * [79] Mamoru Maekawa.  A square root N algorithm for mutual exclusion in decentralized systems.  ACM Trans. Comput. Syst., 3(2):145–159, 1985.
  * [80] Veli Mäkinen and Gonzalo Navarro.  Position-restricted substring searching.  In José R. Correa, Alejandro Hevia, and Marcos A. Kiwi, editors, LATIN 2006: Theoretical Informatics, 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006, Proceedings, volume 3887 of Lecture Notes in Computer Science, pages 703–714. Springer, 2006.
  * [81] Udi Manber and Eugene W. Myers.  Suffix arrays: A new method for on-line string searches.  SIAM J. Comput., 22(5):935–948, 1993.
  * [82] Edward M. McCreight.  Priority search trees.  SIAM J. Comput., 14(2):257–276, 1985.
  * [83] Olena Medelyan and Ian H. Witten.  Thesaurus based automatic keyphrase indexing.  In Gary Marchionini, Michael L. Nelson, and Catherine C. Marshall, editors, ACM/IEEE Joint Conference on Digital Libraries, JCDL 2006, Chapel Hill, NC, USA, June 11-15, 2006, Proceedings, pages 296–297. ACM, 2006\.
  * [84] Donald R. Morrison.  PATRICIA - practical algorithm to retrieve information coded in alphanumeric.  J. ACM, 15(4):514–534, 1968.
  * [85] Ingo Müller, Cornelius Ratsch, and Franz Färber.  Adaptive string dictionary compression in in-memory column-store database systems.  In Sihem Amer-Yahia, Vassilis Christophides, Anastasios Kementsietsidis, Minos N. Garofalakis, Stratos Idreos, and Vincent Leroy, editors, Proceedings of the 17th International Conference on Extending Database Technology, EDBT 2014, Athens, Greece, March 24-28, 2014, pages 283–294. OpenProceedings.org, 2014.
  * [86] J. Ian Munro, Gonzalo Navarro, and Yakov Nekrich.  Space-efficient construction of compressed indexes in deterministic linear time.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 408–424, 2017.
  * [87] Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors.  29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [88] Gonzalo Navarro.  Compact Data Structures - A Practical Approach.  Cambridge University Press, 2016.
  * [89] Gonzalo Navarro and Yakov Nekrich.  Time-optimal top-k document retrieval.  SIAM J. Comput., 46(1):80–113, 2017.
  * [90] Enno Ohlebusch, Johannes Fischer, and Simon Gog.  CST++.  In Edgar Chávez and Stefano Lonardi, editors, String Processing and Information Retrieval - 17th International Symposium, SPIRE 2010, Los Cabos, Mexico, October 11-13, 2010. Proceedings, volume 6393 of Lecture Notes in Computer Science, pages 322–333. Springer, 2010.
  * [91] Michael Roberts, Wayne Hayes, Brian R. Hunt, Stephen M. Mount, and James A. Yorke.  Reducing storage requirements for biological sequence comparison.  Bioinform., 20(18):3363–3369, 2004.
  * [92] Patricia Rodriguez-Tomé, Peter Stoehr, Graham Cameron, and Tomas P. Flores.  The european bioinformatics institute (EBI) databases.  Nucleic Acids Res., 24(1):6–12, 1996.
  * [93] Kunihiko Sadakane.  Compressed suffix trees with full functionality.  Theory Comput. Syst., 41(4):589–607, 2007.
  * [94] Saul Schleimer, Daniel Shawcross Wilkerson, and Alexander Aiken.  Winnowing: Local algorithms for document fingerprinting.  In Alon Y. Halevy, Zachary G. Ives, and AnHai Doan, editors, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003, pages 76–85. ACM, 2003\.
  * [95] Kazutoshi Umemoto, Ruihua Song, Jian-Yun Nie, Xing Xie, Katsumi Tanaka, and Yong Rui.  Search by screenshots for universal article clipping in mobile apps.  ACM Trans. Inf. Syst., 35(4):34:1–34:29, 2017.
  * [96] Jeffrey Scott Vitter.  Algorithms and data structures for external memory.  Found. Trends Theor. Comput. Sci., 2(4):305–474, 2006.
  * [97] Adrian Vogelsgesang, Michael Haubenschild, Jan Finis, Alfons Kemper, Viktor Leis, Tobias Mühlbauer, Thomas Neumann, and Manuel Then.  Get real: How benchmarks fail to represent the real world.  In Alexander Böhm and Tilmann Rabl, editors, Proceedings of the 7th International Workshop on Testing Database Systems, DBTest@SIGMOD 2018, Houston, TX, USA, June 15, 2018, pages 1:1–1:6. ACM, 2018.
  * [98] Peter Weiner.  Linear pattern matching algorithms.  In 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973, pages 1–11. IEEE Computer Society, 1973\.
  * [99] Aaron M. Wenger et al.  Accurate circular consensus long-read sequencing improves variant detection and assembly of a human genome.  Nat. Biotechnol., 37:1155–1162, 2019.
  * [100] Hongyu Zheng, Carl Kingsford, and Guillaume Marçais.  Improved design and analysis of practical minimizers.  Bioinform., 36(Supplement-1):i119–i127, 2020.
  * [101] Hongyu Zheng, Guillaume Marçais, and Carl Kingsford.  Creating and using minimizer sketches in computational genomics.  J. Comput. Biol., 30(12):1251–1276, 2023.