Everything about Compressed suffix array

🧭 Start here: a 6-step reading path

1. Read the overview: Compressed suffix arrayA 5-minute orientation
2. Skim a recent paper: An OTA Upgrade Differential Compression Algorithm Based on Suffix Array Induced Sorting and BsDiff MethodsInfluential work since 2022
3. Pick up a classic book: Fundamentals of data structures in CThe most-reprinted book on the subject
4. Read the landmark paper: Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String MatchingCited 286 times
5. Go sideways: Wavelet TreeA closely related topic
6. Go sideways: Compressed data structureA closely related topic

🏆 Landmark papers (most cited)

• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching

  Roberto Grossi, Jeffrey Scott Vitter · 2005 · SIAM Journal on Computing · 286 citations

• New text indexing functionalities of the compressed suffix arrays

  Kunihiko Sadakane · 2003 · Journal of Algorithms · 175 citations

• A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays

  Wing-Kai Hon, Tak-Wah Lam, Kunihiko Sadakane · 2007 · Algorithmica · 51 citations

• Approximate string matching using compressed suffix arrays

  Trinh N.D. Huynh, Wing-Kai Hon, Tak-Wah Lam · 2006 · Theoretical Computer Science · 29 citations

• Time-space trade-offs for compressed suffix arrays

  S.Srinivasa Rao · 2002 · Information Processing Letters · 15 citations

• Locally Compressed Suffix Arrays

  Rodrigo González, Gonzalo Navarro, Héctor Ferrada · 2015 · ACM Journal of Experimental Algorithmics · 10 citations

• Smaller Compressed Suffix Arrays†

  Ekaterina Benza, Shmuel T Klein, Dana Shapira · 2020 · The Computer Journal · 8 citations

• A quick tour on suffix arrays and compressed suffix arrays

  Roberto Grossi · 2011 · Theoretical Computer Science · 7 citations

🆕 Influential since 2022

• An OTA Upgrade Differential Compression Algorithm Based on Suffix Array Induced Sorting and BsDiff Methods

  Xinrong Zhang, Ying Wang, Yanzhao Su · 2024 · Applied Sciences · 3 citations

• Suffixient Arrays: A New Efficient Suffix Array Compression Technique

  Davide Cenzato, Lore Depuydt, Travis Gagie · 2026 · Theory of Computing Systems · 2 citations

• Adaptive Encodings for Small and Fast Compressed Suffix Arrays

  Diego Díaz-Domínguez, Veli Mäkinen · 2026 · ACM Transactions on Algorithms · 0 citations

• OptiM—a referential genome compression algorithm based on suffix array using an optimal strategy for seeking common substrings

  Tingting Yi, Jianhua Chen · 2025 · Advances in Engineering Technology Research · 0 citations

📚 Books worth reading

• Fundamentals of data structures in CEllis Horowitz · 1993
• Data Structures and Algorithms in JavaMichael T. Goodrich, Roberto Tamassia · 2014
• Data structures, algorithms, and performanceDerick Wood · 1992
• The Burrowswheeler Transform Data Compression Suffix Arrays And Pattern MatchingDonald Adjeroh · 2010
• The Burrowswheeler Transform Data Compression Suffix Arrays And Pattern MatchingTimothy Bell · 2008
• 📕Burrows-Wheeler Transform : Donald Adjeroh, Timothy Bell · 2008
• Fundamentals of data structures in CEllis Horowitz · 2008
• Combinatorial pattern matchingSymposium on Combinatorial Pattern Matching (8th 1997 Aarhus, Denmark) · 1997

Ranked by number of editions on Open Library, a rough measure of how lasting a book is.

🔗 Related topics

• Wavelet Tree The wavelet tree is a succinct data structure to store strings in compressed space. It generalizes the r a n k q {\displaystyle \mathbf {rank} _{q}} and…
• Compressed data structure The term compressed data structure arises in the computer science subfields of algorithms, data structures, and theoretical computer science. It refers…
• Suffix array In computer science, a suffix array is a sorted array of all suffixes of a string. It is a data structure used in, among others, full-text indices, data-compres…
• Generalized suffix array In computer science, a generalized suffix array (GSA) is a suffix array containing all suffixes for a set of strings. Given the set of strings S = S 1…
• Substring index In computer science, a substring index is a data structure which gives substring search in a text or text collection in sublinear time. Once constructed…
• Suffix tree In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the…
• Succinct data structure In computer science, a succinct data structure is a data structure which uses an amount of space that is "close" to the information-theoretic lower bound…
• Jeffrey Vitter Jeffrey Scott Vitter is a U.S. computer scientist and academic administrator. Born in 1955 in New Orleans, Vitter has served in several senior higher education…