# Optimization of the Euro-Asian network of gravitational detectors for
detecting the radiation of collapsing objects

Valentin Rudenko Corresponding Author<EMAIL_ADDRESS>Sternberg
Astronomical Institute, Lomonosov Moscow State University  Faculty of Physics,
Lomonosov Moscow State University  Department of Physics, Bauman Moscow State
Technical University  Svetlana Andrusenko  Department of Physics, Bauman
Moscow State Technical University  Daniil Krichevskiy  Sternberg Astronomical
Institute, Lomonosov Moscow State University  Department of Physics, Bauman
Moscow State Technical University  Gevorg Manucharyan  Sternberg Astronomical
Institute, Lomonosov Moscow State University  Department of Physics, Bauman
Moscow State Technical University

###### Abstract

A Euro-Asian network of four gravitational-wave (GW) interferometers is
considered, taking into account the plan to create such a detector in
Novosibirsk. The efficiency of the network is assessed by typical numerical
criteria, which also depend on the characteristics of the received signal. In
this work, we calculate the optimal orientation of the Novosibirsk detector
for the problem of detecting GW radiation accompanying the collapse of the
progenitor star with an initial angular momentum. The specificity of the
scenario is the presence of the so-called. bar stage deformation, for which
the shape of the emitted GW signal is known.

##  1 Introduction

In September 2015, the first direct registration of a gravitational-wave burst
from the merger of a relativistic binary, whose components were evaluated as
black holes (BH), took place. The detection of this event was carried out
using LIGO detectors [1]. This was followed by the registration of a big
number of events. A qualitative step was the registration by three detectors
(including a similar interferometer VIRGO in Europe) GW170814 burst from the
merger of BH binary ($M=30{M}_{\odot}$) from the distance of $540$ Mps [2],
which allowed to reduce the localization zone of the source on the celestial
sphere by an order of magnitude, up to $\sim 60$ $deg^{2}$. A gravitational
wave (GW) signal from neutron stars (NS) merger was registered, coinciding
with GRB170817A gamma burst (with $1.7$ $s$ delay) [3]. One of the most recent
significant steps is the registration of gravitational waves from the neutron
star – black hole binaries coalescence [4]. All these facts allow to claim
confidently real occurrence of a new gravitational-wave channel of
astrophysical information and heuristic value of multi-messenger astronomy,
i.e. strategy of parallel observation of transients on detectors of different
physical nature.

However, there is still no observation of gravitational waves from supernova
as well as significant coincidence between LIGO/VIGRO data and neutrino
detectors like NOvA [5] and IceCube [6] experiments. Gravitational waves from
core-collapse supernovae can serve as an important source of information about
the processes occurring during a given event [7].

In this situation, the problem of creating an optimal terrestrial network of
gravitational antennas both in terms of their location, orientation and
interconnection (methods of processing common signals against the background
of noises) is of current interest [8]. In this context, we continue the
discussion of a European-Asian network (EAN) which consists of four antennas
in the northern hemisphere: VIRGO in Italy, KAGRA in Japan, LIGO-India in
India and the planned new additional antenna in Novosibirsk. In order to
assess the scientific feasibility and eﬀiciency of such a network the
calculation of its main characteristics was performed in the approach
developed in the articles [9, 10]. In this paper we consider a gravitational
signal from core-collapse supernovae and define the optimal orientation of
Novosibirsk detector while the analysis for the case of relativistic binary
coalescence was carried out in the previous paper [11]. In order to select the
optimal detector orientation angle in Novosibirsk, we perform numerical
calculation of criteria [9]. On this basis, a generalized integral efficiency
criterion is formed, maximizing which by the angle of orientation of the
detector, we find the most effective angle of Novosibirsk detector.

Table 1 shows the coordinates of the detectors in question. The detector
orientation angle $\gamma$ is defined as the angle between the southward
direction at the detector location and the bisector of the angle formed by its
arms, measured counterclockwise. Figure 1 shows geographic location of all
detectors.

Table 1: Detector data; all angles given in degrees. Detector | Latitude $l$ | Longitude $L$ | Orientation $\gamma$
---|---|---|---
VIRGO | 43.6 | -10.5 | 206.5
KAGRA | 36.4 | -137.3 | 163.3
LIGO India | 19.6 | -77.0 | 254.0
Novosibirsk | 55.0 | -82.9 | to be defined
Figure 1: Geographic location of all detectors.

##  2 Criteria of a network

To estimate efficiency of a network of ground based detectors it’s necessary
to construct power patterns of individual components and the whole network.
Let’s result the basic information necessary for construction of the pattern.

In the long wavelength approximation (the GW wavelength is much larger than
the interferometer arm length $L$) the detector response can be evaluated as

$h(t)=\frac{\delta
L}{L}={F}_{+}(\theta,\varphi,\psi){h}_{+}(t)+{F}_{\times}(\theta,\varphi,\psi){h}_{\times}(t),$
(1)

where ${F}_{+}(\theta,\varphi,\psi)$, ${F}_{\times}(\theta,\varphi,\psi)$ are
the antenna pattern functions for the two polarizations, which are functions
of the polar angle $\theta$ and the azimuth angle $\varphi$ of the spherical
coordinate system (XY is the detector plane) and the polarization angle of the
GW $\psi$.

Antenna pattern functions have the following form (in the coordinate frame,
which basis vectors, coincide with the direction of the detector arms):

${F}_{+}=\frac{1}{2}(1+\cos^{2}{\theta})\cos{2\varphi}\cos{2\psi}-\cos{\theta}\sin{2\varphi}\sin{2\psi},$
(2)

${F}_{\times}=\frac{1}{2}(1+\cos^{2}{\theta})\cos{2\varphi}\sin{2\psi}+\cos{\theta}\sin{2\varphi}\cos{2\psi}.$
(3)

In [12] it’s shown that for a network of $N$ detectors network antenna power
pattern ${P}^{N}$:

${P}^{N}=\sum_{k=1}^{4}{({F}_{+,k}^{2}+{F}_{\times,k}^{2})}.$ (4)

Figure 2 shows EAN network power pattern.

Figure 2:  EAN network power pattern.

In order to choose the optimal detector angle in Novosibirsk, we use 3
independent criteria presented in the works [9, 10]. These three conditions
form an integral criterion, which is to be maximized by changing the
orientation of the Novosibirsk detector, to find the most effective angle.

###  2.1 Polarization criterion I

Criterion I characterizes ability of the network to assess the polarization of
the received GW. Following [9] we define $+$ and $\times$ integral functions
for a network of four detectors:

${F}^{N}=\frac{1}{2}\sqrt{{F}_{1}^{2}+{F}_{2}^{2}+{F}_{3}^{2}+{F}_{4}^{2}},$
(5)

where $N$ \- stands for a network function and ${F}_{1}...{F}_{4}$ all either
correspond to the $+$ or $\times$ polarization. Obviously ${F}^{N}$ depend on
the polarization angle of $\psi$.

Calculation of I is carried out in dominant polarization frame (DPF) [13]. In
DPF for each point on the celestial sphere $(\alpha;\delta)$ (in equatorial
coordinate system point is defined by right ascension $\alpha\in[-\pi;\pi]$
and declination $\delta\in[-\frac{\pi}{2};\frac{\pi}{2}]$) a polarization
angle that maximizes the network factor ${F}_{+}^{N}$ and minimizes
${F}_{\times}^{N}$ is chosen. Consequently, for this direction
$(\alpha;\delta)$ the condition ${F}_{+}^{N}\geq{F}_{\times}^{N}$ is valid.
The condition of approximate equality of factors ${F}_{\times}^{N}$ and
${F}_{+}^{N}$ has to be kept, i.e.
$\frac{{F}_{\times}^{N}}{{F}_{+}^{N}}\approx 1$. This means that the gravity
detector network will be sensitive to both gravity wave polarizations. It
follows that a minimum difference of
$\left|{F}_{\times}^{N}-{F}_{+}^{N}\right|$ should be sought for all
$(\alpha;\delta)$. This leads to the quantitative formulation of the
polarization criterion I [9]:

$I={\left(\frac{1}{4\pi}\oiint{{\left|{F}_{+}^{N}(\alpha;\delta)-{F}_{\times}^{N}(\alpha;\delta)\right|}^{2}d\Omega}\right)}^{-1/2},$
(6)

where averaging of $\left|{F}_{\times}^{N}-{F}_{+}^{N}\right|$ over celestial
sphere takes place ($d\Omega$ \- solid angle). The bigger is $I$ the smaller
is the averaged difference $\left|F^{N}_{\times}-F^{N}_{+}\right|$.

###  2.2 Localization criterion D

Criterion D characterizes the ability of a network to define angular position
of a source. In astrometry the problem of a source localization on celestial
sphere of a radiation source is solved by a method of triangulation.
Triangulation is based on the difference in time between the registration of
signals by network detectors. The further apart the detectors are, the greater
the time delay is. To maximize the source location accuracy on the celestial
sphere, the telescopes should be placed as far apart from each other as
possible. According to [9], for a network of four detectors $D$ is calculated
as the area of the triangle formed by the three detectors in the network,
which has the largest area among all possible combinations. If $O$ \- the
center of the Earth, $A$, $B$, $C$ \- points where the detectors are located,
the area of the corresponding triangle:

$S_{ABC}=1/2|[\overrightarrow{AC},\overrightarrow{AB}]|=1/2|[\overrightarrow{OC}-\overrightarrow{OA};\overrightarrow{OB}-\overrightarrow{OA}]|.$
(7)

###  2.3 Parameters reconstruction criterion R

Criterion R characterizes the possibility of reconstruction the parameters of
the signal of a known analytical form. According to the Maximum likelihood
estimation in the additive Gaussian noise background model, the parameters of
the received signal are evaluated by the Rao-Cramer bound. The best possible
estimates are obtained using the Fisher information matrix
${\Gamma}_{\alpha\beta}$ [14] in accordance with the formula

${\Gamma}_{\alpha\beta}=Re\left\\{4\int_{{f}_{min}}^{{f}_{max}}{\frac{\overline{{\partial}_{\alpha}\tilde{h}(f)}{\partial}_{\beta}\tilde{h}(f)}{{S}_{n}(f)}df}\right\\},$
(8)

where $\tilde{h}(f)$ is the Fourier image of response of the detector, the
line above the Fourier image of response represents the complex conjugate, and
${S}_{n}(f)$ is the spectral noise density of a single detector. In this paper
we assume for simplicity that all detectors have the same noise properties
presented in [15].

Rao-Cramer bound determines the best possible accuracy of parameter $P$
estimation [14]:

${\delta P}^{2}={\left({\Gamma}_{N}^{-1}\right)}_{PP},$ (9)

where ${\Gamma}_{N}=\sum_{i=1}^{N}{{\Gamma}_{i}}$, i.e. the Fisher information
matrix for detector network, is the sum of the corresponding detector matrices
constituting the network. The inverse value of the celestial-averaged relative
error is a numerical expression of criterion $R$:

$R={\left(\frac{1}{4\pi}\oiint{{\left(\frac{\delta
P}{P}\right)}^{2}d\Omega}\right)}^{{-1}/{2}}={\left<\frac{\delta
P}{P}\right>}^{-1},$ (10)

Maximization of criterion $R$ leads to the minimum relative error averaged
over the celestial sphere in the estimation of the parameter.

###  2.4  Integral criterion C

Integral criterion $C$ is used to compare different configurations of a
network:

$C=\sqrt{(\frac{I}{I_{max}})^{2}+(\frac{D}{D_{max}})^{2}+(\frac{R}{R_{max}})^{2}}$
(11)

Criteria $I$, $D$ and $R$ together define a three-dimensional space that can
be used to define a point which describes a particular configuration.
Maximization of $C$ by orientation angle of the detector in Novosibirsk gives
the optimal orientation angle and leads to values
$I(\gamma^{max}_{Nsk})=I_{max},D(\gamma^{max}_{Nsk})=D_{max}$ and
$R(\gamma^{max}_{Nsk})=R_{max}$ (from the definition it’s clear $C_{max}=1$).

##  3 Source

In this paper we considered EAN efficiency of in registration of gravitational
waves from core-collapse supernovae. During the core-collapse there exist many
mechanisms of gravitational waves radiation on different stages of the process
[16]. As Fisher matrix approach (8) requires analytical form of the signal we
have considered gravitational waves from long-lived rotational instabilities
of a proto-neutron star. If the key result of this instabilities is bar
deformation that the radiation can be simulated by radiation from a rotating
cylinder (axis of rotation is a bisector of the cylinder axis) with a Gaussian
exponent which is introduced phenomenologically to take into account
finiteness of the signal:

$h(t)=\sqrt{F^{2}_{+}+F^{2}_{\times}}\frac{GM\omega^{2}L^{2}}{3c^{4}r}(1-3\varepsilon^{2})e^{-\frac{4(t-t_{0})^{2}}{t^{2}_{0}}}cos(2\omega
t+\phi),$ (12) $\phi=\pi+\tan^{-1}\frac{F_{+}}{F_{\times}},$ (13)

where $G$ is Newtonian constant of gravitation, $c$ \- speed of light, $M$ \-
mass of the source, $L$ \- length of the cylinder, $R$ \- radius of the
cylinder, $\omega$ \- source angular frequency, $t_{0}$ \- characteristic
signal length and parameter $\varepsilon=\frac{R}{L}$ characterizes the degree
of deformation and is used for calculation of criterion $R$ (10).
Gravitational radiation carries away energy from the system so $\omega$
decreases over time. However for typical values of source parameters [16]
$\omega=2\pi\times 700$ rad/s, $L=20$ km, $R=5$ km, $M=M_{\odot}$ and
$t_{0}=1$ s calculation of gravitational waves luminosity via Einstein’s
formula [17]:

$L_{GW}=\frac{G}{5c^{5}}\left<\sum^{3}_{j,k=1}\dddot{Q}_{jk}(t-\frac{r}{c})\dddot{Q}_{jk}(t-\frac{r}{c})\right>,$
(14)

where $Q_{jk}$ \- reduced quadrupole moment and dot denotes time derivative,
leads to $\frac{\Delta\omega}{\omega}\sim 10^{-7}$, so we consider $\omega$ to
be constant.

##  4 Numerical results and conclusions

In the case of gravitational collapse the strain $h(t)$ is expected to be
several orders of magnitude less than for binary coalescence ($h\sim
10^{-22}-10^{-20}$ at $10$ kpc) so we can’t assume isotropic distribution of
sources over the celestial sphere. Instead we integrate over the Milky Way
disk (neglecting the fact that the sensitivity may be sufficient for detection
of the signal from several nearby galaxies). Due to rotation of the Earth
antenna pattern functions ${F}_{+}$ and ${F}_{\times}$ depend on time (and
consequently $P=P(t)$, $\phi=\phi(t)$) thus we average functions of time over
24 hours which also makes analytical calculation of Fourier image
$\tilde{h}(f)$ in (8) possible (see Figure 3 as an example).

Figure 3: Averaged antenna power pattern for detector in Novosibirsk. Figure
4: Dependence of all criteria on orientation angle of detector in Novosibirsk.
Figure 5: Dependence of R criterion on orientation angle of detector in
Novosibirsk. Figure 6: Optimal orientation of the detector in Novosibirsk.

The calculation results are shown in Figure 4 and Figure 5. Criterion $D$
obviously does not depend on the orientation angle of the detector in
Novosibirsk. $I$ is the most sensitive criterion to changes of orientation
angle. The maximum value of integral criterion $C$ is achieved at
${\gamma}_{Nsk}^{max}={40}^{\circ}$ (see Figure 6). It’s worth noting that the
optimal angle differs from the case of binary coalescence - ${13}^{\circ}$
[11]. The final choice depends on the most topical problems at the time of
construction of the detector in Novosibirsk. To conclude we notice that the
choice of the source is a limitation of this paper, because more significant
physics is encrypted in a more complex structure of the signal from the core
collapse, but such signals are model-dependent and do not have an analytical
form (e.g. [18]), which does not allow using them within the framework of this
approach.

## Acknowledgments

The authors are grateful to V.I.Pustovoit, A.N.Morozov and V.L.Kauts for their
attention to this work and useful discussions.

This work was supported by the grant RFBR 19-29-11010.

## References

  * [1] Abbott B P et al. 2016 Phys. Rev. Lett. 116(6) 061102
  * [2] Abbott B P et al. 2017 Phys. Rev. Lett. 119(14) 141101
  * [3] Abbott B P et al. 2017 Phys. Rev. Lett. 119(16) 161101
  * [4] Abbott R et al. 2021 ApJL 915 L5
  * [5] Acero M A et al. (NOvA Collaboration) 2020 Phys. Rev. D 101(11) 112006
  * [6] Veske D et al. 2021 PoS ICRC2021 950
  * [7] Fryer C L and New K C B 2011 Living Rev. Relativ. 14 1
  * [8] Gusev A and Rudenko V 2019 Moscow Univ. Phys. 74 115–123
  * [9] Raffai P et al. 2013 Class. Quantum Grav. 30 155004
  * [10] Hu Y M et al. 2015 Class. Quantum Grav. 32 105010
  * [11] Rudenko V, Andrusenko S, Krichevskiy D and Manucharyan G 2020 Universe 6 140
  * [12] Finn L S 2001 Physical Review D 63 102001
  * [13] Klimenko S et al. 2011 Phys. Rev. D 83(10) 102001
  * [14] Kocsis B, Haiman Z, Menou K and Frei Z 2007 Phys. Rev. D 76(2) 022003
  * [15] LIGO 2009 lIGO Document T0900288-v3 URL https://dcc.ligo.org/LIGO-T0900288/public
  * [16] Gossan S E et al. 2016 Phys. Rev. D 93(4) 042002
  * [17] Landau L D and Lifshitz E M 1980 The Classical Theory of Fields: Volume 2 (Butterworth-Heinemann)
  * [18] Dimmelmeier H et al. 2008 Phys. Rev. D 78(6) 064056


# Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast

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  Hilde Verbeek
CWI, Amsterdam, The Netherlands

###### Abstract

Sparse suffix sorting is the problem of sorting $b=o(n)$ suffixes of a string
of length $n$. Efficient sparse suffix sorting algorithms have existed for
more than a decade. Despite the multitude of works and their justified claims
for applications in text indexing, the existing algorithms have not been
employed by practitioners. Arguably this is because there are no simple,
direct, _and_ efficient algorithms for sparse suffix array construction. We
provide two new algorithms for constructing the sparse suffix and LCP arrays
that are simultaneously simple, direct, small, and fast. In particular, our
algorithms are: _simple_ in the sense that they can be implemented using only
basic data structures; _direct_ in the sense that the output arrays are not a
byproduct of constructing the sparse suffix tree or an LCE data structure;
_fast_ in the sense that they run in $\mathcal{O}(n\log b)$ time, in the worst
case, or in $\mathcal{O}(n)$ time, when the total number of suffixes with an
LCP value greater than $2^{\lfloor\log\frac{n}{b}\rfloor+1}-1$ is in
$\mathcal{O}(b/\log b)$, matching the time of the optimal yet much more
complicated algorithms [Gawrychowski and Kociumaka, SODA 2017; Birenzwige et
al., SODA 2020]; and _small_ in the sense that they can be implemented using
_only_ $8b+o(b)$ machine words. Our algorithms are simplified, yet non-
trivial, space-efficient adaptations of the Monte Carlo algorithm by I et al.
for constructing the sparse suffix tree in $\mathcal{O}(n\log b)$ time [STACS
2014]. We also provide proof-of-concept experiments to justify our claims on
simplicity and efficiency.

##  1 Introduction

Let $T=T[1\mathinner{.\,.}n]$ be a string of length $n$ over an ordered
alphabet $\Sigma$. Further let $\mathcal{B}\subseteq[1,n]$ be a set of $b>1$
positions in $T$. _Sparse suffix sorting_ is the problem of sorting the set of
suffixes $T_{\mathcal{B}}=\\{T[i\mathinner{.\,.}n]:i\in\mathcal{B}\\}$
lexicographically [17]. This is achieved by constructing the sparse suffix
array. The _sparse suffix array_
$\textsf{SSA}=\textsf{SSA}[1\mathinner{.\,.}b]$ is the array containing the
positions in $\mathcal{B}$ in the lexicographical order of the suffixes in
$T_{\mathcal{B}}$. The associated _sparse longest common prefix array_
$\textsf{SLCP}=\textsf{SLCP}[1\mathinner{.\,.}b]$ stores the length
$\textsf{SLCP}[i]$ of the longest common prefix of
$T[\textsf{SSA}[i-1]\mathinner{.\,.}n]$ and
$T[\textsf{SSA}[i]\mathinner{.\,.}n]$ when $i\in[2,n]$ or 0 when $i=1$. The
SSA and SLCP array can be used to construct the sparse suffix tree in linear
time using the algorithm by Kasai et al. [19]. The _sparse suffix tree_ is the
compacted trie of the set $T_{\mathcal{B}}$. Vice-versa, the SSA and SLCP
array can be obtained in linear time using a pre-order traversal of the sparse
suffix tree.

Sparse suffix sorting was introduced as a fundamental step in the construction
of compressed or sparse text indexes [17]. Modern compressed text indexes [22,
9], practical indexes for long patterns [14, 21, 2], and sublinear-space
string algorithms [3, 4] rely on sparse suffix sorting: they first sample a
sublinear number of “important” suffixes, which they next sort to construct
their final solution. Efficient sparse suffix sorting algorithms have existed
for more than a decade. The following algorithms construct SSA explicitly, or
implicitly by first constructing the sparse suffix tree. Since the size of SSA
(and the size of sparse suffix tree) is $\Theta(b)$, the goal of these
algorithms is to use $\mathcal{O}(b)$ words of space assuming read-only random
access to $T$:

  * •

Kärkkäinen et al. presented a deterministic $\mathcal{O}(n^{2}/s)$-time and
$\mathcal{O}(s)$-space algorithm, for any $s\in[b,n]$ [16, Section 8].

  * •

Bille et al. presented a Monte Carlo $\mathcal{O}(n\log^{2}b)$-time and
$\mathcal{O}(b)$-space algorithm [5]. They also presented a Las Vegas
$\mathcal{O}(n\log^{2}n+b^{2}\log b)$-time and $\mathcal{O}(b)$-space
algorithm.

  * •

I et al. presented a Monte Carlo $\mathcal{O}(n+(bn/s)\log s)$-time and
$\mathcal{O}(b)$-space algorithm, for any $s\in[b,n]$ [15]. They also
presented a Las Vegas $\mathcal{O}(n\log b)$-time and $\mathcal{O}(b)$-space
algorithm.

  * •

Gawrychowski and Kociumaka [13] presented a Monte Carlo $\mathcal{O}(n)$-time
and $\mathcal{O}(b)$-space algorithm. They also presented a Las Vegas
$\mathcal{O}(n\sqrt{\log b})$-time and $\mathcal{O}(b)$-space algorithm.

  * •

Birenzwige et al. [6] presented a Las Vegas algorithm running in
$\mathcal{O}(n)$ time using $\mathcal{O}(b)$ space. They also presented a
deterministic $\mathcal{O}(n\log\frac{n}{b})$-time and $\mathcal{O}(b)$-space
algorithm, for any $b=\Omega(\log n)$.

The following algorithms also construct SSA, but they work in the _restore
model_ [8]: an algorithm is allowed to overwrite parts of the input, as long
as it can restore it to its original form at termination.

  * •

Fischer et al. [11] presented a deterministic $\mathcal{O}(c\sqrt{\log
n}+b\log b\log n\log^{*}n)$-time and $\mathcal{O}(b)$-space algorithm, where
$c$ is the number of letters that must be compared for distinguishing the
suffixes in $T_{\mathcal{B}}$. In some cases, this runs in sublinear extra
time; extra refers to the linear cost of loading $T$ in memory.

  * •

Prezza [24] presented a Monte Carlo $\mathcal{O}(n+b\log^{2}n)$-time algorithm
using $\mathcal{O}(1)$ words of space.

#### Motivation.

Despite the multitude of works on sparse suffix sorting and their justified
claims for applications in text indexing, the existing algorithms have not
been employed by practitioners. Arguably this is because there are no simple,
direct, _and_ efficient algorithms for SSA construction. The
$\mathcal{O}(n)$-time algorithms of Gawrychowski and Kociumaka [13] and of
Birenzwige et al. [6] are far from simple and do not seem to be practically
promising either. The former (Monte Carlo) algorithm relies heavily on the
construction of compacted tries, which induce high constants in space usage,
and on a recursive application of difference cover to construct a Longest
Common Extension (LCE) data structure. The latter (Las Vegas) algorithm relies
on an intricate partitioning scheme (sampling) to construct SSA and on an LCE
data structure to compute the SLCP array. The Monte Carlo $\mathcal{O}(n\log
b)$-time algorithm of I et al. [15] is simple but it also relies heavily on
compacted tries, which makes it less likely to be employed by practitioners
for SSA construction. The Monte Carlo $\mathcal{O}(n+b\log^{2}n)$-time
algorithm of Prezza [24] makes heavy usage of an LCE data structure as well:
constructing the SSA and SLCP array is a byproduct of an in-place LCE data
structure. This algorithm is, to the best of our knowledge, the only algorithm
which has been implemented (at least in a simplified form). Due to the
interest in sparse suffix sorting and the above characteristics of the
existing algorithms, we were motivated to revisit this problem to develop
efficient, yet simple and direct, algorithms for SSA construction. Such
algorithms may serve as baselines for practitioners to engineer the SSA and
SLCP array construction.

#### Our Results.

We assume the standard word RAM model with word size $\Theta(\log n)$; basic
arithmetic and bit-wise operations on $\mathcal{O}(\log n)$-bit integers take
$\mathcal{O}(1)$ time. We assume that we have a read-only random access string
$T$ of length $n$ over an integer alphabet
$\Sigma=\\{1,\ldots,n^{\mathcal{O}(1)}\\}$, a read-only integer array $A$ of
size $b$ storing the $b$ elements of $\mathcal{B}$, and two write-only integer
arrays SSA and SLCP, each of size $b$. We count the amount of _extra space in
machine words_ used to construct the SSA and SLCP array. We present two
algorithms:

  1. 1.

Our first algorithm, Main-Algo, constructs SSA and SLCP _directly_ ; i.e.,
without first explicitly constructing the sparse suffix tree or an LCE data
structure. Its time complexity is $\mathcal{O}(n+(bn/s)\log s))$ and its space
complexity is $s+7b+\mathcal{O}(1)$ machine words, for any chosen $s\in[b,n]$.
It is a Monte Carlo algorithm that returns the correct output _with high
probability_ ; i.e., with probability at least $1-n^{-c}$, for any constant
$c\geq 1$ chosen at construction time. Main-Algo is _simple_ in the sense that
it can be implemented using only _basic data structures_ (e.g., dictionaries
and arrays) readily available in any widely-used programming language (e.g.,
C++ or Python). Main-Algo is a simplified yet non-trivial, space-efficient
simulation of the algorithm by I et al. for sparse suffix tree construction
[15]. A disadvantage of these two algorithms is that they attain the
$\Theta(n\log b)$ time bound for $s=b$ _in any case_. In response, we develop
Parameterized-Algo, a parameterized algorithm which is input-sensitive.

  2. 2.

Our second algorithm, Parameterized-Algo, also constructs SSA and SLCP
directly. Its time complexity is $\mathcal{O}(n+(b^{\prime}n/b)\log b)$ and
its space complexity is $8b+4b^{\prime}+\mathcal{O}(1)$ machine words, where
$b^{\prime}$ is the total number of suffixes $\textsf{SSA}[i]\in\mathcal{B}$
with $\textsf{SLCP}[i]\geq\ell$ or $\textsf{SLCP}[i+1]\geq\ell$, where
$\ell=2^{\lfloor\log\frac{n}{b}\rfloor+1}-1$. When
$b^{\prime}=\mathcal{O}(b/\log b)$, Parameterized-Algo runs in
$\mathcal{O}(n)$ time, thus matching the time of the optimal yet much more
complicated algorithms in [13, 6], using _only_ $8b+o(b)$ machine words. It is
a Monte Carlo algorithm that returns the correct output with high probability.
It is _remarkably simple_ as it consists of two calls of Main-Algo and a
linear-time step that merges the partial results (however, the proof of
correctness requires some work). The running time of Parameterized-Algo is
good in the following sense: if the instance is reasonably sparse, then $\ell$
is large and likely $b^{\prime}=\mathcal{O}(b/\log b)$, thus it runs in
$\mathcal{O}(n)$ time. In any case, it runs in $\mathcal{O}(n\log b)$ time.
For instance, for the full human genome (v. GRCh38) as $T$, where $n\approx
3\cdot 10^{9}$, and for $b=\sqrt{n}=56137$ suffixes selected uniformly at
random, $b^{\prime}=2525<b/\log b<3559$. We also analyze the time complexity
of Parameterized-Algo on random strings and show that it works in
$\mathcal{O}(n)$ time (after a small amendment), for any string chosen
uniformly at random from $\Sigma^{n}$ and any set $T_{\mathcal{B}}$ of $b$
suffixes of $T$, with high probability.

To fully justify our claims, we also provide proof-of-concept experiments. For
comparison purposes, we had to resort to Prezza’s implementation of his
algorithm from [24], which works in the restore model, and it is the only
available implementation. Our experiments show that for realistically sparse
instances of real-world datasets (i.e., for $b\in[n/10^{5},n/10^{3}]$), our
implementation of Parameterized-Algo: (i) runs in linear time (i.e., it is not
substantially affected when $b$ increases); and (ii) clearly outperforms
Prezza’s implementation both in terms of time (even if the latter uses the
$\Omega(n\log|\Sigma|)$ bits of $T$) and space.

##  2 Preliminaries

We consider finite strings over an integer alphabet
$\Sigma=\\{1,\ldots,n^{\mathcal{O}(1)}\\}$. The elements of $\Sigma$ are
called _letters_. A _string_ $T=T[1\mathinner{.\,.}n]$ is a sequence of
letters from $\Sigma$; we denote by $|T|=n$ the _length_ of $T$. The fragment
$T[i\mathinner{.\,.}j]$ of $T$ is an _occurrence_ of the underlying
_substring_ $P=T[i]\ldots T[j]$ occurring at _position_ $i$ in $T$. A prefix
of $T$ is a substring of $T$ of the form $T[1\mathinner{.\,.}j]$ and a suffix
of $T$ is a substring of $T$ of the form $T[i\mathinner{.\,.}n]$.

#### Karp-Rabin Fingerprints.

Let $T$ 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 Karp-Rabin (KR) fingerprint
[18] of $T[i\mathinner{.\,.}j]$ is defined as:

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

Clearly, if $T[i\mathinner{.\,.}i+\ell]=T[j\mathinner{.\,.}j+\ell]$ then
$\phi_{T}(i,i+\ell)=\phi_{T}(j,j+\ell)$. On the other hand, if
$T[i\mathinner{.\,.}i+\ell]\neq T[j\mathinner{.\,.}j+\ell]$ then
$\phi_{T}(i,i+\ell)\neq\phi_{T}(j,j+\ell)$ with probability at least
$1-\ell/p$ [10]. 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})$ (but still small enough to fit in $\mathcal{O}(1)$
machine words) to make the KR fingerprint function perfect with probability at
least $1-n^{-c}$.

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

Any string $T\in\Sigma^{n}$ can be preprocessed in $\mathcal{O}(n)$ time using
$s+\mathcal{O}(1)$ machine words, for any $s\in[1,n]$, so that the KR
fingerprint of any length-$k$ fragment of $T$ is computed in
$\mathcal{O}(\min\\{k,n/s\\})$ time.111I et al. [15] claim $\mathcal{O}(s)$
space but from their construction it is evident that in fact
$s+\mathcal{O}(1)$ machine words are used.

I et al. [15] employ the _distribute-and-collect_ technique [23] to group $b$
suffixes, according to a fixed-length common prefix by using their KR
fingerprints, in $\mathcal{O}(b\log_{s}n)$ time. We instead use hashing to
achieve the same result in $\mathcal{O}(b)$ time with high probability. This
gives improved running times in some special regimes (see Theorem 2 and
Theorem 3). It also simplifies our algorithms in terms of implementation since
efficient hashing implementations are readily available in any widely-used
programming language.

##  3 Main Algorithm

#### Overview.

A summary of our main algorithm (Main-Algo) follows with references to the
pseudocode given in Algorithms 1 and 2.222The pseudocode is complete in the
sense that it only assumes the implementation of Lemma 1 (Line 11). As input,
it takes a string $T$ from $\Sigma^{n}$ and an array $A$ of $b$ elements,
indicating the starting positions of the suffixes that need to be sorted. As
additional input, it takes an integer $j_{\text{start}}$, which defines the
number of iterations. In this section, $j_{\text{start}}$ is set to
$\lfloor\log n\rfloor$, but a different value is used for the parameterized
algorithm in Section 4.

During the first phase (Algorithm 1, Lines 1-25), the suffixes are distributed
into groups such that all suffixes belonging to a particular group share a
common prefix. At the end of this process, we are left with a hierarchy of
groups that describes the exact longest common prefixes between suffixes. The
members of each group are then sorted lexicographically (Algorithm 1, Lines
26-27), which is made possible by knowing their longest common prefixes, such
that a traversal of the hierarchy will yield the suffixes in lexicographic
order. This traversal is the second phase (Algorithm 1, Line 28 and Algorithm
2): a simple depth-first search is used to construct the sparse suffix array
and accompanying sparse LCP array from the hierarchy.

Algorithm 1 Main-Algo

Input: string $T\in\Sigma^{n}$, integer $b$, array $A$ of $b$ distinct
integers from $[n]$, and integer $j_{\text{start}}$ (default $\lfloor\log
n\rfloor$)
Output: arrays SSA and SLCP

1:$m\leftarrow b+1$ $\triangleright$ The number of currently used id’s

2:$L_{m}\leftarrow(1,\dots,b)$ $\triangleright$ The first group

3:$B\leftarrow\\{(m,0,L_{m})\\}$ $\triangleright$ List containing the first
group $L_{m}$ with id $m$ and LCP value $0$

4:$A[m]\leftarrow A[1]$ $\triangleright$ Choose a witness for group with id
$m$ and extend $A$

5:for $j=j_{\text{start}},\ldots,0$ do $\triangleright$ For all relevant
powers of $2$ down to $0$

6: $B^{\prime}\leftarrow$ empty list$\triangleright$ List to store the new
groups

7: for $(i,k,L_{i})\in B$ do $\triangleright$ For every group

8: $H_{i}\leftarrow$ empty hash table $\triangleright$ key: the fingerprint of
the group member; value: id’s of the members

9: $s\leftarrow|L_{i}|$ $\triangleright$ To memorize the original size of
$L_{i}$

10: for $l\in L_{i}$ do $\triangleright$ Partition group $L_{i}$ according to
LCP value $k+2^{j}$

11: $h\leftarrow\phi_{T}(A[l],A[l]+k+2^{j}-1)$ $\triangleright$ Fingerprint of
$T[A[l]\mathinner{.\,.}A[l]+k+2^{j}-1]$ using Lemma 1

12: $H_{i}[h].\text{append}(l)$ $\triangleright$ Append id $l$ as a value of
fingerprint $h$ to a satellite vector

13: $L_{i}.\text{erase}(l)$ $\triangleright$ Remove $l$ from $L_{i}$ (to save
space) – $L_{i}$ is empty at the end of the loop

14: for $h\in H_{i}$ do $\triangleright$ For every fingerprint in the hash
table

15: $f\leftarrow H_{i}[h]$ $\triangleright$ Let $f$ denote the vector of id’s
with fingerprint $h$

16: if $|f|=s$ then $\triangleright$ All members belong to the same group

17: $B\leftarrow B\setminus\\{(i,k,L_{i})\\}\cup\\{(i,k+2^{j},f)\\}$
$\triangleright$ The old group is replaced due to a longer LCP

18: else if $|f|\geq 2$ then $\triangleright$ New group $f$ must be created

19: $m\leftarrow m+1$ $\triangleright$ New group id

20: $L_{i}.\text{append}(m)$ $\triangleright$ Append the new id to $L$ of
tuple $(i,k,L)\in B$

21: $B^{\prime}\leftarrow B^{\prime}\cup\\{(m,k+2^{j},f)\\}$ $\triangleright$
New group $f$ with id $m$ and LCP value $k+2^{j}$ is created

22: $A[m]\leftarrow A[f[1]]$ $\triangleright$ Choose witness $A[f[1]]$ for
group with id $m$ and extend $A$

23: else if $|f|=1$ then

24: $L_{i}.\text{append}(f)$ $\triangleright$ Append the old id (only element
of $f$) back to $L_{i}$

25: $B.\text{append}(B^{\prime})$ $\triangleright$ Append $B^{\prime}$ to $B$

26:for $(i,k,L_{i})\in B$ do

27: $L_{i}.\text{sort}(l\mapsto T[A[l]+k])$ $\triangleright$ Sort group in
ascending order w.r.t. $T[A[l]+k]$ using in-place sort

28:return $\textsc{Output-Arrays}(B,b,A)$ $\triangleright$ See Algorithm 2

Algorithm 2 Output-Arrays

Input: List $B$ of tuples $(i,k,L_{i})$ expected in ascending order by $i$,
integer $b$, and array $A$
Output: SSA and SLCP

1:$\textsf{SSA}\leftarrow$ empty array

2:$\textsf{SLCP}\leftarrow$ empty array

3:$S\leftarrow$ empty stack

4:$S.\text{push}((b+1,0))$ $\triangleright$ The initial entry of the stack
relating to the first group which has LCP value 0

5:$\ell\leftarrow 0$ $\triangleright$ Variable tracking the least LCP value
encountered since the last suffix

6:while $S$ is not empty do

7: $(i,\ell^{\prime})\leftarrow S.\text{pop}()$

8: if $\ell^{\prime}<\ell$ then $\triangleright$ Update $\ell$ if it is less
than before

9: $\ell\leftarrow\ell^{\prime}$

10: if $i\leq b$ then $\triangleright$ Member $i$ is a suffix: add it to SSA
and SLCP

11: SSA.append$(A[i])$

12: SLCP.append$(\ell)$

13: $\ell\leftarrow\infty$ $\triangleright$ Reset $\ell$

14: else$\triangleright$ Member $i$ is a group: add its members to the stack

15: $(i,k,L_{i})\leftarrow B[i-b]$

16: for $i^{\prime}\in L_{i}$ in reverse order do $\triangleright$ Since the
stack is FILO, the first entry needs to be added last

17: $S.\text{push}((i^{\prime},k))$

18:return SSA and SLCP

###  3.1 Computing and Sorting the LCP Groups

During the first phase, the suffixes of $A$ are organized into several groups,
stored in list $B$. Each group in $B$ is represented by a triple
$(i,k,\\{v_{1},\ldots,v_{n_{i}}\\})$, where $i$ is the index (id) of the
group, $k$ is its associated LCP value and $v_{1}$ through $v_{n_{i}}$ are its
members, which are either suffixes or other groups. To distinguish between
suffixes and groups, the indices $1$ through $b$ are reserved for the suffixes
in $A$ and the group numbering starts at $b+1$. At every point of the
algorithm, it holds that in a group $(i,k,\\{v_{1},\ldots,v_{n_{i}}\\})$, all
suffixes and groups (with their respective suffixes) in
$\\{v_{1},\ldots,v_{n_{i}}\\}$ share a prefix of length _at least_ $k$. At the
start (base case), there exists just one group $(b+1,0,\\{1,\ldots,b\\})$
(Line 3) containing all suffixes as members.

The LCP groups are then “refined” (the refinement process will be explained
immediately) over the course of $\lfloor\log n\rfloor$ iterations, such that
in the end each group describes the exact longest common prefix of its members
rather than just a lower bound. Specifically, by the end of iteration $j$
(where $j$ descends from $\lfloor\log n\rfloor$ down to zero), in a group with
LCP value $k$, two suffixes will have an actual longest common prefix of at
least $k$ and at most $k+2^{j}-1$ letters. This gap is closed once $j$ has
reached zero, at which point the refinement process is completed. The
algorithm allows specifying a different starting value for $j$ than
$\lfloor\log n\rfloor$, through the parameter $j_{\text{start}}$. This is used
in the parameterized algorithm described in Section 4.

The refinement process works as follows in iteration $j$. We refine every
existing group; let one such group be $(i,k,\\{v_{1},\ldots,v_{n_{i}}\\})$. We
create a hash table (Line 8) and for every group member, with index $v_{i}$,
we take the KR fingerprint as per Lemma 1 of
$T[A[v_{i}]+k\mathinner{.\,.}A[v_{i}]+k+2^{j}-1]$ (Line 11).333This assumes
that $A[b_{i}]+k+2^{j}-1\leq n$; if this is not the case, the suffix ends at
position $n$. If $v_{i}$ denotes a group, we do the same thing using any given
suffix belonging to that group; this is easily achieved by appending “witness”
suffixes to $A$ for every created group as seen in Lines 4 and 22. (Any suffix
can be a witness but we choose the one with the smallest index.) All the
members are grouped in the hash table based on their KR fingerprints: if two
suffixes have the same KR fingerprint, they will end up in the same entry of
the hash table and with high probability have the same prefix of length
$k+2^{j}$. To save space, entries are removed from the group as they are added
to the hash table (Line 13). All entries of the hash table are then inspected
(Line 14). We distinguish three cases. In case 1 (Lines 16-17), if all
suffixes in a group end up having the same KR fingerprint, we update the LCP
value of the old group to $k+2^{j}$ rather than creating a new group. In case
2 (Lines 18-22), if two or more suffixes have the same KR fingerprint, a new
group is made with LCP value $k+2^{j}$, containing these suffixes, and added
to $B$ (Lines 18-22). After removing the suffixes from their original group,
we replace them with the index of the newly created group (Line 20). In case 3
(Lines 23-24), if a suffix is not grouped with any other suffix, we append it
back to the group it originated from.

Once the iteration with $j=0$ ends, all LCP groups describe the exact longest
common prefix of their members.444This is not true when $j_{\text{start}}$ was
set to a value less than $\lfloor\log n\rfloor$; in this case, the LCP values
are only correct if they are less than $2^{j_{\text{start}}+1}-1$; this is
expanded on in Section 4. We now sort the members of every group
lexicographically (Lines 26-27). Sorting can beis done using merge sort or
radix sort, because these algorithmsy can be performed in place using
$\mathcal{O}(1)$ additional memory. Moreover, since we now know the exact LCP
value for each group, two members in the same group can easily be compared in
constant time: if they have a longest common prefix of length $k$, then the
first position in which they differ is $k+1$, meaning they can be compared by
only comparing their $k+1$-th letters. After this, structure $B$ contains the
complete and sorted LCP groups, which are passed on to the second step of the
algorithm.

###  3.2 Constructing the SSA and SLCP array

The second phase (Algorithm 2) of the main algorithm involves traversing the
groups created in the previous step in order to construct the SSA and SLCP
array. At this point, the members of each group are sorted lexicographically,
which means that the SSA can be obtained by a simple pre-order walk along the
hierarchy of the groups. For any two members, their exact longest common
prefix is stored by their lowest common ancestor; that is, group with the
greatest LCP value that both suffixes fall under.

This part of the algorithm is thus a simple depth-first search of the
underlying hierarchy that records all encountered suffixes in SSA in the order
they appear. For every group that is visited, the LCP value of its direct
“parent” is stored with it (Lines 4 and 17). Throughout, a value $\ell$ is
tracked that takes the value of the lowest LCP value that has been seen since
the last suffix was encountered (Lines 8-9); every time a suffix is appended
to SSA, $\ell$ is appended to the SLCP array (Lines 11-12). This completes the
construction.

###  3.3 A Full Working Example

A step-by-step example of the workings of this algorithm is described below.
In this example, we construct the SSA and SLCP arrays on the string
$T=\texttt{abracadabrarabia}$ for the positions $A=(1,3,8,10,11,13)$. $A$
contains the starting indices of the suffixes we wish to process. The
corresponding suffixes are, in order of their starting positions in $T$,
abracadabrarabia, racadabrarabia, abrarabia, rarabia, arabia and abia.

We start with a singular group containing all indices and having a shared
prefix of length zero (see Table 1). For decreasing powers of 2 starting with
$2^{\lfloor\log n\rfloor}$, groups are refined in order to have more and more
precise LCP values. For every new group that we create, we take the index
corresponding to one of its members and add it to the array $A$, so that we
can easily find the shared prefix corresponding to that group.

In the actual algorithm, the prefixes are efficiently grouped by taking their
KR fingerprints as per Lemma 1 and indexed in a hash table. For the sake of
the example, each relevant prefix is listed instead of its KR fingerprint. The
members of each group are sorted lexicographically using merge sort or radix
sort. At this point, the groups are refined to the point where they define the
exact longest common prefix between their members, so sorting them is done by
looking at just the letter succeeding their longest common prefix.

$T=\texttt{abracadabrarabia}$ $A=(1,3,8,10,11,13)$
---
Initial group: $(7,0,(1,2,3,4,5,6))$
$2^{j}=16,8$ | None of the suffixes share a prefix of length $16$ or $8$, so no refinement is possible.
$2^{j}=4$ | Consider the prefixes of length $4$ of every suffix:
1: abra
2: raca
3: abra
4: rara
5: arab
6: abia
Combine the members 1 and 3 into a new group with id $8$ and LCP value 4:
$\\{(7,0,(2,4,5,6,\textbf{8})),(8,4,(\textbf{1, 3}))\\}$
$2^{j}=2$ | Extend the prefixes by 2 and re-group:
2: ra | 1: (abra)ca
4: ra | 3: (abra)ra
5: ar |
6: ab |
8: ab |
New groups:
$\\{(7,0,(5,\textbf{9},\textbf{10})),(8,4,(1,3)),(9,2,(\textbf{2,
4})),(10,2,(\textbf{6, 8}))\\}$
$2^{j}=1$ | Extend the prefixes of every suffix by 1 and regroup:
5: a | 1: (abra)c | 2: (ra)c | 6: (ab)i
9: r | 3: (abra)r | 4: (ra)r | 8: (ab)r
10: a |  |  |  |
New groups:
$\\{(7,0,(9,\textbf{11})),(8,4,(1,3)),(9,2,(2,4)),(10,2,(6,8)),(11,1,(\textbf{5,
10}))\\}$
Sorting | Sort every group based on the letter appearing directly after the prefix of each member:
9: r | 1: (abra)c | 2: (ra)c | 6: (ab)i | 5: (a)r
11: a | 3: (abra)r | 4: (ra)r | 8: (ab)r | 10: (a)b
Final groups:
$\\{(7,0,(\textbf{11,
9})),(8,4,(1,3)),(9,2,(2,4)),(10,2,(6,8)),(11,1,(\textbf{10, 5}))\\}$
Table 1: Computing and sorting the LCP groups.

The second phase of the algorithm is a fairly straightforward DFS on the
groups in order to build the two output arrays (see Table 2). The variable
$\ell$, at every point, takes as value the length of the longest common prefix
stored in the lowest common ancestor between the last discovered suffix, in
the (conceptual) underlying hierarchy that records all encountered suffixes in
SSA in the order they appear, and the currently inspected member. To
facilitate this, every member is stored with its _parent’s_ LCP value in the
search stack.

At every iteration, the top of the stack (represented as the first member) is
popped. If it is a group, its children are pushed onto the stack and $\ell$ is
updated if necessary. If it is a suffix, the element $A[i]$, where $i$ is the
index of the suffix, is added to SSA, and the current value of $\ell$ is added
to SLCP.

| $\ell$ | Stack | SSA | SLCP
---|---|---|---|---
1 | $0$ | $(7,0)$ | $\emptyset$ | $\emptyset$
2 | $0$ | $(11,0),(9,0)$ | $\emptyset$ | $\emptyset$
3 | $0$ | $(10,1),(5,1),(9,0)$ | $\emptyset$ | $\emptyset$
4 | $0$ | $(6,2),(8,2),(5,1),(9,0)$ | $\emptyset$ | $\emptyset$
5 | $2$ | $(8,2),(5,1),(9,0)$ | $(13)$ | $(0)$
6 | $2$ | $(1,4),(3,4),(5,1),(9,0)$ | $(13)$ | $(0)$
7 | $4$ | $(3,4),(5,1),(9,0)$ | $(13,1)$ | $(0,2)$
8 | $1$ | $(5,1),(9,0)$ | $(13,1,8)$ | $(0,2,4)$
9 | $0$ | $(9,0)$ | $(13,1,8,11)$ | $(0,2,4,1)$
10 | $0$ | $(2,2),(4,2)$ | $(13,1,8,11)$ | $(0,2,4,1)$
11 | $2$ | $(4,2)$ | $(13,1,8,11,3)$ | $(0,2,4,1,0)$
12 | $2$ | $\emptyset$ | $(13,1,8,11,3,10)$ | $(0,2,4,1,0,2)$
Table 2: Constructing the SSA and SLCP array.

Thus the resulting arrays are $\textsf{SSA}=(13,1,8,11,3,10)$ and
$\textsf{SLCP}=(0,2,4,1,0,2)$. Indeed, the corresponding suffixes are abia,
abracadabrarabia, abrarabia, arabia, racadabrarabia and rarabia, which are now
lexicographically sorted. Moreover, between each consecutive pair of suffixes
in SSA, the longest common prefixes correspond to the values in SLCP (the
first value in SLCP is $0$, by definition).

###  3.4 Analysis

We prove the following result (Theorem 1) by analyzing the time (Lemma 2) and
space (Lemma 3) complexity of the Main-Algo. The correctness of the algorithm
follows directly from [15].

######  Theorem 1.

For any string $T\in\Sigma^{n}$, any set $T_{\mathcal{B}}$ of $b$ suffixes of
$T$, and any $s\in[b,n]$, Main-Algo with $j_{\text{start}}$ set to
$\lfloor\log n\rfloor$ computes the SSA and SLCP of $T_{\mathcal{B}}$ in
$\mathcal{O}(n+(bn/s)\log s)$ time using $s+7b+\mathcal{O}(1)$ machine words.
The output is correct with high probability.

######  Lemma 2.

Main-Algo with $j_{\text{start}}$ set to $\lfloor\log n\rfloor$ runs in
$\mathcal{O}(n+(bn/s)\log s)$ time.

###### Proof.

The first phase of the algorithm consists of $\mathcal{O}(\log n)$ iterations
and a sorting step. During every iteration, each existing group is considered
and every member within the group is hashed. After being hashed, it is either
re-added to the same group or put into a new group. The total number of groups
is at most $b-1$, as the group structure represents a conceptual tree
(hierarchy) with $b$ leaves in which all internal nodes have at least two
children. The number of members in each group is at most $b$. However, by
amortization, it can be seen that every member (that is, every suffix and
every group other than the “root”) is processed precisely once during every
iteration. Thus, we have $2b-2=\mathcal{O}(b)$ members in total.

For every group member, a KR fingerprint is computed. After the one-time pre-
processing of $T$ in $\mathcal{O}(n)$ time, the KR fingerprint of a length-$k$
substring can be computed in $\mathcal{O}(\min\\{k,n/s\\})$ time (Lemma 1). In
the first $\log s$ iterations, the cost is $\mathcal{O}(n/s)$, so the total
cost of these iterations is $\mathcal{O}((bn/s)\log s)$. After $\log s$
iterations, the length $k$ of the substring whose KR fingerprint is computed
is $k<n/2^{\log s}=n/s$ and so the total cost of all remaining iterations is
$bn/s+bn/(2s)+bn/(4s)+\cdots+b=\mathcal{O}(bn/s)$. Thus the total cost of
computing all KR fingerprints is $\mathcal{O}(n+(bn/s)\log s)$.

Every group member has its KR fingerprint taken and added to a hash table
supporting constant worst-case operations with high probability [1].
Afterwards, all members from the hash table are re-added to the groups; for
every KR fingerprint collision a new group is created with its respective
members, and all other members are re-added to the original group. The number
of newly created groups is at most half the number of members in the original
group, as every new group has to contain at least two members. So other than
the fingerprinting, all operations for a single member are performed in
constant time with high probability, meaning that the total time for every
iteration is $\mathcal{O}(b\log n)=\mathcal{O}((bn/s)\log s)$.555If this is
not the case, we output incorrect arrays deliberately to ensure that our
algorithm is Monte Carlo.

In the sorting step, we have two cases: (a) $b<n/\log n$ and (b) $b\geq n/\log
n$. The members in each group are sorted using in-place merge sort [25, 20]
(Case (a)) or in-place radix sort [12] (Case (b)) in $\mathcal{O}(n)$ time.

Case (a): $b<n/\log n$.

Sorting $k$ members with merge sort takes $\mathcal{O}(k\log k)$ time. Recall
that there are at most $b-1$ groups and that the total number of members over
all groups is at most $2b-2=\mathcal{O}(b)$. If the number of members to be
sorted in group $i$ is $k_{i}$, $k_{1}+\dots+k_{b-1}=\mathcal{O}(b)$ so the
time needed to sort all groups is $\mathcal{O}(k_{1}\log
k_{1}+\dots+k_{b-1}\log k_{b-1})=\mathcal{O}((k_{1}+\dots+k_{b-1})\log
b)=\mathcal{O}(b\log b)=\mathcal{O}(n)$.

Case (b): $b\geq n/\log n$.

We employ the algorithm by Franceschini et al. [12], which given an array $A$
of $k$ $\mathcal{O}(\log k)$-bit integers, sorts $A$ in place in
$\mathcal{O}(k)$ time. In our case sorting $2b-2$ members in total, takes
$\mathcal{O}(b)=\mathcal{O}(n)$ time, because every letter is a
$\log\sigma=\mathcal{O}(\log n)=\mathcal{O}(\log b)$-bit integer, where
$\sigma=|\Sigma|$.

The second phase of the algorithm is a simple stack-based DFS. Each of the
$\mathcal{O}(b)$ members is pushed to and popped from the stack precisely
once. The further operations applied to each member all take constant time, so
this step takes $\mathcal{O}(b)$ time.

Adding all this together gives
$\mathcal{O}(n)+\mathcal{O}(bn/s)\cdot\mathcal{O}(\log
s)+\mathcal{O}(n)+\mathcal{O}(b)=\mathcal{O}(n+(bn/s)\log s)$ time. ∎

Like the algorithm by I et al. [15], Main-Algo can be amended to work in
$\mathcal{O}(n)$ time, when $s=b\log b$.

######  Lemma 3.

Main-Algo can be implemented using $s+7b+\mathcal{O}(1)$ machine words,
excluding the read-only string $T$, the array $A$ representing the set of $b$
suffixes, and the write-only output arrays SSA and SLCP.

###### Proof.

We analyze the peak space used by the algorithm neglecting the use of
$\mathcal{O}(1)$ machine words:

  * •

KR fingerprints: Pre-processing $T$ to compute KR fingerprints takes $s$
integers by Lemma 1.

  * •

Array $A$: Array $A$ starts with $b$ integers as input, but at most $b-1$ more
integers are appended to it during the algorithm to store witness suffixes for
new groups, so it stores at most $b-1$ new integers. (Even if $A$ is read-only
we can simulate the append operation by using an extraother array.)

  * •

List $B$: We implement list $B$ using three arrays: $K$ of size $b-1$; $C$ of
size $b-1$; and $L$ of size $2b-2$. $K[i]$ stores the LCP value for the group
with id $i+b$; and $L[C[i-1]+1],\ldots,L[C[i]]$ are the group’s member
id’s.666If $i=1$ then the group member id’s are $L[1],\ldots,L[C[i]]$. There
are at most $b-1$ groups; for every group one integer is stored in $K$ and $C$
as well as the group member id’s in $L$. The total number of group members is
at most $2b-2$, since all groups except the “root” group are a member. Thus
list $B$ can be implemented using $4b-4$ integers.

  * •

Hash table $H_{i}$: While processing group $i+b$, every group member is
(removed from the group and) added to a hash table $H_{i}$ as satellite value
of the corresponding KR fingerprint key. We use a space-efficient hash table
storing $c_{i}=C[i]-C[i-1]$ integers (KR fingerprints) as keys: By using [1],
we implement $H_{i}$ using $(1+\epsilon)c_{i}$ machine words, for any
$0<\epsilon<1$. We need at most $b$ integers to maintain the size of the
satellite values per KR fingerprint because every group can have at most $b$
members. By choosing $\epsilon=1/c_{i}$ we need at most $2b+\mathcal{O}(1)$
machine words in total to maintain the hash table.

We can delete the fingerprint data structure and the hash table before moving
to the sorting phase. Sorting does not use any additional space because merge
sort and radix sort can be implemented in-place [25, 20, 12], thus using only
$\mathcal{O}(1)$ additional machine words. The first step of the algorithm
uses at most $s+7b+\mathcal{O}(1)$ machine words but at the end of it we have
$5b+\mathcal{O}(1)$ machine words stored: array $A$ and list $B$.

We now analyze the space used by Algorithm 2; in particular, the space taken
by the search stack and the output arrays. The stack stores at most every
group and every suffix. However, the stack never simultaneously stores a
member and one of its ancestors, meaning the maximum size of the stack at any
point is at most the maximum width of the sparse suffix tree, which is $b$.
Every element in the stack consists of two integers, so the stack takes up at
most $2b$ machine words. No other machine words need to be stored as the
maximum stack size $b$ is known in advance and so the stack is implemented
using an array.

Adding this together gives at most $s+7b+\mathcal{O}(1)$ machine words in
total needed for the algorithm. ∎

##  4 A Simple Parameterized Algorithm

In real-world datasets, the $b$ suffixes in $T_{\mathcal{B}}$ will generally
not share very long prefixes. Even when they do, it is highly unlikely that
all of them have this property. While Main-Algo is theoretically efficient, it
would waste a lot of time with such datasets by considering large overlaps
between suffixes when in reality the longest common prefixes are much shorter
or when only very few suffixes share very long prefixes. Below, we show a
simple method to take advantage of this, by only considering short common
prefixes in the beginning and then extending them _only_ for the suffixes that
happen to share longer prefixes. By considering an extra parameter
$b^{\prime}$ indicating the number of suffixes that share longest common
prefixes longer than a certain threshold, we arrive at a time and space
complexity that appears favorable for such real-world datasets.

#### Main Idea.

We design an algorithm for constructing SSA and SLCP which is parameterized by
the total number $b^{\prime}\leq b$ of suffixes which have an LCP value of at
least $\ell=2^{\lfloor\log\frac{n}{b}\rfloor+1}-1$ with some other suffix. We
show that partitioning the $b$ suffixes into two classes (one with suffixes
with LCP value strictly less than $\ell$; and another with suffixes with LCP
value greater than or equal to $\ell$) can be done in $\mathcal{O}(n)$ time.
In particular, we show that it suffices to invoke Theorem 1 twice: once (with
a small change) for the $b$ suffixes; and once (as is) for the $b^{\prime}$
suffixes; and then merge the partial results in $\mathcal{O}(b)$ time to
obtain the final SSA and SLCP.

#### Description and Pseudocode.

The pseudocode for the algorithm is given as Parameterized-Algo (Algorithm
3).777The pseudocode is complete in the sense that it only assumes the
implementation of Main-Algo. A line-by-line explanation of the algorithm
follows.

Parameterized-Algo invokes the original algorithm Main-Algo twice with
different arguments. In Line 1, it calls Main-Algo with the full array $A$ as
argument (and $s=b$). We set the parameter $j_{\text{start}}$ that indicates
the starting value of $j$ (Line 5 of Algorithm 1) to
$\lfloor\log\frac{n}{b}\rfloor$, meaning that $j$ starts at a lower value than
the value $\lfloor\log n\rfloor$ used in the Main-Algo and so it will take
less time to complete. The result of this is that SSA will only be sorted up
to $\ell=2^{\lfloor\log\frac{n}{b}\rfloor+1}-1$ positions. This means that for
every consecutive pair of suffixes in SSA, if their LCP value is less than
$\ell$, they will already be sorted correctly, whereas the other suffixes,
with associated LCP values of $\ell$, will need to be further sorted in a
second phase (Lines 8 to 13).

What remains is to identify the suffixes that need to be further sorted, sort
these suffixes separately from the others, and re-insert them into the output
arrays along with the corrected LCP values. We use two arrays $A^{\prime}$ and
$P$: $A^{\prime}$ contains the suffixes; and $P$ tracks the positions in SSA
that these suffixes are taken from, to ensure that they will later be re-
inserted at the correct positions. In Line 5, we ensure that the right
suffixes are tracked in these arrays, namely those that have an LCP value of
$\ell$ with their predecessor or successor suffix. If any such suffixes are
found, we invoke Main-Algo again (Line 9), but with just these suffixes (those
in array $A^{\prime}$) as input, and with the default value of
$j_{\text{start}}=\lfloor\log n\rfloor$. This means that the suffixes of
$A^{\prime}$ will now be fully sorted rather than being sorted up to $\ell$
positions. Then, in Lines 10 and 11, we insert these re-sorted suffixes at the
same positions that they were taken from before, but in the corrected order.
In Lines 12 and 13, we also copy the associated LCP values, but only at the
positions in-between two re-sorted suffixes, as all other LCP values were
already correct.

We next state and prove Theorem 2.

Algorithm 3 Parameterized-Algo

Input: string $T\in\Sigma^{n}$, integer $b$, and array $A$ of $b$ distinct
integers from $[n]$
Output: SSA and SLCP

1:$\textsf{SSA},\textsf{SLCP}\leftarrow\textsc{Main-
Algo}(T,A,b,j_{\text{start}}=\lfloor\log\frac{n}{b}\rfloor)$ $\triangleright$
Quasi-sort the $b$ suffixes

2:$\ell\leftarrow 2^{\lfloor\log\frac{n}{b}\rfloor+1}-1$

3:$P,A^{\prime}\leftarrow\text{empty arrays}$

4:for $i=1,\ldots,b$ do $\triangleright$ Check which of the $b$ suffixes need
further sorting

5: if $\textsf{SLCP}[i]=\ell\lor(i<b\land\textsf{SLCP}[i+1]=\ell)$ then
$\triangleright$ Suffix $T[\textsf{SSA}[i]\mathinner{.\,.}n]$ needs further
sorting

6: $P.\text{append}(i)$

7: $A^{\prime}.\text{append}(\textsf{SSA}[i])$

8:if $|A^{\prime}|>0$ then

9: $\textsf{SSA}^{\prime},\textsf{SLCP}^{\prime}\leftarrow\textsc{Main-
Algo}(T,A^{\prime},|A^{\prime}|,j_{\text{start}}=\lfloor\log n\rfloor)$
$\triangleright$ Sort $|A^{\prime}|$ out of $b$ suffixes

10: for $i=1,\ldots,|A^{\prime}|$ do $\triangleright$ Merge the partial arrays

11: $\textsf{SSA}[P[i]]\leftarrow\textsf{SSA}^{\prime}[i]$

12: if $\textsf{SLCP}[P[i]]=\ell$ then $\triangleright$ Only copy the SLCP
value if the suffix at $P[i]-1$ was also re-sorted

13: $\textsf{SLCP}[P[i]]\leftarrow\textsf{SLCP}^{\prime}[i]$

14:return SSA and SLCP

######  Theorem 2.

For any string $T\in\Sigma^{n}$ and any set $T_{\mathcal{B}}$ of $b$ suffixes
of $T$, Parameterized-Algo computes the SSA and SLCP of $T_{\mathcal{B}}$ in
$\mathcal{O}(n+(b^{\prime}n/b)\log b)$ time using
$8b+4b^{\prime}+\mathcal{O}(1)$ machine words, where $b^{\prime}$ is the total
number of $i$ such that $\textsf{SSA}[i]\in\mathcal{B}$ and
$\textsf{SLCP}[i]\geq\ell$ or $\textsf{SLCP}[i+1]\geq\ell$, with
$\ell=2^{\lfloor\log\frac{n}{b}\rfloor+1}-1$. The output is correct with high
probability. When $b^{\prime}=\mathcal{O}(b/\log b)$, Parameterized-Algo runs
in $\mathcal{O}(n)$ time using $8b+o(b)$ machine words.

#### Time Complexity.

The first phase of the algorithm (Line 1) runs in
$\mathcal{O}(\log\frac{n}{b})$ iterations. The longest prefixes whose KR
fingerprints are computed have length $\mathcal{O}(\frac{n}{b})$, and there
are $\mathcal{O}(b)$ KR fingerprints computed in each iteration. This means
that computing the KR fingerprints during the first phase takes
$\mathcal{O}(b)\cdot(\mathcal{O}(\frac{n}{b})+\mathcal{O}(\frac{n}{2b})+\mathcal{O}(\frac{n}{4b})+\ldots)=\mathcal{O}(n)$
time. Hashing the fingerprints takes
$\mathcal{O}(b\log\frac{n}{b})=\mathcal{O}(n)$ worst-case time with high
probability. (Grouping the fingerprints via distribute-and-collect, like the
algorithm by I et al. [15], would incur a multiplicative factor of
$\log_{s}n$.) Sorting takes $\mathcal{O}(n)$ time (see Lemma 2). Therefore the
entire first phase runs in $\mathcal{O}(n)$ time. The second phase (Lines 8 to
13) computes KR fingerprints of longer prefixes as well and otherwise runs the
same as Main-Algo, with the exception that only $b^{\prime}$ suffixes are now
sorted. By Lemma 2, for $s=b$, this takes $\mathcal{O}(n+(b^{\prime}n/b)\log
b)$ time. All other operations run in single loops over arrays of size $b$ or
$b^{\prime}$ with constant-time operations, and thus take $\mathcal{O}(b)$
time. Adding everything together gives $\mathcal{O}(n+(b^{\prime}n/b)\log b)$
time. When $b^{\prime}=\mathcal{O}(b/\log b)$, the running time becomes
$\mathcal{O}(n)$.

#### Space Complexity.

The first phase of the algorithm uses $s+7b+\mathcal{O}(1)$ machine words as
per Lemma 3. The additional arrays $P$, $A^{\prime}$, $\textsf{SSA}^{\prime}$
and $\textsf{SLCP}^{\prime}$ use $4b^{\prime}$ machine words in total. The
second invocation of Main-Algo uses $s+7b^{\prime}+\mathcal{O}(1)$ machine
words as per Lemma 3. By setting $s=b$, the algorithm uses
$8b+4b^{\prime}+\mathcal{O}(1)$ machine words in total. If
$b^{\prime}=\mathcal{O}(b/\log b)$, the algorithm uses $8b+o(b)$ machine
words.

#### Correctness.

The correctness of SSA is proved by Lemma 6 and that of SLCP is proved by
Lemma 7. To prove these lemmas, we first show the auxiliary Lemmas 4 and 5.

######  Lemma 4.

Let $\textsf{SSA}_{1}$ be the instance of SSA after the first invocation of
Main-Algo (Line 1). The strings $T[\textsf{SSA}_{1}[i]\mathinner{.\,.}n]$,
$i\in[1,b]$, are sorted up to their prefix of length
$\ell=2^{\lfloor\log\frac{n}{b}\rfloor+1}-1$.

###### Proof.

In Main-Algo, all LCP values can be increased by powers of two in each
iteration. With the starting value
$j_{\text{start}}=\lfloor\log\frac{n}{b}\rfloor$, this adds up to a maximum
LCP value of $\ell$ in any group. At any point during Main-Algo, two suffixes
that are in the same group with LCP value $k$ share a longest common prefix of
at least length $k$. Thus, this invocation of Main-Algo will compute the LCP
values between suffixes correctly if they are at most $\ell$, and all other
LCP values will be $\ell$. The sorting step takes into account only the letter
which appears after the computed (longest) common prefix, so if the LCP
between any two suffixes is less than $\ell$ the suffixes will be sorted
correctly. The statement follows. ∎

######  Lemma 5.

Let $\textsf{SSA}_{1}$ be the instance of SSA after the first invocation of
Main-Algo (Line 1), and let $\textsf{SSA}_{2}$ be the instance of SSA returned
at the end of Parameterized-Algo (Line 14). For every $i\in[1,b]$, either
$\textsf{SSA}_{1}[i]=\textsf{SSA}_{2}[i]$ and $\textsf{SSA}_{1}[i]$ and
$\textsf{SSA}_{2}[i]$ have a longest common prefix of length
$n-\textsf{SSA}_{1}[i]+1$, or $\textsf{SSA}_{1}[i]\neq\textsf{SSA}_{2}[i]$ and
$\textsf{SSA}_{1}[i]$ and $\textsf{SSA}_{2}[i]$ have a longest common prefix
of length at least $\ell$.

###### Proof.

If $\textsf{SSA}_{1}[i]=\textsf{SSA}_{2}[i]$, this is trivial, so we only
concern ourselves with the case $\textsf{SSA}_{1}[i]\neq\textsf{SSA}_{2}[i]$.
In this case, the value was overwritten in Line 11, meaning that the suffix
$\textsf{SSA}_{1}[i]$ was stored in $A^{\prime}$ in Line 7 to be re-sorted in
the second invocation of Main-Algo. The same must hold for
$\textsf{SSA}_{2}[i]$.

Consider the array $A^{\prime}$ as it is built in Lines 4-7. By Lemma 4, the
suffixes of $\textsf{SSA}_{1}$ are sorted up to their length-$\ell$ prefix;
since the entries of $A^{\prime}$ appear in the same order as they appear in
$\textsf{SSA}_{1}$, this must also be the case for $A^{\prime}$. Because the
suffixes of $A^{\prime}$ are already sorted correctly up to their
length-$\ell$ prefix, it must be that for every position $j\in[1,b^{\prime}]$,
$A^{\prime}[j]$ and $\textsf{SSA}^{\prime}[j]$ have the same length-$\ell$
prefix. Now note that if $\textsf{SSA}_{1}[i]$ appears in position $j$ in
$A^{\prime}$, then $\textsf{SSA}_{2}[i]$ will take the value from
$\textsf{SSA}^{\prime}[j]$. Since $A^{\prime}[j]$ and
$\textsf{SSA}^{\prime}[j]$ have a length-$\ell$ common prefix,
$\textsf{SSA}_{1}[i]$ and $\textsf{SSA}_{2}[i]$ must as well. ∎

######  Lemma 6.

$\textsf{SSA}_{2}=\textsf{SSA}$ as returned by Algorithm 3 contains the
suffixes of $A$ sorted lexicographically.

###### Proof.

We prove this by showing that for any two consecutive positions $i$ and $i+1$,
$\textsf{SSA}_{2}[i]$ and $\textsf{SSA}_{2}[i+1]$ appear in the right order.
Let $\textsf{SSA}_{1}$ be the instance of SSA after the first invocation of
Main-Algo.

We already know that $\textsf{SSA}_{1}$ is sorted correctly up to $\ell$
positions. This means that for any $i$, if the longest common prefix of
$\textsf{SSA}_{1}[i]$ and $\textsf{SSA}_{1}[i+1]$ is shorter than $\ell$, they
already appear in the correct order in this array. If neither suffix is
overwritten after the second phase, this is also trivially the case for them
in $\textsf{SSA}_{2}$.

Now suppose that exactly one of the two (wlog $\textsf{SSA}_{1}[i+1]$) is
replaced by some other suffix $s$ while the other remains the same. Let $k$ be
the LCP of $\textsf{SSA}_{1}[i]$ and $\textsf{SSA}_{1}[i+1]$. By Lemma 5,
$\textsf{SSA}_{1}[i+1]$ and $s$ have a longest common prefix of length at
least $\ell$. This is longer than $k$, which is strictly less than $\ell$.
This means that the $(k+1)$-th letter of $s$ is the same as that of
$\textsf{SSA}_{1}[i+1]$, which is the first position in which it differs from
$\textsf{SSA}_{1}[i]$. Thus $\textsf{SSA}_{2}[i]=\textsf{SSA}_{1}[i]$ and
$\textsf{SSA}_{2}[i+1]=s$ are sorted correctly relative to one another.

The remaining case is when $\textsf{SSA}_{1}[i]$ and $\textsf{SSA}_{1}[i+1]$
have a longest common prefix of length $\ell$ or longer. In this case, both
suffixes are added to $A^{\prime}$ to be re-sorted in the second invocation,
and both $\textsf{SSA}_{2}[i]$ and $\textsf{SSA}_{2}[i+1]$ may take the value
of another suffix. The second invocation of the main algorithm sorts all
suffixes in $A^{\prime}$ completely, returning $\textsf{SSA}^{\prime}$. The
suffixes in $\textsf{SSA}^{\prime}$ are then re-inserted into
$\textsf{SSA}_{2}$, in which they will appear in the same order as they did in
$\textsf{SSA}^{\prime}$. Therefore, no matter which suffixes end up at
$\textsf{SSA}_{2}[i]$ and $\textsf{SSA}_{2}[i+1]$, they also appeared
consecutively in $\textsf{SSA}^{\prime}$ and therefore must be sorted
correctly. ∎

######  Lemma 7.

For any two consecutive positions $i$ and $i+1$, $\textsf{SLCP}[i+1]$, as
returned by Algorithm 3, gives the length of the longest common prefix of
$\textsf{SSA}[i]$ and $\textsf{SSA}[i+1]$.

###### Proof.

Let $\textsf{SSA}_{1}$ and $\textsf{SLCP}_{1}$ be the arrays returned by the
first invocation of Main-Algo, and $\textsf{SSA}_{2}$ and $\textsf{SLCP}_{2}$
the arrays produced at the end. By Lemma 4, if $\textsf{SLCP}_{1}[i+1]<\ell$,
this value is correct. Therefore, the only values that need to be overwritten
for $\textsf{SLCP}_{2}$ are when $\textsf{SLCP}_{1}[i+1]=\ell$. The check at
Line 12 ensures this. Of course, when $\textsf{SLCP}_{1}[i+1]=\ell$, then both
$\textsf{SSA}_{1}[i]$ and $\textsf{SSA}_{1}[i+1]$ are added to $A^{\prime}$ in
order to be re-sorted in the second invocation. The values at
$\textsf{SSA}_{2}[i]$ and $\textsf{SSA}_{2}[i+1]$ are then replaced by two
suffixes that appear consecutively in $\textsf{SSA}^{\prime}$, say
$\textsf{SSA}^{\prime}[j]$ and $\textsf{SSA}^{\prime}[j+1]$. By the
correctness of Main-Algo, the LCP value of these two suffixes is given by
$\textsf{SLCP}^{\prime}[j+1]$, which is the value that
$\textsf{SLCP}_{2}[j+1]$ takes. ∎

#### Random Strings.

Finally, we show that Parameterized-Algo can be trivially amended to work in
$\mathcal{O}(n)$ time for any string chosen uniformly at random from
$\Sigma^{n}$.

######  Theorem 3.

For any string $T$ chosen uniformly at random from $\Sigma^{n}$ and any set
$T_{\mathcal{B}}$ of $b$ suffixes of $T$, SSA and SLCP of $T_{\mathcal{B}}$
can be computed in $\mathcal{O}(n)$ time using $\mathcal{O}(b)$ space. The
output is correct with high probability.

###### Proof.

We assume $|\Sigma|\geq 2$, otherwise the problem has a trivial solution.
Bollobás and Letzter [7, Theorem 4] showed that the maximum length of an LCE
on $T$ is at most $2\log_{|\Sigma|}n+\log_{|\Sigma|}\log_{|\Sigma|}n$ with
high probability. We bound this from above by $3\log n$ and amend
Parameterized-Algo as follows:

Case (a): $b\log n<n$.

We invoke Main-Algo by setting $j_{\text{start}}$ to the smallest integer such
that $2^{j_{\text{start}}}\geq 2\lfloor\log n\rfloor$, which gives
$\ell=2\lfloor\log n\rfloor\cdot 2-1=4\lfloor\log n\rfloor-1$. After the
$\mathcal{O}(n)$-time preprocessing of Lemma 1, computing the KR fingerprints
takes $\mathcal{O}(b)\cdot 4(\mathcal{O}(\frac{\log
n}{1})+\mathcal{O}(\frac{\log n}{2})+\mathcal{O}(\frac{\log
n}{4})+\ldots)=\mathcal{O}(b\log n)$ time. Hashing the fingerprints takes
$\mathcal{O}(b)$ time per iteration with high probability, and so
$\mathcal{O}(b\log n)$ total time. Merge sort takes $\mathcal{O}(b\log b)$
time. Since $\ell>3\log n$, all suffixes of $T_{\mathcal{B}}$ will be fully
sorted from the first invocation of Main-Algo. If
$b^{\prime}=\mathcal{O}(b/\log b)$ suffixes are still unsorted after the first
invocation, these will be fully sorted in the second invocation of Main-Algo
in $\mathcal{O}(n)$ time (Theorem 2). If $b^{\prime}=\omega(b/\log b)$, we
output incorrect arrays. The total time complexity is $\mathcal{O}(n+b\log
n)=\mathcal{O}(n)$.

Case (b): $b\log n\geq n$.

We have $\mathcal{O}(s)$ space to sort the $b$ suffixes; we can do it
efficiently using radix sort because it suffices to sort all prefixes of them
of length $\mathcal{O}(\log_{\sigma}n)$ by the Bollobas and Letzter’s result,
where $\sigma=|\Sigma|$ (otherwise, we output incorrect arrays). The $b$
prefixes are each of length at most $c\log_{\sigma}n$, for some
$c=\mathcal{O}(1)$; so radix sort takes $\mathcal{O}((b+s)(c\cdot\log
n/\log\sigma)\cdot(\log\sigma/\log s))$ time, because we have at most $(c\log
n/\log\sigma)$ letters in every prefix, and each time we sort $b$ letters, one
from each prefix, we use $(\log\sigma/\log s)$ rounds of counting sort because
$\sigma$ can be up to $n^{c^{\prime}}$, for some constant
$c^{\prime}=\mathcal{O}(1)$. Conveniently, the $\log\sigma$ terms cancel out.
Then, because we set $s=b$, and by the fact that we are in the case $b\geq
n/\log n$, we have that $\log n/\log s=\mathcal{O}(1)$. The total time
complexity is thus $\mathcal{O}(b+s)=O(b)$.

∎

##  5 Proof-of-Concept Experiments

We have used the following C++ implementations that we make all available at
https://github.com/lorrainea/SSA:

  1. 1.

A simplified implementation produced by Prezza of his algorithm from
[24].888https://github.com/nicolaprezza/rk-lce/blob/master/sa-rk.cpp It first
constructs an LCE data structure in $\mathcal{O}(n)$ time in place: using
exactly the same space as $T$ (plus $\mathcal{O}(1)$ machine words). Since the
structure supports $\mathcal{O}(\log n)$-time LCE queries, the implementation
uses LCE queries and std::sort to construct the SSA. We have amended this
implementation to also compute the SLCP in $\mathcal{O}(b\log n)$ extra time
using the SSA and LCE queries. We denote this implementation by SSA-LCE.

  2. 2.

A simplified implementation by us of Main-Algo. It is simplified in the sense
that for hashing we use the unordered_dense
class.999https://github.com/martinus/unordered_dense Also if the number of KR
fingerprints to be grouped is smaller than a predefined constant (set to 1.5M
by default), then we resort to std::sort to achieve the same goal. For KR
fingerprints, we have used the class by
Kempa.101010https://github.com/dominikkempa/lz77-to-
slp/blob/main/src/karp_rabin_hashing.cpp We denote this implementation by MA.

  3. 3.

An implementation by us of Parameterized-Algo using the above simplified
implementation of Main-Algo. We denote this implementation by PA.

We have used the following two datasets choosing $b\in[n/10^{5},n/10^{3}]$
suffixes uniformly at random:

  1. 1.

A file of $n=11,038,279,710$ bytes ($11.04$ GB), with $|\Sigma|=64$,
containing $689,781$ human DNA reads of total length is $5,455,971,336$, along
with their quality scores.111111https://github.com/nanopore-wgs-
consortium/NA12878/blob/master/nanopore-human-genome/rel_3_4.md (FAF01132) The
reads have been sequenced using an Oxford Nanopore MinION device. We denote
this dataset by FASTQ.

  2. 2.

A file of $n=10,225,926,270$ bytes ($10.23$ GB), with $|\Sigma|=96$,
containing 21,928,568 Amazon reviews (Home and
Kitchen).121212https://cseweb.ucsd.edu/~jmcauley/datasets/amazon_v2/(Home and
Kitchen) We denote this dataset by AMAZON.

(a) Time for varying $n$

(b) Time for varying $b$

(c) Memory for varying $n$

(d) Memory for varying $b$

(e) Time for varying $n$

(f) Time for varying $b$

(g) Memory for varying $n$

(h) Memory for varying $b$

Figure 1: Results for FASTQ (top row) and AMAZON (bottom row). The exact value
of $b^{\prime}$ is on top of the points of the PA curves to highlight the
relevance of Theorem 2. By default, we used $b=0.01\%\cdot n$.

By default, we used $b=0.01\%\cdot n$. The experiments ran on an Intel Xeon
Gold 648 CPU at 2.5GHz with 32GB RAM. All programs were compiled with g++
version 10.2.0 at the -Ofast optimization level.

Figure 1(a) shows that: (i) PA is up to $4$ times faster than SSA-LCE and even
faster than MA; and (ii) the runtime of all implementations scales linearly
with $n$. Figure 1(b) shows that: (i) PA is again many times faster than the
other two implementations; and (ii) PA is not substantially affected (if at
all) by increasing $b$ as opposed to the other two implementations. In
conjunction, the results of Figures 1(a) and 1(b), show that PA runs in linear
time on these instances (see Theorem 2). Figure 1(c) shows that: (i) PA and MA
consume up to $54\%$ less memory compared to SSA-LCE; and (ii) the peak memory
usage for all implementations scales linearly with $n$. Figure 1(d) shows
that: (i) PA and MA are many times more space-efficient than SSA-LCE; and (ii)
PA and MA start off with the space required by the input and increase the peak
memory usage linearly with $b$. The former is explained by the fact that SSA-
LCE is a simplified implementation of the algorithm in [24] (no other
implementation is available), which uses more than $\mathcal{O}(1)$ words of
space to sort the considered suffixes. The results in Figures 1(e)-1(h) for
AMAZON are analogous.

The benefits of PA are explained by the fact that the value of $b^{\prime}$ is
smaller than the one of $b$ by orders of magnitude and even zero in most
cases, which fully justifies the design goals of PA.

## Acknowledgments

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] Yuriy Arbitman, Moni Naor, and Gil Segev.  Backyard cuckoo hashing: Constant worst-case operations with a succinct representation.  In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 787–796. IEEE Computer Society, 2010.
  * [2] 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.
  * [3] 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.
  * [4] Giulia Bernardini, Gabriele Fici, Pawel Gawrychowski, and Solon P. Pissis.  Substring complexity in sublinear space.  CoRR, abs/2007.08357, 2020.
  * [5] Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, and Hjalte Wedel Vildhøj.  Sparse text indexing in small space.  ACM Trans. Algorithms, 12(3):39:1–39:19, 2016.
  * [6] 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.
  * [7] Béla Bollobás and Shoham Letzter.  Longest common extension.  Eur. J. Comb., 68:242–248, 2018.
  * [8] Timothy M. Chan, J. Ian Munro, and Venkatesh Raman.  Selection and sorting in the ”restore” model.  ACM Trans. Algorithms, 14(2):11:1–11:18, 2018.
  * [9] Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza.  Optimal-time dictionary-compressed indexes.  ACM Trans. Algorithms, 17(1):8:1–8:39, 2021.
  * [10] 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.
  * [11] Johannes Fischer, Tomohiro I, and Dominik Köppl.  Deterministic sparse suffix sorting in the restore model.  ACM Trans. Algorithms, 16(4):50:1–50:53, 2020.
  * [12] Gianni Franceschini, S. Muthukrishnan, and Mihai Puatracscu.  Radix sorting with no extra space.  In Lars Arge, Michael Hoffmann, and Emo Welzl, editors, Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, volume 4698 of Lecture Notes in Computer Science, pages 194–205. Springer, 2007.
  * [13] 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.
  * [14] Szymon Grabowski and Marcin Raniszewski.  Sampled suffix array with minimizers.  Softw. Pract. Exp., 47(11):1755–1771, 2017.
  * [15] 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.
  * [16] Juha Kärkkäinen, Peter Sanders, and Stefan Burkhardt.  Linear work suffix array construction.  J. ACM, 53(6):918–936, 2006.
  * [17] Juha Kärkkäinen and Esko Ukkonen.  Sparse suffix trees.  In Jin-yi Cai and C. K. Wong, editors, Computing and Combinatorics, Second Annual International Conference, COCOON ’96, Hong Kong, June 17-19, 1996, Proceedings, volume 1090 of Lecture Notes in Computer Science, pages 219–230. Springer, 1996.
  * [18] Richard M. Karp and Michael O. Rabin.  Efficient randomized pattern-matching algorithms.  IBM J. Res. Dev., 31(2):249–260, 1987.
  * [19] 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.
  * [20] Jyrki Katajainen, Tomi Pasanen, and Jukka Teuhola.  Practical in-place mergesort.  Nord. J. Comput., 3(1):27–40, 1996.
  * [21] Grigorios Loukides and Solon P. Pissis.  Bidirectional string anchors: A new string sampling mechanism.  In 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, pages 64:1–64:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [22] Gonzalo Navarro and Nicola Prezza.  Universal compressed text indexing.  Theor. Comput. Sci., 762:41–50, 2019.
  * [23] Robert Paige and Robert Endre Tarjan.  Three partition refinement algorithms.  SIAM J. Comput., 16(6):973–989, 1987.
  * [24] Nicola Prezza.  Optimal substring equality queries with applications to sparse text indexing.  ACM Trans. Algorithms, 17(1):7:1–7:23, 2021.
  * [25] Jeffrey S. Salowe and William L. Steiger.  Simplified stable merging tasks.  J. Algorithms, 8(4):557–571, 1987.