Suffix arrays: a new method for on-line string searches

By U. Manber, Eugene W. Myers. 1993

Subfields: Information Retrieval & Search

How researchers see this paper

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

In Information Retrieval & Search

Citations in the corpus

Deduplicating Training Data Makes Language Models Better (2021, methodology): “A suffix array (Manber and Myers, 1993) is a representation of a suffix tree (Weiner, 1973) that can be constructed in linear time in ‖S‖ (Kärkkäinen and Sanders, 2003) and enables efficient computation of many substring queries; in particular, they allow us to identify duplicated training examples ”
The RefinedWeb Dataset for Falcon LLM: Outperforming Curated Corpora with Web Data, and Web Data Only (2023, methodology): “For exact duplicates, it is common to match exact substrings of a minimum length using suffix arrays (Manber & Myers, 1993).”
The BigScience ROOTS Corpus: A 1.6TB Composite Multilingual Dataset (2023, methodology): “Instead, we applied substring deduplication (Lee et al., 2022) based on Suffix Array (Manber and Myers, 1993) as a complementary method that clusters documents sharing a long substring, for documents with more than 6000 characters.”
OMA orthology in 2021: website overhaul, conserved isoforms, ancestral gene order and more (2020, methodology): “This method relies on a k-mer index, which is built from a suffix array––a sorted array of all suffixes of a particular string (32).”
Adaptive seeds tame genomic sequence comparison. (2011, positive): “T , sorted according to the alphabetical order of the suffixes starting at each position (Table 1, left column; Manber and Myers 1993).”
Non-commercial Research and Educational Use including without Limitation Use in Instruction at Your Institution, Sending It to Specific Colleagues That You Know, and Providing a Copy to Your Institution's Administrator. All Other Uses, Reproduction and Distribution, including without Limitation Comm (2005, unknown): “[18,19] the fitness function F fg has been defined as: F fg ¼ ðf ; gÞ kf kkgk”
High-order entropy-compressed text indexes (2003, methodology): “We first perform a search of P in SA`+lg t(n), which is stored explicitly along with LCP `+lg t(n), the longest common prefix information required in [10].”
A survey of sequence alignment algorithms for next-generation sequencing (2010, unknown): “vented byManber and Myers [43].”
Indexing Compressed Text (2003, methodology): “Suffix Arrays [40, 31]: Manber and Myers and Gonnet et al.”
MathPile: A Billion-Token-Scale Pretraining Corpus for Math (2023, unknown): “Despite finding many near-duplicates in ProofWiki, they were differentiated as unique lemmas, proofs, or definitions, leading us to retain these entries (cf. Note that we also experimented with using suffix arrays [43] to eliminate exact match sequences within documents.”
Compressed Suffix Trees with Full Functionality (2007, background): “Suffix links are shown in dotted line. called a prefix of T .”
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. 2005a; Ko and Aluru 2005; K¨ainen and Sanders arkk¨2003].”
Clustered Sequence Representation for Fast Homology Search (2007, unknown): “Malde et al. (2003) and Gracy and Argos (1998) investigated the use of sufﬁx structures such as sufﬁx trees (Gusﬁeld, 1997) and sufﬁx arrays (Manber and Myers, 1993) to identify groupings of similar sequences in linear time.”