Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
By Roberto Grossi, Jeffrey Scott Vitter. Symposium on the Theory of Computing, 2000
693 citations recorded by the source corpus.
Subfields: Artificial Intelligence, Hardware and Architecture, Molecular Biology
View Paper: https://www.semanticscholar.org/paper/cceb84298feb1e81bab4d43b9e2c2e57a3b05ea4
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
- Meng He
- Kunihiko Sadakane
- Paolo Ferragina
- William F. Smyth
- Andrew Turpin
- Simon J. Puglisi
- Giovanni Manzini
- Roberto Grossi
In Hardware and Architecture
- Kunihiko Sadakane
- Meng He
- William F. Smyth
- Andrew Turpin
- Simon J. Puglisi
- Peter Sanders
- Juha Kärkkäinen
- Paolo Ferragina
In Molecular Biology
- Kunihiko Sadakane
- Meng He
- William F. Smyth
- Andrew Turpin
- Simon J. Puglisi
- Giovanni Manzini
- Paolo Ferragina
- Jeffrey Scott Vitter
Citations in the corpus
- Opportunistic data structures with applications (2000, methodology): “The removal of the sublogarithmic term in the query bound is yet an open problem even in the uncompressed setting [11].”
- Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications (2001, methodology): “Recently, Sadakane proposed a compressed text database system [20] based on the compressed suffix array [10].”
- Compressed Suffix Trees with Full Functionality (2007, background): “Lemma 1 [12] Given s integers in sorted order, each containing w bits, where s < 2, we can store them in at most s(2 + w − lg s ) + O(s/ lg lg s) bits, so that retrieving the h-th integer takes constant time.”
- Replacing suffix trees with enhanced suffix arrays (2004, background): “Under a different name, the function link appeared already in [14].”
- A taxonomy of suffix array construction algorithms (2007, methodology): “For example, algorithms and techniques such as those discussed in [Grossi and Vitter 2005; Mäkinen and Navarro 2006] and references therein are not covered.”
- Succinct Representation of Balanced Parentheses and Static Trees (2002, background): “The time and space bound for the suffix tree operations are further improved by Grossi and Vitter [9].”
- High-order entropy-compressed text indexes (2003, methodology): “Building the above data structures is simply a variation of what was done in [6]; thus it takes O(n lg |Σ|) time to compress (as given in Definition 2.”
- Linear work suffix array construction (2006, background): “An even more space-efficient approach is to construct compressed indexes [21, 27, 42, 31, 32].”
- Indexing Compressed Text (2003, background): “Compressed Suffix Arrays [32]: The compressed suffix array structure also”