{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,24]],"date-time":"2026-10-24T18:53:12Z","timestamp":1792867992482,"version":"4.5.0"},"reference-count":72,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>The proliferation of online text, such as found on the World Wide Web and in online databases, motivates the need for space-efficient text indexing methods that support fast string searching. We model this scenario as follows: Consider a text T consisting of n symbols drawn from a fixed alphabet $\\Sigma$. The text T can be represented in $n \\lg |\\Sigma|$ bits by encoding each symbol with $\\lg |\\Sigma|$ bits. The goal is to support fast online queries for searching any string pattern P of m symbols, with T being fully scanned only once, namely, when the index is created at preprocessing time. The text indexing schemes published in the literature are greedy in terms of space usage: they require $\\Omega(n \\lg n)$ additional bits of space in the worst case. For example, in the standard unit cost RAM, suffix trees and suffix arrays need $\\Omega(n)$ memory words, each of $\\Omega(\\lg n)$ bits. These indexes are larger than the text itself by a multiplicative factor of $\\Omega(\\smash{\\lg_{|\\Sigma|} n})$, which is significant when $\\Sigma$ is of constant size, such as in \\textsc{ascii} or \\textsc{unicode}. On the other hand, these indexes support fast searching, either in $O(m \\lg |\\Sigma|)$ time or in $O(m +\\lg n)$ time, plus an output-sensitive cost $O(\\mathit{occ})$ for listing the $\\mathit{occ}$ pattern occurrences. We present a new text index that is based upon compressed representations of suffix arrays and suffix trees. It achieves a fast $\\smash{O(m \/\\lg_{|\\Sigma|} n + \\lg_{|\\Sigma|}^\\epsilon n)}$ search time in the worst case, for any constant $0 &lt; \\epsilon \\leq 1$, using at most $\\smash{\\bigl(\\epsilon^{-1} + O(1)\\bigr) \\, n \\lg |\\Sigma|}$ bits of storage. Our result thus presents for the first time an efficient index whose size is provably linear in the size of the text in the worst case, and for many scenarios, the space is actually sublinear in practice. As a concrete example, the compressed suffix array for a typical 100 MB \\textsc{ascii} file can require 30--40 MB or less, while the raw suffix array requires 500 MB. Our theoretical bounds improve \\emph{both} time and space of previous indexing schemes. Listing the pattern occurrences introduces a sublogarithmic slowdown factor in the output-sensitive cost, giving $O(\\mathit{occ} \\, \\smash{\\lg_{|\\Sigma|}^\\epsilon n})$ time as a result. When the patterns are sufficiently long, we can use auxiliary data structures in $O(n \\lg |\\Sigma|)$ bits to obtain a total search bound of $O(m \/\\lg_{|\\Sigma|} n + \\mathit{occ})$ time, which is optimal.<\/jats:p>","DOI":"10.1137\/s0097539702402354","type":"journal-article","created":{"date-parts":[[2005,10,24]],"date-time":"2005-10-24T21:00:13Z","timestamp":1130187613000},"page":"378-407","source":"Crossref","is-referenced-by-count":285,"title":["Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching"],"prefix":"10.1137","volume":"35","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Stephen Alstrup, Gerth Brodal, Theis Rauhe, New data structures for orthogonal range searching, IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, 198\u20132071931818","DOI":"10.1109\/SFCS.2000.892088"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"A. Amir and G. Benson,\n                      Efficient two\u2010dimensional compressed matching\n                      , in Proceedings of the IEEE Data Compression Conference, J. A. Storer and M. Cohn, eds., IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 279\u2013288.","DOI":"10.1109\/DCC.1992.227453"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0023"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1104"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009260"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380250203"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Alberto Apostolico, The myriad virtues of subword trees, NATO Adv. Sci. Inst. Ser. F Comput. Systems Sci., Vol. 12, Springer, Berlin, 1985, 85\u201396815333","DOI":"10.1007\/978-3-642-82456-2_6"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762122"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263991"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90157-4"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28873"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Gerth Brodal, Leszek Ga\u00b8sieniec, Approximate dictionary queries, Lecture Notes in Comput. Sci., Vol. 1075, Springer, Berlin, 1996, 65\u2013741436874","DOI":"10.1007\/3-540-61258-0_6"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795294165"},{"key":"R14","unstructured":"M. Burrows and D. J. Wheeler,\n                      A Block Sorting Data Compression Algorithm\n                      , Tech. report, Digital Systems Research Center, Palo Alto, CA, 1994."},{"key":"R15","unstructured":"D. Clark,\n                      Compact Pat Trees\n                      , Ph.D. thesis, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, 1996."},{"key":"R16","unstructured":", Proceedings of the Seventh Annual ACM\u2010SIAM Symposium on Discrete Algorithms, Association for Computing Machinery (ACM), 1996, 0\u20130, x+586, Held in Atlanta, Georgia, January 28\u201330, 199696j:68007"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00061-0"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90041-1"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116845"},{"key":"R20","volume-title":"Text algorithms","author":"Crochemore Maxime","year":"1994"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"E. S. de Moura, G. Navarro, and N. Ziviani,\n                      Indexing compressed text\n                      , in Proceedings of the South American Workshop on String Processing, Carleton University Press, Ottawa, Ontario, Canada, 1997, pp. 95\u2013111.","DOI":"10.1515\/9780773591400-010"},{"key":"R22","unstructured":"Erik Demaine, Alejandro L\u00f3pez\u2010Ortiz, A linear lower bound on index size for text retrieval, SIAM, Philadelphia, PA, 2001, 289\u20132941958421"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009202"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"M. Farach\u2010Colton,\n                      Optimal suffix tree construction with large alphabets\n                      , in Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, FL, 1997, pp. 137\u2013143.","DOI":"10.1109\/SFCS.1997.646102"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355547"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Martin Farach, S. Muthukrishnan, Optimal logarithmic time randomized suffix tree construction, Lecture Notes in Comput. Sci., Vol. 1099, Springer, Berlin, 1996, 550\u20135611464475","DOI":"10.1007\/3-540-61440-0_158"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301973"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Paolo Ferragina, Giovanni Manzini, Opportunistic data structures with applications, IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, 390\u20133981931836","DOI":"10.1109\/SFCS.2000.892127"},{"key":"R30","unstructured":"P. Ferragina and G. Manzini,\n                      An experimental study of an opportunistic index\n                      , in Proceedings of the 12th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2001, pp. 269\u2013278."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Anna G\u00e1l, Peter Miltersen, The cell probe complexity of succinct data structures, Lecture Notes in Comput. Sci., Vol. 2719, Springer, Berlin, 2003, 332\u20133442080711","DOI":"10.1007\/3-540-45061-0_28"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90002-8"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"R. Giegerich, S. Kurtz, and J. Stoye,\n                      Efficient implementation of lazy suffix trees\n                      , in Proceedings of the 3rd Workshop on Algorithm Engineering, J. S. Vitter and C. D. Zaroliagis, eds., Lecture Notes in Comput. Sci. 1668, Springer\u2010Verlag, Berlin, 1999, pp. 30\u201342.","DOI":"10.1007\/3-540-48318-7_5"},{"key":"R35","unstructured":"G. H. Gonnet, R. A. Baeza\u2010Yates, and T. Snider,\n                      New indices for text: PAT trees and PAT arrays\n                      , in Information Retrieval: Data Structures And Algorithms, Prentice\u2013Hall, Englewood Cliffs, NJ, 1992, pp. 66\u201382."},{"key":"R36","unstructured":"Roberto Grossi, Ankur Gupta, Jeffrey Vitter, High\u2010order entropy\u2010compressed test indexes, ACM, New York, 2003, 841\u20138501975003"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"Roberto Grossi, Jeffrey Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract), ACM, New York, 2000, 397\u20134062115275","DOI":"10.1145\/335305.335351"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1171"},{"key":"R40","unstructured":"W.\u2010K. Hon, K. Sadakane, and W.\u2010K. Sung,\n                      Breaking a time\u2010and\u2010space barrier in constructing full\u2010text indices\n                      , in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2003, pp. 251\u2013260."},{"key":"R41","unstructured":"R. W. Irving,\n                      Suffix Binary Search Trees\n                      , Tech. report TR\u20101995\u20107, Computing Science Department, University of Glasgow, Glasgow, UK, 1995."},{"key":"R42","doi-asserted-by":"crossref","unstructured":"G. Jacobson,\n                      Space\u2010efficient static trees and graphs\n                      , in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 549\u2013554.","DOI":"10.1109\/SFCS.1989.63533"},{"key":"R43","unstructured":"G. Jacobson,\n                      Succinct Static Data Structures\n                      , Tech. report CMU\u2010CS\u201089\u2010112, Department of Computer Science, Carnegie\u2010Mellon University, Pittsburgh, PA, 1989."},{"key":"R44","doi-asserted-by":"crossref","unstructured":"Juha K\u00e4rkk\u00e4inen, Suffix cactus: a cross between suffix tree and suffix array, Lecture Notes in Comput. Sci., Vol. 937, Springer, Berlin, 1995, 191\u20132041467515","DOI":"10.1007\/3-540-60044-2_43"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009205"},{"key":"R46","unstructured":"J. K\u00e4rkk\u00e4inen and E. Ukkonen,\n                      Lempel\u2010Ziv parsing and sublinear\u2010size index structures for string matching\n                      , in Proceedings of the 3rd South American Workshop on String Processing, N. Ziviani, R. Baeza\u2010Yates, and K. Guimar\u00e3es, eds., Carleton University Press, Ottawa, Ontario, Canada, 1996, pp. 141\u2013155."},{"key":"R47","doi-asserted-by":"crossref","unstructured":"Juha K\u00e4rkk\u00e4inen, Esko Ukkonen, Sparse suffix trees, Lecture Notes in Comput. Sci., Vol. 1090, Springer, Berlin, 1996, 219\u20132301455667","DOI":"10.1007\/3-540-61332-3_155"},{"key":"R48","unstructured":"D. E. Knuth,\n                      Sorting and Searching\n                      , 2nd ed., The Art of Computer Programming 3, Addison\u2010Wesley, Reading, MA, 1998."},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"R50","doi-asserted-by":"crossref","unstructured":"S. R. Kosaraju,\n                      Real\u2010time pattern matching and quasi\u2010real\u2010time construction of suffix tree\n                      , in Proceedings of the 26th ACM Symposium on the Theory of Computing, ACM, New York, pp. 310\u2013316.","DOI":"10.1145\/195058.195170"},{"key":"R51","doi-asserted-by":"crossref","unstructured":"S. R. Kosaraju and A. L. Delcher,\n                      Large\u2010scale assembly of DNA strings and space\u2010efficient construction of suffix trees\n                      , in Proceedings of the Twenty\u2010Seventh Annual ACM Symposium on the Theory of Computing, Las Vegas, NV, 1995, pp. 169\u2013177.","DOI":"10.1145\/225058.225108"},{"key":"R52","doi-asserted-by":"crossref","unstructured":"S. R. Kosaraju and A. L. Delcher,\n                      Correction: Large\u2010scale assembly of DNA strings and space\u2010efficient construction of suffix trees\n                      , in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, 1996, p. 659.","DOI":"10.1145\/237814.250975"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O"},{"key":"R54","unstructured":", Combinatorial pattern matching, Proceedings of the 11th Annual Symposium (CPM 2000), held at the Universit\u00e9 de Montr\u00e9al, Montreal, QC, June 21\u201323, 2000, Lecture Notes in Computer Science, Vol. 1848, Springer\u2010Verlag, 2000, 0\u20130, xii+4232001e:68007"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"R56","unstructured":"U. Manber and S. Wu,\n                      GLIMPSE: A tool to search through entire file systems\n                      , in Proceedings of the USENIX Winter 1994 Technical Conference, 1994, pp. 23\u201332."},{"key":"R57","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1145\/237496.237497"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321481"},{"key":"R60","doi-asserted-by":"crossref","unstructured":"J. Munro, Tables, Lecture Notes in Comput. Sci., Vol. 1180, Springer, Berlin, 1996, 37\u20134298m:68046","DOI":"10.1007\/3-540-62034-6_35"},{"key":"R61","doi-asserted-by":"crossref","unstructured":"J. I. Munro and V. Raman,\n                      Succinct representation of balanced parentheses, static trees and planar graphs\n                      , in Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, 1997, pp. 118\u2013126.","DOI":"10.1109\/SFCS.1997.646100"},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1151"},{"key":"R63","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"R64","doi-asserted-by":"crossref","unstructured":"K. Sadakane,\n                      Compressed text databases with efficient query algorithms based on the compressed suffix array\n                      , in Proceedings of ISAAC \u201900, Lecture Notes in Comput. Sci. 1969, Springer, Berlin, New York, 2000, pp. 410\u2013421.","DOI":"10.1007\/3-540-40996-3_35"},{"key":"R65","unstructured":"K. Sadakane,\n                      Succinct representations of lcp information and improvements in the compressed suffix arrays\n                      , in Proceedings of the 13th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2002, pp. 225\u2013232."},{"key":"R66","doi-asserted-by":"crossref","unstructured":"S. C. Sahinalp and U. Vishkin,\n                      Symmetry breaking for suffix tree construction\n                      , in Proceedings of the 26th Annual Symposium on the Theory of Computing, ACM, 1994, pp. 300\u2013309.","DOI":"10.1145\/195058.195164"},{"key":"R67","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206331"},{"key":"R68","doi-asserted-by":"crossref","unstructured":"P. Weiner,\n                      Linear pattern matching algorithm\n                      , in Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory, 1973, pp. 1\u201311.","DOI":"10.1109\/SWAT.1973.13"},{"key":"R69","doi-asserted-by":"crossref","unstructured":"D. E. Willard,\n                      On the application of sheared retrieval to orthogonal range queries\n                      , in Proceedings of the Second Annual Symposium on Computational Geometry, ACM, New York, 1986, pp. 80\u201389.","DOI":"10.1145\/10515.10524"},{"key":"R70","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0875"},{"key":"R71","doi-asserted-by":"publisher","DOI":"10.1109\/2.881693"},{"key":"R72","doi-asserted-by":"publisher","DOI":"10.1145\/296854.277632"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539702402354","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:17:39Z","timestamp":1787336259000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539702402354"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":72,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0097539702402354"],"URL":"https:\/\/doi.org\/10.1137\/s0097539702402354","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}