Simple Linear Work Suffix Array Construction

By Juha Kärkkäinen, Peter Sanders. 2003

481 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Hardware and Architecture, Molecular Biology, Algorithms & Complexity

How researchers see this paper

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

In Artificial Intelligence

In Hardware and Architecture

In Molecular Biology

In Algorithms & Complexity

Citations in the corpus

Deduplicating Training Data Makes Language Models Better (2021, background): “…sufﬁx array (Manber and Myers, 1993) is a representation of a sufﬁx tree (Weiner, 1973) that can be constructed in linear time in (cid:107)S(cid:107) (Kärkkäinen and Sanders, 2003) and enables efﬁcient computation of many substring queries; in particular, they allow us to identify duplicated…”
Gepard: a rapid and sensitive tool for creating dotplots on genome scale (2007, methodology): “Gepard uses the Skew algorithm for suffix array calculation (Kärkkäinen and Sanders, 2003).”
Parallel Lightweight Wavelet Tree, Suffix Array and FM-Index Construction (2016, methodology): “While prefix doubling [17] and recursive algorithms [13] have been parallelized in the past, the sequential algorithms that are the fastest and most memory-efficient in practice all use induced copying.”
Compressed full-text indexes (2007, methodology): “There are several more sophisticated algorithms, from the original O(n log n) time [Manber and Myers 1993] to the latest O(n) time algorithms [Kim et al. 2005; Ko and Aluru 2005; Kärkkäinen and Sanders 2003].”
Linear work suffix array construction (2006, background): “Independently and simultaneously to our result, which originally appeared in [36], two different linear-time algorithms were introduced by Kim et al.”
Replacing suffix trees with enhanced suffix arrays (2004, background): “Very recently, it was shown independently and contemporaneously in [19,21,23] that a direct linear time construction of the suffix array is possible.”
A taxonomy of suffix array construction algorithms (2007, methodology): “There are three main algorithms in this class: KA [Ko and Aluru 2003], KS [Kärkkäinen and Sanders 2003] and KJP [Kim et al.”