{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T19:55:16Z","timestamp":1725738916112},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_43","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"504-515","source":"Crossref","is-referenced-by-count":12,"title":["Dynamic Compressed Strings with Random Access"],"prefix":"10.1007","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satti Srinivasa","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rossano","family":"Venturini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"43_CR1","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/2000807.2000820","volume":"7","author":"J. Barbay","year":"2011","unstructured":"Barbay, J., He, M., Munro, J.I., Satti, S.R.: Succinct indexes for strings, binary relations and multilabeled trees. ACM Transactions on Algorithms\u00a07, 52 (2011)","journal-title":"ACM Transactions on Algorithms"},{"key":"43_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-48447-7_4","volume-title":"Algorithms and Data Structures","author":"A. Brodnik","year":"1999","unstructured":"Brodnik, A., Carlsson, S., Demaine, E.D., Munro, J.I., Sedgewick, R.: Resizable arrays in optimal time and space. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663, pp. 37\u201348. Springer, Heidelberg (1999)"},{"key":"43_CR3","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M. Dietzfelbinger","year":"1994","unstructured":"Dietzfelbinger, M., Karlin, A.R., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., Tarjan, R.E.: Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput.\u00a023, 738\u2013761 (1994)","journal-title":"SIAM J. Comput."},{"key":"43_CR4","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and indexing labeled trees, with applications. J. ACM\u00a057 (2009)","DOI":"10.1145\/1613676.1613680"},{"key":"43_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, 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"43_CR6","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. Theor. Comput. Sci.\u00a0372, 115\u2013121 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"43_CR7","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Saks, M.E.: The cell probe complexity of dynamic data structures. In: STOC, pp. 345\u2013354 (1989)","DOI":"10.1145\/73007.73040"},{"key":"43_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/978-3-540-73437-6_23","volume-title":"Combinatorial Pattern Matching","author":"R. Gonz\u00e1lez","year":"2007","unstructured":"Gonz\u00e1lez, R., Navarro, G.: Compressed text indexes with fast locate. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 216\u2013227. Springer, Heidelberg (2007)"},{"key":"43_CR9","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, Part I. LNCS, vol.\u00a06198, pp. 678\u2013689. Springer, Heidelberg (2010)"},{"key":"43_CR10","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R. Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Computing\u00a035, 378\u2013407 (2005)","journal-title":"SIAM J. Computing"},{"key":"43_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1007\/978-3-642-31594-7_43","volume-title":"Automata, Languages, and Programming","author":"J. Jansson","year":"2012","unstructured":"Jansson, J., Sadakane, K., Sung, W.-K.: CRAM: Compressed random access memory. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 510\u2013521. Springer, Heidelberg (2012)"},{"key":"43_CR12","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, 407\u2013430 (2001)","journal-title":"J. ACM"},{"key":"43_CR13","doi-asserted-by":"crossref","unstructured":"Navarro, G., Nekrich, Y.: Optimal dynamic sequence representations. In: Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2013)","DOI":"10.1137\/1.9781611973105.62"},{"key":"43_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/3-540-44985-X_4","volume-title":"Algorithm Theory - SWAT 2000","author":"R. Pagh","year":"2000","unstructured":"Pagh, R.: A new trade-off for deterministic dictionaries. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 22\u201331. Springer, Heidelberg (2000)"},{"key":"43_CR15","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R. Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms\u00a051, 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"key":"43_CR16","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M. P\u01cetra\u015fcu","year":"2006","unstructured":"P\u01cetra\u015fcu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput.\u00a035, 932\u2013963 (2006)","journal-title":"SIAM J. Comput."},{"key":"43_CR17","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Viola, E.: Cell-probe lower bounds for succinct partial sums. In: Charikar, M. (ed.) SODA, pp. 117\u2013122. SIAM (2010)","DOI":"10.1137\/1.9781611973075.11"},{"key":"43_CR18","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM TALG\u00a03 (2007)","DOI":"10.1145\/1290672.1290680"},{"key":"43_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/3-540-44634-6_39","volume-title":"Algorithms and Data Structures","author":"R. Raman","year":"2001","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct Dynamic Data Structures. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol.\u00a02125, pp. 426\u2013437. Springer, Heidelberg (2001)"},{"key":"43_CR20","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Grossi, R.: Squeezing succinct data structures into entropy bounds. In: SODA, pp. 1230\u20131239. ACM Press (2006)","DOI":"10.1145\/1109557.1109693"},{"key":"43_CR21","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: SODA, pp. 134\u2013149 (2010)","DOI":"10.1137\/1.9781611973075.13"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T09:32:56Z","timestamp":1557912776000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}