{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T19:54:59Z","timestamp":1773258899434,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540327554","type":"print"},{"value":"9783540327561","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"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":[[2006]]},"DOI":"10.1007\/11682462_34","type":"book-chapter","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T11:50:30Z","timestamp":1140177030000},"page":"349-361","source":"Crossref","is-referenced-by-count":20,"title":["De Dictionariis Dynamicis Pauco Spatio Utentibus"],"prefix":"10.1007","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[]},{"given":"Friedhelm Meyer auf","family":"der Heide","sequence":"additional","affiliation":[]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[]},{"given":"Mihai","family":"P\u01cetra\u015fcu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G., Rauhe, T.: Optimal static range reporting in one dimension. In: STOC 2001, pp. 476\u2013482 (2001)","DOI":"10.1145\/380752.380842"},{"issue":"5","key":"34_CR2","doi-asserted-by":"publisher","first-page":"1627","DOI":"10.1137\/S0097539795294165","volume":"28","author":"A. Brodnik","year":"1999","unstructured":"Brodnik, A., Munro, J.I.: Membership in constant time and almostminimum space. SIAM J. Computing\u00a028(5), 1627\u20131640 (1999); See also ESA 1994","journal-title":"SIAM J. Computing"},{"key":"34_CR3","unstructured":"Chazelle, B., Kilian, J., Rubinfeld, R., Tal, A.: The Bloomier filter: an efficient data structure for static support lookup tables. In: SODA 2004 (2004)"},{"key":"34_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/BFb0032018","volume-title":"Automata, Languages and Programming","author":"M. Dietzfelbinger","year":"1990","unstructured":"Dietzfelbinger, M.: A new universal class of hash functions and dynamic hashing in real time. In: Paterson, M. (ed.) ICALP 1990. LNCS, vol.\u00a0443, pp. 6\u201319. Springer, Heidelberg (1990)"},{"issue":"4","key":"34_CR5","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M. Dietzfelbinger","year":"1994","unstructured":"Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Auf Der Heide, F.M., Rohnert, H., Tarjan, R.E.: Dynamic perfect hashing: Upper and lower bounds. SIAM J. Computing\u00a023(4), 738\u2013761 (1994); See also FOCS 1988","journal-title":"SIAM J. Computing"},{"issue":"1","key":"34_CR6","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1137\/0605009","volume":"5","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J.: On the size of separating systems and families of perfect hash functions. SIAM J. Algebraic and Discrete Methods\u00a05(1), 61\u201368 (1984)","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"issue":"3","key":"34_CR7","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with 0(1) worst case access time. JACM\u00a031(3), 538\u2013544 (1984); See also FOCS 1982","journal-title":"JACM"},{"key":"34_CR8","doi-asserted-by":"crossref","unstructured":"Hagerup, T., Tholey, T.: Efficient minimal perfect hashing in nearly minimal space. In: STACS 2001, pp. 317\u2013326 (2001)","DOI":"10.1007\/3-540-44693-1_28"},{"key":"34_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/11538462_30","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"E. Kaplan","year":"2005","unstructured":"Kaplan, E., Naor, M., Reingold, O.: Derandomized constructions of k-wise (almost) independent permutations. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 354\u2013365. Springer, Heidelberg (2005)"},{"key":"34_CR10","doi-asserted-by":"crossref","unstructured":"Mortensen, C.W., Pagh, R., P\u01cetra\u015fcu, M.: On dynamic range reporting in one dimension. In: STOC 2005, pp. 104\u2013111 (2005)","DOI":"10.1145\/1060590.1060606"},{"issue":"2","key":"34_CR11","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1137\/S0097539700369909","volume":"31","author":"R. Pagh","year":"2001","unstructured":"Pagh, R.: Low redundancy in static dictionaries with constant query time. SIAM Journal on Computing\u00a031(2), 353\u2013363 (2001); Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.): ICALP 1999. LNCS, vol.\u00a01644, pp. 353\u2013363. Springer, Heidelberg (1999)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR12","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: SODA 2002 (2002)"},{"key":"34_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/3-540-45061-0_30","volume-title":"Automata, Languages and Programming","author":"R. Raman","year":"2003","unstructured":"Raman, R., Rao, S.S.: Succinct dynamic dictionaries and trees. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 357\u2013368. Springer, Heidelberg (2003)"},{"issue":"3","key":"34_CR14","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/S0097539701386216","volume":"33","author":"A. Siegel","year":"2004","unstructured":"Siegel, A.: On universal classes of extremely random constant-time hash functions. SIAM Journal on Computing\u00a033(3), 505\u2013543 (2004)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","LATIN 2006: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11682462_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T00:18:27Z","timestamp":1555460307000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11682462_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540327554","9783540327561"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11682462_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}