{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T23:03:33Z","timestamp":1743375813343},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_17","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"181-192","source":"Crossref","is-referenced-by-count":20,"title":["New Lower and Upper Bounds for Representing Sequences"],"prefix":"10.1007","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-17514-5_27","volume-title":"Algorithms and Computation","author":"J. Barbay","year":"2010","unstructured":"Barbay, J., Gagie, T., Navarro, G., Nekrich, Y.: Alphabet Partitioning for Compressed Rank\/Select and Applications. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part II. LNCS, vol.\u00a06507, pp. 315\u2013326. Springer, Heidelberg (2010)"},{"key":"17_CR2","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":"17_CR3","unstructured":"Barbay, J., Navarro, G.: Compressed representations of permutations, and applications. In: Proc. 26th STACS, pp. 111\u2013122 (2009)"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monotone minimal perfect hashing: searching a sorted table with o(1) accesses. In: Proc. 20th SODA, pp. 785\u2013794 (2009)","DOI":"10.1137\/1.9781611973068.86"},{"key":"17_CR5","unstructured":"Belazzougui, D., Navarro, G.: New lower and upper bounds for representing sequences. CoRR, arXiv:1111.26211v1 (2011) \n                  \n                    http:\/\/arxiv.org\/abs\/1111.2621v1"},{"key":"17_CR6","unstructured":"Clark, D.: Compact Pat Trees. PhD thesis, University of Waterloo, Canada (1996)"},{"key":"17_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-642-12476-1_5","volume-title":"Algorithms and Applications","author":"F. Claude","year":"2010","unstructured":"Claude, F., Navarro, G.: Extended Compact Web Graph Representations. In: Elomaa, T., Mannila, H., Orponen, P. (eds.) Ukkonen Festschrift 2010. LNCS, vol.\u00a06060, pp. 77\u201391. Springer, Heidelberg (2010)"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and indexing labeled trees, with applications. Journal of the ACM\u00a057(1) (2009)","DOI":"10.1145\/1613676.1613680"},{"issue":"4","key":"17_CR9","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 texts. Journal of the ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"Journal of the ACM"},{"issue":"2","key":"17_CR10","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1145\/1240233.1240243","volume":"3","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms\u00a03(2), article 20 (2007)","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"17_CR11","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.012","volume":"372","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. Theoretical Computer Science\u00a0372(1), 115\u2013121 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"17_CR12","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/j.ipl.2006.04.008","volume":"99","author":"T. Gagie","year":"2006","unstructured":"Gagie, T.: Large alphabets and incompressibility. Information Processing Letters\u00a099(6), 246\u2013251 (2006)","journal-title":"Information Processing Letters"},{"key":"17_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-642-16321-0_7","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2010","unstructured":"Gagie, T., Navarro, G., Puglisi, S.J.: Colored Range Queries and Document Retrieval. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 67\u201381. Springer, Heidelberg (2010)"},{"issue":"3","key":"17_CR14","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.tcs.2007.07.041","volume":"387","author":"A. Golynski","year":"2007","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. Theoretical Computer Science\u00a0387(3), 348\u2013359 (2007)","journal-title":"Theoretical Computer Science"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Golynski, A.: Cell probe lower bounds for succinct data structures. In: Proc. 20th SODA, pp. 625\u2013634 (2009)","DOI":"10.1137\/1.9781611973068.69"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, I., Rao, 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":"17_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-540-69903-3_15","volume-title":"Algorithm Theory \u2013 SWAT 2008","author":"A. Golynski","year":"2008","unstructured":"Golynski, A., Raman, R., Rao, S.S.: On the Redundancy of Succinct Data Structures. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol.\u00a05124, pp. 148\u2013159. Springer, Heidelberg (2008)"},{"key":"17_CR18","unstructured":"Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proc. 14th SODA, pp. 841\u2013850 (2003)"},{"key":"17_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1007\/978-3-642-14165-2_57","volume-title":"Automata, Languages and Programming","author":"R. Grossi","year":"2010","unstructured":"Grossi, R., Orlandi, A., Raman, R.: Optimal Trade-Offs for Succinct String Indexes. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 678\u2013689. Springer, Heidelberg (2010)"},{"key":"17_CR20","unstructured":"Gupta, A., Hon, W.-K., Shah, R., Vitter, J.: Dynamic rank\/select dictionaries with applications to XML indexing. Technical Report CSD TR #06-014, Purdue University (July 2006)"},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proc. 30th FOCS, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"issue":"3","key":"17_CR22","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":"17_CR23","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":"I. Munro","year":"1996","unstructured":"Munro, I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 37\u201342. Springer, Heidelberg (1996)"},{"key":"17_CR24","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":"17_CR25","doi-asserted-by":"crossref","unstructured":"Patrascu, M.: Succincter. In: Proc. 49th FOCS, pp. 305\u2013313 (2008)","DOI":"10.1109\/FOCS.2008.83"},{"key":"17_CR26","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proc. 38th STOC, pp. 232\u2013240 (2006)","DOI":"10.1145\/1132516.1132551"},{"key":"17_CR27","unstructured":"Patrascu, M., Thorup, M.: Time-space trade-offs for predecessor search. CoRR, cs\/0603043v1 (2008), \n                  \n                    http:\/\/arxiv.org\/pdf\/cs\/0603043v1"},{"key":"17_CR28","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Viola, E.: Cell-probe lower bounds for succinct partial sums. In: Proc. 21st SODA, pp. 117\u2013122 (2010)","DOI":"10.1137\/1.9781611973075.11"},{"key":"17_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-73437-6_22","volume-title":"Combinatorial Pattern Matching","author":"N. V\u00e4lim\u00e4ki","year":"2007","unstructured":"V\u00e4lim\u00e4ki, N., M\u00e4kinen, V.: Space-Efficient Algorithms for Document Retrieval. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 205\u2013215. Springer, Heidelberg (2007)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:54:45Z","timestamp":1620129285000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}