A taxonomy of suffix array construction algorithms

347 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Parallel Lightweight Wavelet Tree, Suffix Array and FM-Index Construction (2016, methodology): “However the fastest and most space-efficient sequential SA algorithms use induced copying [27], so our goal here is to parallelize such an algorithm.”
Adaptive seeds tame genomic sequence comparison. (2011, background): “There has been much research on efficient algorithms to construct ordinary suffix arrays (Puglisi et al. 2007).”
Compressed full-text indexes (2007, background): “There is also some recent work on efficient construction of (plain) suffix arrays (see [Puglisi et al. 2006] for a good survey).”
A four-stage algorithm for updating a Burrows-Wheeler transform (2009, background): “Its construction is based on the construction of the suffix array, usually performed in O(n)-time [9].”
Succinct nearest neighbor search (2011, methodology): “Secondly, the database is lexicographically sorted, using a linear sort for the first levels and a threeway quick sort for deeper levels, similarly to practical suffix array sorting algorithms [19].”
The Algorithm Design Manual (2020, methodology): “See [PST07] for a recent survey covering all these developments.”