{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T09:30:48Z","timestamp":1775899848357,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642157745","type":"print"},{"value":"9783642157752","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15775-2_37","type":"book-chapter","created":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T14:47:32Z","timestamp":1283352452000},"page":"427-438","source":"Crossref","is-referenced-by-count":25,"title":["Fast Prefix Search in Little Space, with Applications"],"prefix":"10.1007","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[]},{"given":"Paolo","family":"Boldi","sequence":"additional","affiliation":[]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[]},{"given":"Sebastiano","family":"Vigna","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"37_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Optimal static range reporting in one dimension. In: STOC 2001, pp. 476\u2013482 (2001)","DOI":"10.1145\/380752.380842"},{"key":"37_CR2","first-page":"785","volume-title":"SODA 2009","author":"D. Belazzougui","year":"2009","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monotone minimal perfect hashing: Searching a sorted table with O(1) accesses. In: SODA 2009, pp. 785\u2013794. ACM Press, New York (2009)"},{"key":"37_CR3","volume-title":"ALENEX 2009","author":"D. Belazzougui","year":"2009","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Theory and practise of monotone minimal perfect hashing. In: ALENEX 2009. SIAM, Philadelphia (2009)"},{"key":"37_CR4","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1145\/1142351.1142385","volume-title":"PODS 2006","author":"M.A. Bender","year":"2006","unstructured":"Bender, M.A., Farach-Colton, M., Kuszmaul, B.C.: Cache-oblivious string B-trees. In: PODS 2006, pp. 233\u2013242. ACM, New York (2006)"},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R.: Cache-oblivious string dictionaries. In: SODA 2006, pp. 581\u2013590 (2006)","DOI":"10.1145\/1109557.1109621"},{"key":"37_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/3-540-55719-9_77","volume-title":"Automata, Languages and Programming","author":"M. Dietzfelbinger","year":"1992","unstructured":"Dietzfelbinger, M., Gil, J., Matias, Y., Pippenger, N.: Polynomial hash functions are reliable (extended abstract). In: Kuich, W. (ed.) ICALP 1992. LNCS, vol.\u00a0623, pp. 235\u2013246. Springer, Heidelberg (1992)"},{"key":"37_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-540-70575-8_32","volume-title":"Automata, Languages and Programming","author":"M. Dietzfelbinger","year":"2008","unstructured":"Dietzfelbinger, M., Pagh, R.: Succinct data structures for retrieval and approximate membership (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 385\u2013396. Springer, Heidelberg (2008)"},{"issue":"2","key":"37_CR8","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P. Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. J. Assoc. Comput. Mach.\u00a021(2), 246\u2013260 (1974)","journal-title":"J. Assoc. Comput. Mach."},{"key":"37_CR9","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","volume":"21","author":"P. Elias","year":"1975","unstructured":"Elias, P.: Universal codeword sets and representations of the integers. IEEE Trans.\u00a0on Info.\u00a0Theory\u00a021, 194\u2013203 (1975)","journal-title":"IEEE Trans.\u00a0on Info.\u00a0Theory"},{"issue":"2","key":"37_CR10","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/301970.301973","volume":"46","author":"P. Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The string B-tree: a new data structure for string search in external memory and its applications. Journal of the ACM\u00a046(2), 236\u2013280 (1999)","journal-title":"Journal of the ACM"},{"key":"37_CR11","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Grossi, R., Gupta, A., Shah, R., Vitter, J.S.: On searching compressed string collections cache-obliviously. In: PODS 2008, pp. 181\u2013190 (2008)","DOI":"10.1145\/1376916.1376943"},{"key":"37_CR12","first-page":"285","volume-title":"FOCS 1999","author":"M. Frigo","year":"1999","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: FOCS 1999, pp. 285\u2013297. IEEE Comput. Soc. Press, Los Alamitos (1999)"},{"issue":"3","key":"37_CR13","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/j.tcs.2007.07.042","volume":"387","author":"A. Gupta","year":"2007","unstructured":"Gupta, A., Hon, W.-K., Shah, R., Vitter, J.S.: Compressed data structures: Dictionaries and data-aware measures. Theor. Comput. Sci.\u00a0387(3), 313\u2013331 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"37_CR14","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: FOCS 1989, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"37_CR15","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Randomization does not help searching predecessors. In: SODA 2007, pp. 555\u2013564 (2007)"},{"key":"37_CR16","first-page":"233","volume-title":"SODA 2002","author":"R. Raman","year":"2002","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: SODA 2002, pp. 233\u2013242. ACM Press, New York (2002)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15775-2_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,19]],"date-time":"2019-03-19T20:12:41Z","timestamp":1553026361000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15775-2_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642157745","9783642157752"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15775-2_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}