The DOI matches its Crossref record.
Suffix Arrays: A New Method for On-Line String Searches
Abstract
A new and conceptually simple data structure, called a suffix array, for on-line string searches is introduced in this paper. Constructing and querying suffix arrays is reduced to a sort and search paradigm that employs novel algorithms. The main advantage of suffix arrays over suffix trees is that, in practice, they use three to five times less space. From a complexity standpoint, suffix arrays permit on-line string searches of the type, “Is W a substring of A?” to be answered in time $O(P + \log N)$, where P is the length of W and N is the length of A, which is competitive with (and in some cases slightly better than) suffix trees. The only drawback is that in those instances where the underlying alphabet is finite and small, suffix trees can be constructed in $O(N)$ time in the worst case, versus $O(N\log N)$ time for suffix arrays. However, an augmented algorithm is given that, regardless of the alphabet size, constructs suffix arrays in $O(N)$expected time, albeit with lesser space efficiency. It is believed that suffix arrays will prove to be better in practice than suffix trees for many applications.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
STAR: ultrafast universal RNA-seq aligner
Dobin, A., Davis, C. A., Schlesinger, F., Drenkow, J., Zaleski, C., Jha, S., Batut, P., Chaisson, M., & Gingeras, T. R. (2013) · Bioinformatics · doi:10.1093/bioinformatics/bts635 · Cited by 51,709
Huang, L., Yu, W., Ma, W., Zhong, W., Feng, Z., Wang, H., Chen, Q., Peng, W., Feng, X., Qin, B., et al. (2025) · ACM Transactions on Information Systems · doi:10.1145/3703155 · Cited by 4,688
“In addition, a more efficient method utilizes the construction of a suffix array (Manber and Myers, 1993), enabling effective computation of numerous substring queries in linear time.”
Fast and SNP-tolerant detection of complex variants and splicing in short reads
Wu, T. D., & Nacu, S. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq057 · Cited by 1,894
Ashley, E. A. (2016) · Nature Reviews Genetics · doi:10.1038/nrg.2016.86 · Cited by 1,116
A survey of sequence alignment algorithms for next-generation sequencing
Li, H., & Homer, N. (2010) · Briefings in Bioinformatics · doi:10.1093/bib/bbq015 · Cited by 875
Navarro, G., & Mäkinen, V. (2007) · ACM Computing Surveys · doi:10.1145/1216370.1216372 · Cited by 735
Deduplicating Training Data Makes Language Models Better
Lee, K., Ippolito, D., Nystrom, A., Zhang, C., Eck, D., Callison-Burch, C., & Carlini, N. (2022) · Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2022.acl-long.577 · Cited by 304
Huang, L., Yu, W., Ma, W., Zhong, W., Feng, Z., Wang, H., Chen, Q., Peng, W., Feng, X., Qin, B., et al. (2023) · arXiv · doi:10.48550/arxiv.2311.05232 · Cited by 2,516
“In addition, a more efficient method utilizes the construction of a suffix array (Manber and Myers, 1993), enabling effective computation of numerous substring queries in linear time.”
The BigScience ROOTS Corpus: A 1.6TB Composite Multilingual Dataset
Laurençon, H., Saulnier, L., Wang, T., Akiki, C., del Moral, A. V., Scao, T. L., Von Werra, L., Mou, C., Ponferrada, E. G., Nguyen, H., et al. (2023) · arXiv · doi:10.48550/arxiv.2303.03915 · Cited by 93
“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.”
MethodFast Plagiarism Detection System
Mozgovoy, M., Fredriksson, K., White, D., Joy, M., & Sutinen, E. (2005) · Lecture Notes in Computer Science · doi:10.1007/11575832_30 · Cited by 49
Application of a superword array in genome assembly
Huang, X. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkj419 · Cited by 30
Sankar, B. S., Gilliland, D., Rincon, J., Hermjakob, H., Yan, Y., Adam, I., Lemaster, G., Wang, D., Watson, K., Bui, A., et al. (2024) · Bioengineering · doi:10.3390/bioengineering11100984 · Cited by 26
Efficient inverted index with n-gram sampling for string matching in Arabic documents
Nagoudi, E. M. B., Khorsi, A., & Cherroun, H. (2016) · 2016 IEEE/ACS 13th International Conference of Computer Systems and Applications (AICCSA) · doi:10.1109/aiccsa.2016.7945743 · Cited by 1
Metadata
- Authors
- Manber, U., & Myers, G.
- Venue
- SIAM Journal on Computing
- Published
- 1993-10
- Volume
- 22
- Issue
- 5
- Pages
- 935-948
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2158874082
- Cited by
- 1,915
- References
- 0
- FWCI
- 11.36
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
