{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:15Z","timestamp":1760202615839},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175138"},{"type":"electronic","value":"9783642175145"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17514-5_27","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T15:09:23Z","timestamp":1291388963000},"page":"315-326","source":"Crossref","is-referenced-by-count":31,"title":["Alphabet Partitioning for Compressed Rank\/Select and Applications"],"prefix":"10.1007","author":[{"given":"J\u00e9r\u00e9my","family":"Barbay","sequence":"first","affiliation":[]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[]},{"given":"Yakov","family":"Nekrich","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-61422-2_131","volume-title":"Algorithm Theory - SWAT \u201996","author":"A. Andersson","year":"1996","unstructured":"Andersson, A.: Sorting and searching revisited. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 185\u2013197. Springer, Heidelberg (1996)"},{"issue":"3","key":"27_CR2","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/j.tcs.2007.07.015","volume":"387","author":"J. Barbay","year":"2007","unstructured":"Barbay, J., Golynski, A., Munro, J.I., Rao, S.S.: Adaptive searching in succinctly encoded binary relations and tree-structured documents. Theoretical Computer Science\u00a0387(3), 284\u2013297 (2007)","journal-title":"Theoretical Computer Science"},{"key":"27_CR3","unstructured":"Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. In: Proc. 18th SODA, pp. 680\u2013689 (2007)"},{"key":"27_CR4","unstructured":"Barbay, J., Navarro, G.: Compressed representations of permutations, and applications. In: Proc. 26th STACS, pp. 111\u2013122 (2009)"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Blandford, D., Blelloch, G.: Index compression through document reordering. In: Proc. DCC, pp. 342\u2013351 (2002)","DOI":"10.1109\/DCC.2002.999972"},{"key":"27_CR6","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-540-89097-3_18","volume-title":"String Processing and Information Retrieval","author":"F. Claude","year":"2008","unstructured":"Claude, F., Navarro, G.: Practical rank\/select queries over arbitrary sequences. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol.\u00a05280, pp. 176\u2013187. Springer, Heidelberg (2008)"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms\u00a03(2) (2007)","DOI":"10.1145\/1240233.1240243"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"Gagie, T., Navarro, G., Nekrich, Y.: Fast and compact prefix codes. In: van Leeuwen, J., Muscholl, A., Peleg, D., Pokorn\u00fd, J., Rumpe, B. (eds.) SOFSEM 2010. LNCS, vol.\u00a05901, pp. 419\u2013427. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-11266-9_35"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, J.I., Rao, S.S.: Rank\/select operations on large alphabets: a tool for text indexing. In: Proc. 17th SODA, pp. 368\u2013373 (2006)","DOI":"10.1145\/1109557.1109599"},{"key":"27_CR11","unstructured":"Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proc. 14th SODA, pp. 841\u2013850 (2003)"},{"key":"27_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1007\/978-3-642-04128-0_65","volume-title":"Algorithms - ESA 2009","author":"J.B. Hreinsson","year":"2009","unstructured":"Hreinsson, J.B., Kr\u00f8yer, M., Pagh, R.: Storing a compressed function with constant time access. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 730\u2013741. Springer, Heidelberg (2009)"},{"issue":"1","key":"27_CR13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/inco.1994.1050","volume":"112","author":"C. Levcopoulos","year":"1994","unstructured":"Levcopoulos, C., Petersson, O.: Sorting shuffled monotone sequences. Information and Computation\u00a0112(1), 37\u201350 (1994)","journal-title":"Information and Computation"},{"issue":"3","key":"27_CR14","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.tcs.2007.07.013","volume":"387","author":"V. M\u00e4kinen","year":"2007","unstructured":"M\u00e4kinen, V., Navarro, G.: Rank and select revisited and extended. Theoretical Computer Science\u00a0387(3), 332\u2013347 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"27_CR15","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. Journal of the ACM\u00a048(3), 407\u2013430 (2001)","journal-title":"Journal of the ACM"},{"key":"27_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/3-540-09118-1_22","volume-title":"Theoretical Computer Science","author":"K. Mehlhorn","year":"1979","unstructured":"Mehlhorn, K.: Sorting presorted files. In: Weihrauch, K. (ed.) GI-TCS 1979. LNCS, vol.\u00a067, pp. 199\u2013212. Springer, Heidelberg (1979)"},{"key":"27_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/3-540-45061-0_29","volume-title":"Automata, Languages and Programming","author":"J.I. Munro","year":"2003","unstructured":"Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Succinct representations of permutations. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 345\u2013356. Springer, Heidelberg (2003)"},{"key":"27_CR18","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys\u00a039(1):article 2 (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"27_CR19","volume-title":"Encyclopedia of Algorithms","author":"N. Rahman","year":"2008","unstructured":"Rahman, N., Raman, R.: Rank and select operations on binary strings. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms. Springer, Heidelberg (2008)"},{"key":"27_CR20","unstructured":"Raman, R., Raman, V., Rao, S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th SODA, pp. 233\u2013242 (2002)"},{"issue":"2","key":"27_CR21","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","volume":"48","author":"K. Sadakane","year":"2003","unstructured":"Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. Journal of Algorithms\u00a048(2), 294\u2013313 (2003)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"27_CR22","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., van Leeuwen, J.: Worst-case analysis of set union algorithms. Journal of the ACM\u00a031(2), 245\u2013281 (1984)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17514-5_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,22]],"date-time":"2019-03-22T13:01:59Z","timestamp":1553259719000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17514-5_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175138","9783642175145"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17514-5_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}