{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:21:13Z","timestamp":1758273673712},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642389047"},{"type":"electronic","value":"9783642389054"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38905-4_9","type":"book-chapter","created":{"date-parts":[[2013,5,15]],"date-time":"2013-05-15T23:28:54Z","timestamp":1368660534000},"page":"74-82","source":"Crossref","is-referenced-by-count":3,"title":["A Constant-Space Comparison-Based Algorithm for Computing the Burrows\u2013Wheeler Transform"],"prefix":"10.1007","author":[{"given":"Maxime","family":"Crochemore","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juha","family":"K\u00e4rkk\u00e4inen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gad M.","family":"Landau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Adjeroh, D., Bell, T., Mukherjee, A.: The Burrows\u2013Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching. Springer (2008)","DOI":"10.1007\/978-0-387-78909-5"},{"key":"9_CR2","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Research Report 124, Digital SRC, Palo Alto, CA, USA (May 1994)"},{"issue":"2","key":"9_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1721837.1721842","volume":"6","author":"T.M. Chan","year":"2010","unstructured":"Chan, T.M.: Comparison-based time-space lower bounds for selection. ACM Trans. Algorithms\u00a06(2), 1\u201316 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"9_CR4","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1145\/322261.322264","volume":"28","author":"D.J. Dobkin","year":"1981","unstructured":"Dobkin, D.J., Ian Munro, J.: Optimal time minimal space selection algorithms. Journal of the ACM\u00a028(3), 454\u2013461 (1981)","journal-title":"Journal of the ACM"},{"issue":"4","key":"9_CR5","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/978-3-540-73420-8_47","volume-title":"Automata, Languages and Programming","author":"G. Franceschini","year":"2007","unstructured":"Franceschini, G., Muthukrishnan, S.: In-Place Suffix Sorting. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 533\u2013545. Springer, Heidelberg (2007)"},{"key":"9_CR7","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: SODA, pp. 841\u2013850 (2003)"},{"issue":"7","key":"9_CR8","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"C.A.R. Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 65: Find. Communications of the ACM\u00a04(7), 321\u2013322 (1961)","journal-title":"Communications of the ACM"},{"issue":"1","key":"9_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s00453-006-1228-8","volume":"48","author":"W.-K. Hon","year":"2007","unstructured":"Hon, W.-K., Lam, T.W., Sadakane, K., Sung, W.-K., Yiu, S.-M.: A space and time efficient algorithm for constructing compressed suffix arrays. Algorithmica\u00a048(1), 23\u201336 (2007)","journal-title":"Algorithmica"},{"issue":"6","key":"9_CR10","doi-asserted-by":"publisher","first-page":"2162","DOI":"10.1137\/070685373","volume":"38","author":"W.-K. Hon","year":"2009","unstructured":"Hon, W.-K., Sadakane, K., Sung, W.-K.: Breaking a time-and-space barrier in constructing full-text indices. SIAM J. Comput.\u00a038(6), 2162\u20132178 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9_CR11","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.tcs.2007.07.018","volume":"387","author":"J. K\u00e4rkk\u00e4inen","year":"2007","unstructured":"K\u00e4rkk\u00e4inen, J.: Fast BWT in small space by blockwise suffix sorting. Theor. Comput. Sci.\u00a0387(3), 249\u2013257 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Lam, T.W., Li, R., Tam, A., Wong, S., Wu, E., Yiu, S.M.: High Throughput Short Read Alignment via Bi-directional BWT. In: IEEE International Conference on Bioinformatics and Biomedicine, pp. 31\u201336 (2009)","DOI":"10.1109\/BIBM.2009.42"},{"issue":"3","key":"9_CR13","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B. Langmead","year":"2009","unstructured":"Langmead, B., Trapnell, C., Pop, M., Salzberg, S.L.: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biology\u00a010(3), R25 (2009)","journal-title":"Genome Biology"},{"issue":"5","key":"9_CR14","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","volume":"26","author":"H. Li","year":"2010","unstructured":"Li, H., Durbin, R.: Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinformatics\u00a026(5), 589\u2013595 (2010)","journal-title":"Bioinformatics"},{"issue":"5","key":"9_CR15","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"9_CR16","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1145\/382780.382782","volume":"48","author":"G. Manzini","year":"2001","unstructured":"Manzini, G.: An analysis of the Burrows-Wheeler transform. J. ACM\u00a048(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"key":"9_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"J. Ian Munro","year":"1996","unstructured":"Ian Munro, J.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 37\u201342. Springer, Heidelberg (1996)"},{"issue":"2","key":"9_CR18","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(95)00225-1","volume":"165","author":"J. Ian Munro","year":"1996","unstructured":"Ian Munro, J., Raman, V.: Selection from read-only memory and sorting with minimum data movement. Theoretical Computer Science\u00a0165(2), 311\u2013323 (1996)","journal-title":"Theoretical Computer Science"},{"issue":"1-3","key":"9_CR19","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.tcs.2007.05.030","volume":"385","author":"J.C. Na","year":"2007","unstructured":"Na, J.C., Park, K.: Alphabet-independent linear-time construction of compressed suffix arrays using o(nlogn)-bit working space. Theor. Comput. Sci.\u00a0385(1-3), 127\u2013136 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-03784-9_9","volume-title":"String Processing and Information Retrieval","author":"D. Okanohara","year":"2009","unstructured":"Okanohara, D., Sadakane, K.: A linear-time Burrows-Wheeler transform using induced sorting. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 90\u2013101. Springer, Heidelberg (2009)"},{"issue":"2","key":"9_CR21","first-page":"162","volume":"6","author":"V. Raman","year":"1999","unstructured":"Raman, V., Ramnath, S.: Improved Upper Bounds for Time-Space Trade-offs for Selection. Nordic J. Computing\u00a06(2), 162\u2013180 (1999)","journal-title":"Nordic J. Computing"},{"issue":"43","key":"9_CR22","doi-asserted-by":"publisher","first-page":"4350","DOI":"10.1016\/j.tcs.2009.07.016","volume":"410","author":"M. Salson","year":"2009","unstructured":"Salson, M., Lecroq, T., L\u00e9onard, M., Mouchard, L.: A four-stage algorithm for updating a Burrows\u2013Wheeler Transform. Theor. Comput. Sci.\u00a0410(43), 4350\u20134359 (2009)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38905-4_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T21:48:57Z","timestamp":1557697737000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38905-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642389047","9783642389054"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38905-4_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}