{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:31:02Z","timestamp":1760243462061,"version":"build-2065373602"},"reference-count":51,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2013,5,21]],"date-time":"2013-05-21T00:00:00Z","timestamp":1369094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The suffix tree is an extremely important data structure in bioinformatics. Classical implementations require much space, which renders them useless to handle large sequence collections. Recent research has obtained various compressed representations for suffix trees, with widely different space-time tradeoffs. In this paper we show how the use of range min-max trees yields novel representations achieving practical space\/time tradeoffs. In addition, we show how those trees can be modified to index highly repetitive collections, obtaining the first compressed suffix tree representation that effectively adapts to that scenario.<\/jats:p>","DOI":"10.3390\/a6020319","type":"journal-article","created":{"date-parts":[[2013,5,21]],"date-time":"2013-05-21T14:22:12Z","timestamp":1369146132000},"page":"319-351","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["Practical Compressed Suffix Trees"],"prefix":"10.3390","volume":"6","author":[{"given":"Andr\u00e9s","family":"Abeliuk","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Chile, Santiago 8320000, Chile"}]},{"given":"Rodrigo","family":"C\u00e1novas","sequence":"additional","affiliation":[{"name":"NICTA Victoria Research Laboratory, Department of Computing and Information Systems; University of Melbourne, Victoria 3010, Australia;"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Chile, Santiago 8320000, Chile"}]}],"member":"1968","published-online":{"date-parts":[[2013,5,21]]},"reference":[{"key":"ref_1","unstructured":"MIT Technology Review. Available online: http:\/\/www.technologyreview.com\/featuredstory\/511051\/inside-chinas-genome-factory."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","article-title":"A space-economical suffix tree construction algorithm","volume":"32","author":"McCreight","year":"1976","journal-title":"J. ACM"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Weiner, P. (1973, January 15\u201317). Linear Pattern Matching Algorithms. Proceedings of the IEEE Symposium on Switching and Automata Theory, Iowa City, IA, USA.","DOI":"10.1109\/SWAT.1973.13"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Apostolico, A. (1985). Combinatorial Algorithms on Words, Springer-Verlag.","DOI":"10.1007\/978-3-642-82456-2"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Gusfield, D. (1997). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press.","DOI":"10.1017\/CBO9780511574931"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1002\/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O","article-title":"Reducing the space requirements of suffix trees","volume":"29","author":"Kurtz","year":"1999","journal-title":"Softw. Prac. Exp."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix arrays: A new method for on-line string searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM J. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","article-title":"Replacing suffix trees with enhanced suffix arrays","volume":"2","author":"Abouelhoda","year":"2004","journal-title":"J. Discret. Algorithms"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jagm.2000.1151","article-title":"Space efficient suffix trees","volume":"39","author":"Munro","year":"2001","journal-title":"J. Algorithms"},{"key":"ref_10","unstructured":"Sadakane, K. (2002, January 6\u20138). Succinct Representations of Lcp Information and Improvements in the Compressed Suffix Arrays. Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, CA, USA."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","article-title":"Compressed suffix trees with full functionality","volume":"41","author":"Sadakane","year":"2007","journal-title":"Theory Comput. Syst."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","article-title":"New text indexing functionalities of the compressed suffix arrays","volume":"48","author":"Sadakane","year":"2003","journal-title":"J. Algorithms"},{"key":"ref_13","unstructured":"Russo, L., Navarro, G., and Oliveira, A. (2008, January 7\u201311). Fully-Compressed Suffix Trees. Proceedings of the 8th Latin American Symposium on Theoretical Informatics (LATIN), Rio de Janeiro, Brazil."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Russo, L., Navarro, G., and Oliveira, A. (2011). Fully-compressed suffix trees. ACM Trans. Algorithms, 7.","DOI":"10.1145\/2000807.2000821"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., and Navarro, G. (2007). Compressed representations of sequences and full-text indexes. ACM Trans. Algorithms, 3.","DOI":"10.1145\/1240233.1240243"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1145\/382780.382782","article-title":"An analysis of the Burrows-Wheeler transform","volume":"48","author":"Manzini","year":"2001","journal-title":"J. ACM"},{"key":"ref_17","unstructured":"Fischer, J., M\u00e4kinen, V., and Navarro, G. (2008, January 18\u201320). An(other) Entropy-Bounded Compressed Suffix Tree. Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching (CPM), Pisa, Italy."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"5354","DOI":"10.1016\/j.tcs.2009.09.012","article-title":"Faster entropy-bounded compressed suffix trees","volume":"410","author":"Fischer","year":"2009","journal-title":"Theory Comput. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/j.ipl.2010.02.010","article-title":"Wee LCP","volume":"110","author":"Fischer","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"V\u00e4lim\u00e4ki, N., Gerlach, W., Dixit, K., and M\u00e4kinen, V. (2007, January 6\u20138). Engineering a Compressed Suffix Tree Implementation. Proceedings of the 6th Workshop on Experimental Algorithms (WEA), Rome, Italy.","DOI":"10.1007\/978-3-540-72845-0_17"},{"key":"ref_21","unstructured":"Gog, S. (2011). Compressed Suffix Trees: Design, Construction, and Applications. [Ph.D. Thesis, University of Ulm]."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Sadakane, K., and Navarro, G. (2010, January 17\u201319). Fully-Functional Succinct Trees. Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Austin, TX, USA.","DOI":"10.1137\/1.9781611973075.13"},{"key":"ref_23","unstructured":"Arroyuelo, D., C\u00e1novas, R., Navarro, G., and Sadakane, K. (2009, January 3). Succinct Trees in Practice. Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX), New York, NY, USA."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Kreft, S., and Navarro, G. (2011, January 27\u201329). Self-Indexing Based on LZ77. Proceedings of the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM), Palermo, Italy.","DOI":"10.1007\/978-3-642-21458-5_6"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1089\/cmb.2009.0169","article-title":"Storage and retrieval of highly repetitive sequence collections","volume":"17","author":"Navarro","year":"2010","journal-title":"J. Comput. Biol."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Claude, F., and Navarro, G. (2009, January 24\u201328). Self-Indexed Text Compression Using Straight-Line Programs. Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS), Novy Smokovec, Slovakia.","DOI":"10.1007\/978-3-642-03816-7_21"},{"key":"ref_27","unstructured":"Claude, F., Fari\u00f1a, A., Mart\u00ednez-Prieto, M., and Navarro, G. (June, January 31). Compressed q-Gram Indexing for Highly Repetitive Biological Sequences. Proceedings of the 10th IEEE Conference on Bioinformatics and Bioengineering (BIBE), Philadelphia, PA, USA."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Ohlebusch, E., Fischer, J., and Gog, S. (2010, January 11\u201313). CST++. Proceedings of the 17th International Symposium on String Processing and Information Retrieval (SPIRE), Los Cabos, Mexico.","DOI":"10.1007\/978-3-642-16321-0_34"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"C\u00e1novas, R., and Navarro, G. (2010, January 20\u201322). Practical Compressed Suffix Trees. Proceedings of the 9th International Symposium on Experimental Algorithms (SEA), Ischia Island, Italy.","DOI":"10.1007\/978-3-642-13193-6_9"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Abeliuk, A., and Navarro, G. (2012, January 21\u201325). Compressed Suffix Trees for Repetitive Texts. Proceedings of the 19th International Symposium on String Processing and Information Retrieval (SPIRE), Cartagena, Colombia.","DOI":"10.1007\/978-3-642-34109-0_5"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Navarro, G., and M\u00e4kinen, V. (2007). Compressed full-text indexes. ACM Comput. Surv., 39.","DOI":"10.1145\/1216370.1216372"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Gonz\u00e1lez, R., Navarro, G., and Venturini, R. (2009). Compressed text indexes: From theory to practice. ACM J. Exp. Algorithmics, 13.","DOI":"10.1145\/1412228.1455268"},{"key":"ref_33","unstructured":"Munro, I. (1996, January 18\u201320). Tables. Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Hyderabad, India."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1722","DOI":"10.1109\/5.892708","article-title":"Off-Line dictionary-based compression","volume":"88","author":"Larsson","year":"2000","journal-title":"Proc. IEEE"},{"key":"ref_35","unstructured":"Gonz\u00e1lez, R., and Navarro, G. (2007, January 9\u201311). Compressed Text Indexes with Fast Locate. Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM), London, Canada."},{"key":"ref_36","first-page":"40","article-title":"Succinct suffix arrays based on run-length encoding","volume":"12","author":"Navarro","year":"2005","journal-title":"Nord. J. Comput."},{"key":"ref_37","unstructured":"Raman, R., Raman, V., and Rao, S. (2002, January 6\u20138). Succinct Indexable Dictionaries with Applications to Encoding k-Ary Trees and Multisets. Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, CA, USA."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Okanohara, D., and Sadakane, K. (2007, January 6). Practical Entropy-Compressed Rank\/Select Dictionary. Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, LA, USA.","DOI":"10.1137\/1.9781611972870.6"},{"key":"ref_39","unstructured":"Gonz\u00e1lez, R., Grabowski, S., M\u00e4kinen, V., and Navarro, G. (2005, January 10\u201313). Practical Implementation of Rank and Select Queries. Proceedings of the posters 4th Workshop on Experimental Algorithms (WEA), Santorini Island, Greece."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Claude, F., and Navarro, G. (2008, January 10\u201312). Practical Rank\/Select Queries over Arbitrary Sequences. Proceedings of the 15th International Symposium on String Processing and Information Retrieval (SPIRE), Melbourne Australia.","DOI":"10.1007\/978-3-540-89097-3_18"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Puglisi, S., and Turpin, A. (2008, January 15\u201317). Space-Time Tradeoffs for Longest-Common-Prefix Array Computation. Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC), Gold Coast, Australia.","DOI":"10.1007\/978-3-540-92182-0_14"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Manzini, G., and Puglisi, S. (2009, January 22\u201324). Permuted Longest-Common-Prefix Array. Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM), Lille, France.","DOI":"10.1007\/978-3-642-02441-2_17"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Brisaboa, N., Ladra, S., and Navarro, G. (2009, January 25\u201327). Directly Addressable Variable-length Codes. Proceedings of the 16th International Symposium on String Processing and Information Retrieval (SPIRE), Saariselk, Finland.","DOI":"10.1007\/978-3-642-03784-9_12"},{"key":"ref_44","unstructured":"Pizza & Chili Corpus. Available online: http:\/\/pizzachili.dcc.uchile.cl."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.tcs.2006.09.014","article-title":"A simple optimal representation for balanced parentheses","volume":"368","author":"Geary","year":"2006","journal-title":"Theory Comput. Sci."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/090779759","article-title":"Space-Efficient preprocessing schemes for range minimum queries on static arrays","volume":"40","author":"Fischer","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Konow, R., and Navarro, G. (2013, January 20). Faster Compact Top-k Document Retrieval. Proceedings of the 23rd Data Compression Conference (DCC), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2013.43"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1016\/j.jda.2004.08.016","article-title":"A fully linear-time approximation algorithm for grammar-based compression","volume":"3","author":"Sakamoto","year":"2005","journal-title":"J. Discret. Algorithms"},{"key":"ref_49","unstructured":"Pizza & Chili Repetitive Corpus. Available online: http:\/\/pizzachili.dcc.uchile.cl\/repcorpus."},{"key":"ref_50","unstructured":"Software Page of Gonzalo Navarro. Available online: http:\/\/www.dcc.uchile.cl\/gnavarro\/software."},{"key":"ref_51","unstructured":"Pizza & Chili Corpus. Available online: http:\/\/pizzachili.dcc.uchile.cl\/cst."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/2\/319\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:46:53Z","timestamp":1760219213000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/2\/319"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,21]]},"references-count":51,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2013,6]]}},"alternative-id":["a6020319"],"URL":"https:\/\/doi.org\/10.3390\/a6020319","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2013,5,21]]}}}