{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T10:10:02Z","timestamp":1746267002777,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_78","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"943-954","source":"Crossref","is-referenced-by-count":2,"title":["Pseudorandom Graphs in Data Structures"],"prefix":"10.1007","author":[{"given":"Omer","family":"Reingold","sequence":"first","affiliation":[]},{"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[]},{"given":"Udi","family":"Wieder","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"78_CR1","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Y. Azar","year":"1999","unstructured":"Azar, Y., Broder, A., Karlin, A., Upfal, E.: Balanced allocations. SIAM J. Computing\u00a029(1), 180\u2013200 (1999)","journal-title":"SIAM J. Computing"},{"key":"78_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-642-33090-2_11","volume-title":"Algorithms \u2013 ESA 2012","author":"M. Aum\u00fcller","year":"2012","unstructured":"Aum\u00fcller, M., Dietzfelbinger, M., Woelfel, P.: Explicit and efficient hash families suffice for cuckoo hashing with a stash. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol.\u00a07501, pp. 108\u2013120. Springer, Heidelberg (2012)"},{"issue":"3","key":"78_CR3","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1137\/120871626","volume":"42","author":"L.E. Celis","year":"2013","unstructured":"Celis, L.E., Reingold, O., Segev, G., Wieder, U.: Balls and bins: Smaller hash families and faster evaluation. SIAM J. Comput.\u00a042(3), 1030\u20131050 (2013)","journal-title":"SIAM J. Comput."},{"key":"78_CR4","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Woelfel, P.: Almost random graphs with simple hash functions. In: STOC, pp. 629\u2013638 (2003)","DOI":"10.1145\/780632.780634"},{"issue":"1-2","key":"78_CR5","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."},{"issue":"4","key":"78_CR6","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1137\/080728743","volume":"39","author":"A. Kirsch","year":"2009","unstructured":"Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: Cuckoo hashing with a stash. Siam J. Computing\u00a039(4), 1543\u20131561 (2009)","journal-title":"Siam J. Computing"},{"key":"78_CR7","doi-asserted-by":"crossref","unstructured":"Meka, R., Reingold, O., Rothblum, G.N., Rothblum, R.D.: Fast pseudorandomness for independence and load balancing (2013) (manuscript)","DOI":"10.1007\/978-3-662-43948-7_71"},{"key":"78_CR8","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Vadhan, S.: Why simple hash functions work: Exploiting the entropy in a data stream. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008,, pp. 746\u2013755 (2008)","DOI":"10.1137\/1.9780898716474"},{"issue":"3","key":"78_CR9","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1137\/110827831","volume":"53","author":"A. Pagh","year":"2011","unstructured":"Pagh, A., Pagh, R., Ruzic, M.: Linear probing with 5-wise independence. SIAM Review\u00a053(3), 547\u2013558 (2011)","journal-title":"SIAM Review"},{"issue":"2","key":"78_CR10","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. Journal of Algorithms\u00a051(2), 122\u2013144 (2004)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"78_CR11","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/2220357.2220361","volume":"59","author":"M. Patrascu","year":"2012","unstructured":"Patrascu, M., Thorup, M.: The power of simple tabulation hashing. J. ACM\u00a059(3), 14 (2012)","journal-title":"J. ACM"},{"issue":"3","key":"78_CR12","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 J. Comput.\u00a033(3), 505\u2013543 (2004)","journal-title":"SIAM J. Comput."},{"key":"78_CR13","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Simple tabulation, fast expanders, double tabulation, and high independence. In: FOCS, pp. 90\u201399 (2013)","DOI":"10.1109\/FOCS.2013.18"},{"issue":"4","key":"78_CR14","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1145\/792538.792546","volume":"50","author":"B. V\u00f6cking","year":"2003","unstructured":"V\u00f6cking, B.: How asymmetry helps load balancing. J. ACM\u00a050(4), 568\u2013589 (2003)","journal-title":"J. ACM"},{"key":"78_CR15","doi-asserted-by":"crossref","unstructured":"Woelfel, P.: Asymmetric balanced allocation with simple hash functions. In: SODA, pp. 424\u2013433 (2006)","DOI":"10.1145\/1109557.1109605"}],"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-662-43948-7_78","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:31:05Z","timestamp":1746264665000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_78"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_78","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}