{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T21:55:28Z","timestamp":1777154128990,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540705826","type":"print"},{"value":"9783540705833","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70583-3_51","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"631-642","source":"Crossref","is-referenced-by-count":18,"title":["History-Independent Cuckoo Hashing"],"prefix":"10.1007","author":[{"given":"Moni","family":"Naor","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gil","family":"Segev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Udi","family":"Wieder","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4-5","key":"51_CR1","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/BF01940874","volume":"16","author":"N. Alon","year":"1996","unstructured":"Alon, N., Naor, M.: Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica\u00a016(4-5), 434\u2013449 (1996)","journal-title":"Algorithmica"},{"key":"51_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-48658-5_22","volume-title":"Advances in Cryptology - CRYPTO 1994","author":"M. Bellare","year":"1994","unstructured":"Bellare, M., Goldreich, O., Goldwasser, S.: Incremental Cryptography: The Case of Hashing and Signing. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol.\u00a0839, pp. 216\u2013233. Springer, Heidelberg (1994)"},{"key":"51_CR3","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldreich, O., Goldwasser, S.: Incremental cryptography and application to virus protection. In: 27th STOC, pp. 45\u201356 (1995)","DOI":"10.1145\/225058.225080"},{"key":"51_CR4","unstructured":"Bethencourt, J., Boneh, D., Waters, B.: Cryptographic methods for storing ballots on a voting machine. In: 14th NDSS, pp. 209\u2013222 (2007)"},{"key":"51_CR5","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Golovin, D.: Strongly history-independent hashing with applications. In: 48th FOCS, pp. 272\u2013282 (2007)","DOI":"10.1109\/FOCS.2007.36"},{"issue":"2","key":"51_CR6","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/j.ic.2005.11.001","volume":"204","author":"N. Buchbinder","year":"2006","unstructured":"Buchbinder, N., Petrank, E.: Lower and upper bounds on obtaining history-independence. Inf. Comput.\u00a0204(2), 291\u2013337 (2006)","journal-title":"Inf. Comput."},{"issue":"4","key":"51_CR7","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., auf der Heide, F.M., Rohnert, H., Tarjan, R.E.: Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput.\u00a023(4), 738\u2013761 (1994)","journal-title":"SIAM J. Comput."},{"issue":"1-2","key":"51_CR8","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2007.02.054","volume":"380","author":"M. Dietzfelbinger","year":"2007","unstructured":"Dietzfelbinger, M., Weidling, C.: Balanced allocation and dictionaries with tightly packed constant size bins. Theor. Comput. Sci.\u00a0380(1-2), 47\u201368 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"51_CR9","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Woelfel, P.: Almost random graphs with simple hash functions. In: 35th STOC, pp. 629\u2013638 (2003)","DOI":"10.1145\/780542.780634"},{"key":"51_CR10","unstructured":"Erlingsson, \u00da., Manasse, M., McSherry, F.: A cool and practical alternative to traditional hash tables. In: 7th Workshop on Distributed Data and Structures (2006)"},{"issue":"2","key":"51_CR11","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s00224-004-1195-x","volume":"38","author":"D. Fotakis","year":"2005","unstructured":"Fotakis, D., Pagh, R., Sanders, P., Spirakis, P.G.: Space efficient hash tables with worst case constant access time. Theor. Comput. Sys.\u00a038(2), 229\u2013248 (2005)","journal-title":"Theor. Comput. Sys."},{"issue":"3","key":"51_CR12","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 O(1) worst case access time. J. ACM\u00a031(3), 538\u2013544 (1984)","journal-title":"J. ACM"},{"issue":"1","key":"51_CR13","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1171","volume":"41","author":"T. Hagerup","year":"2001","unstructured":"Hagerup, T., Miltersen, P.B., Pagh, R.: Deterministic dictionaries. J. Algorithms\u00a041(1), 69\u201385 (2001)","journal-title":"J. Algorithms"},{"issue":"1","key":"51_CR14","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s00453-004-1140-z","volume":"42","author":"J.D. Hartline","year":"2005","unstructured":"Hartline, J.D., Hong, E.S., Mohr, A.E., Pentney, W.R., Rocke, E.: Characterizing history independent data structures. Algorithmica\u00a042(1), 57\u201374 (2005)","journal-title":"Algorithmica"},{"key":"51_CR15","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., \u0141uczak, T., Ruci\u0144ski, A.: Random Graphs. Wiley-Interscience, Chichester (2000)"},{"key":"51_CR16","doi-asserted-by":"crossref","unstructured":"Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: Cuckoo hashing with a stash (manuscript, 2008)","DOI":"10.1007\/978-3-540-87744-8_51"},{"key":"51_CR17","doi-asserted-by":"crossref","unstructured":"Kutzelnigg, R.: Bipartite random graphs and cuckoo hashing. In: 4th Colloquium on Mathematics and Computer Science, pp. 403\u2013406 (2006)","DOI":"10.46298\/dmtcs.3486"},{"key":"51_CR18","doi-asserted-by":"crossref","unstructured":"Micciancio, D.: Oblivious data structures: Applications to cryptography. In: 29th STOC, pp. 456\u2013464 (1997)","DOI":"10.1145\/258533.258638"},{"key":"51_CR19","doi-asserted-by":"crossref","unstructured":"Miltersen, P.B.: Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries. In: 9th SODA, pp. 556\u2013563 (1998)","DOI":"10.7146\/brics.v4i17.18813"},{"key":"51_CR20","unstructured":"Mitzenmacher, M., Vadhan, S.: Why simple hash functions work: Exploiting the entropy in a data stream. In: 19th SODA, pp. 746\u2013755 (2008)"},{"key":"51_CR21","doi-asserted-by":"crossref","unstructured":"Molnar, D., Kohno, T., Sastry, N., Wagner, D.: Tamper-evident, history-independent, subliminal-free data structures on PROM storage -or- How to store ballots on a voting machine. In: IEEE S&P, pp. 365\u2013370 (2006)","DOI":"10.1109\/SP.2006.39"},{"key":"51_CR22","doi-asserted-by":"crossref","unstructured":"Moran, T., Naor, M., Segev, G.: Deterministic history-independent strategies for storing information on write-once memories. In: 34th ICALP, pp. 303\u2013315 (2007)","DOI":"10.1007\/978-3-540-73420-8_28"},{"key":"51_CR23","doi-asserted-by":"crossref","unstructured":"Naor, M., Teague, V.: Anti-persistence: History independent data structures. In: 33rd STOC, pp. 492\u2013501 (2001)","DOI":"10.1145\/380752.380844"},{"key":"51_CR24","doi-asserted-by":"crossref","unstructured":"Ostlin, A., Pagh, R.: Uniform hashing in constant time and linear space. In: 35th STOC, pp. 622\u2013628 (2003)","DOI":"10.1145\/780542.780633"},{"issue":"2","key":"51_CR25","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. of Algorithms\u00a051(2), 122\u2013144 (2004)","journal-title":"J. of Algorithms"},{"key":"51_CR26","unstructured":"Panigrahy, R.: Efficient hashing with lookups in two memory accesses. In: 16th SODA, pp. 830\u2013839 (2005)"},{"key":"51_CR27","doi-asserted-by":"crossref","unstructured":"Ross, K.A.: Efficient hash probes on modern processors. In: 23nd International Conference on Data Engineering, pp. 1297\u20131301 (2007)","DOI":"10.1109\/ICDE.2007.368997"},{"key":"51_CR28","doi-asserted-by":"crossref","unstructured":"Siegel, A.: On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In: 30th FOCS, pp. 20\u201325 (1989)","DOI":"10.1109\/SFCS.1989.63450"},{"key":"51_CR29","doi-asserted-by":"crossref","unstructured":"Zukowski, M., H\u00e9man, S., Boncz, P.A.: Architecture conscious hashing. In: 2nd International Workshop on Data Management on New Hardware, vol.\u00a06 (2006)","DOI":"10.1145\/1140402.1140410"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70583-3_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:13:37Z","timestamp":1738325617000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70583-3_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540705826","9783540705833"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70583-3_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}