Linear Suffix Array Construction by Almost Pure Induced-Sorting
By Ge Nong, Sen Zhang, Wai Hong Chan. 2009
172 citations recorded by the source corpus.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Model Architectures, 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
- Daphne Ippolito
- Katherine Lee
- Luke S. Zettlemoyer
- Nicholas Carlini
- Mohit Bansal
- Chiyuan Zhang
- Percy Liang
- Colin Raffel
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Trevor Darrell
- Bernt Schiele
- Xiaogang Wang
- Yi Yang
- Ming-Hsuan Yang
- Alan L. Yuille
In Model Architectures
- Chiyuan Zhang
- Chris Callison-Burch
- Taku Kudo
- Douglas Eck
- Nicholas Carlini
- Katherine Lee
- Daphne Ippolito
In Algorithms & Complexity
- Chiyuan Zhang
- Guy E. Blelloch
- Chris Callison-Burch
- Taku Kudo
- Julian Shun
- Andrew Nystrom
- Douglas Eck
- Nicholas Carlini
Citations in the corpus
- Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (2018, methodology): “Frequent substrings can be enumerated in O ( T ) time and O (20 T ) space with the Enhanced Suffix Array algorithm (Nong et al., 2009), where T is the size of the corpus.”
- Deduplicating Training Data Makes Language Models Better (2021, methodology): “As a building block, we make black-box use of the SA-IS algorithm for constructing a suffix array in linear time Nong et al. (2009); Ko and Aluru (2003).”
- Parallel Lightweight Wavelet Tree, Suffix Array and FM-Index Construction (2016, background): “SA-IS is a lightweight linear-work algorithm and one of the fastest in practice.”