{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:04:57Z","timestamp":1750694697854},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_60","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:16:36Z","timestamp":1252952196000},"page":"671-681","source":"Crossref","is-referenced-by-count":9,"title":["3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit"],"prefix":"10.1007","author":[{"given":"Eric","family":"Lehman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rina","family":"Panigrahy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"60_CR1","doi-asserted-by":"crossref","unstructured":"Adler, M., Chakrabarti, S., Mitzenmacher, M., Rasmussen, L.: Parallel randomized load balancing. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, May 1995, pp. 238\u2013247 (1995)","DOI":"10.1145\/225058.225131"},{"key":"#cr-split#-60_CR2.1","doi-asserted-by":"crossref","unstructured":"Azar, Y., Broder, A.Z., Karlin, A.R., Upfal, E.: Balanced allocations. SIAM Journal on Computing??29, 180???200 (1999);","DOI":"10.1137\/S0097539795288490"},{"key":"#cr-split#-60_CR2.2","unstructured":"A preliminary version of this paper appeared in Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing (1994)"},{"issue":"1","key":"60_CR3","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1006\/jctb.1996.0036","volume":"67","author":"S. Spencer","year":"1996","unstructured":"Spencer, S., Pittel, B., Wormald, N.: Sudden emergence of a giant k-core in a random graph. J. Combin. Theory Ser. B\u00a067(1), 111\u2013151 (1996)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"6","key":"60_CR4","doi-asserted-by":"publisher","first-page":"1350","DOI":"10.1137\/S009753970444435X","volume":"35","author":"P. Berenbrink","year":"2006","unstructured":"Berenbrink, P., Czumaj, A., Steger, A., V\u00f6cking, B.: Balanced allocations: The heavily loaded case. SIAM J. Comput.\u00a035(6), 1350\u20131385 (2006)","journal-title":"SIAM J. Comput."},{"key":"60_CR5","doi-asserted-by":"crossref","unstructured":"Broder, A., Mitzenmacher, M.: Using multiple hash functions to improve ip lookups. In: Proceedings of IEEE INFOCOM 2001, pp. 1454\u20131463 (2001)","DOI":"10.1109\/INFCOM.2001.916641"},{"key":"60_CR6","unstructured":"Cain, J.A., Sanders, P., Wormald, N.: The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation. In: SODA 2007: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 469\u2013476 (2007)"},{"key":"60_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/3-540-60313-1_133","volume-title":"Shared memory simulations with triple-logarithmic delay","author":"A. Czumaj","year":"1995","unstructured":"Czumaj, A., Meyer auf der Heide, F., Stemann, V.: Shared memory simulations with triple-logarithmic delay. LNCS, vol.\u00a0979, pp. 46\u201359. Springer, Heidelberg (1995)"},{"key":"60_CR8","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Meyer auf der Heide, F.: Simple efficient shared memory simulations. In: Proc. of the 5th SPAA, pp. 110\u2013119 (1993)","DOI":"10.1145\/165231.165246"},{"key":"60_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":"60_CR10","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., Meyer auf der Heide, F.: 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":"60_CR11","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., Meyer auf der Heide, F., 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."},{"key":"60_CR12","doi-asserted-by":"crossref","unstructured":"Fotakis, P.S.D., Pagh, R., Spirakis, P.: Space efficient hash tables with worst case constant access time. In: 20th Annual Symposium on Theoretical Aspects of Computer Science (2003)","DOI":"10.1007\/3-540-36494-3_25"},{"issue":"2","key":"60_CR13","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0304-3975(96)00032-1","volume":"162","author":"C. Scheideler","year":"1996","unstructured":"Scheideler, C., Meyer auf der Heide, F., Stemann, V.: Exploiting storage redundancy to speed up randomized shared memory simulations. Theoretical Computer Science\u00a0162(2), 245\u2013281 (1996); Preliminary version in Proc. of the 12th STACS, pp. 267\u2013278 (1995)","journal-title":"Theoretical Computer Science"},{"key":"60_CR14","unstructured":"Fernholz, D., Ramachandran, V.: The k-orientability thresholds for gn, p. In: SODA 2007: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 459\u2013468. Society for Industrial and Applied Mathematics (2007)"},{"issue":"3","key":"60_CR15","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Komlos, J., Szemeredi, E.: Storing a sparse table with o(1) worst case access time. J. Assoc. Comput. Mach.\u00a031(3), 538\u2013544 (1984)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1-2","key":"60_CR16","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1002\/rsa.20147","volume":"30","author":"S. Janson","year":"2007","unstructured":"Janson, S., Luczak, M.J.: A simple solution to the k-core problem. Random Struct. Algorithms\u00a030(1-2), 50\u201362 (2007)","journal-title":"Random Struct. Algorithms"},{"key":"60_CR17","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1145\/1109557.1109606","volume-title":"SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm","author":"K. Kenthapadi","year":"2006","unstructured":"Kenthapadi, K., Panigrahy, R.: Balanced allocation on graphs. In: SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 434\u2013443. ACM, New York (2006)"},{"key":"60_CR18","unstructured":"Kirsch, A., Mitzenmacher, M.: Using a queue to de-amortize cuckoo hashing in hardware. In: 45th Allerton Conference on Communication, Control, and Computing, pp. 751\u2013758 (2007)"},{"key":"60_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/978-3-540-87744-8_51","volume-title":"Algorithms - ESA 2008","author":"A. Kirsch","year":"2008","unstructured":"Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: Cuckoo hashing with a stash. In: Halperin, D., Mehlhorn, K. (eds.) Esa 2008. LNCS, vol.\u00a05193, pp. 611\u2013622. Springer, Heidelberg (2008)"},{"key":"#cr-split#-60_CR20.1","doi-asserted-by":"crossref","unstructured":"Pagh, R., Rodler, F.: Cuckoo hashing. Journal of Algorithms??51, 122???144 (2004);","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"#cr-split#-60_CR20.2","unstructured":"A preliminary version appeared in proceedings of the 9th Annual European Symposium on Algorithms, pp. 121???133 (2001)"},{"key":"60_CR21","unstructured":"Panigrahy, R.: Efficient hashing with lookups in two memory accesses. In: SODA 2005: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 830\u2013839. Society for Industrial and Applied Mathematics (2005)"},{"issue":"1","key":"60_CR22","first-page":"21","volume":"35","author":"H. Jan","year":"2003","unstructured":"Jan, H., Korst Peter Sanders, M., Egner, S.: Fast concurrent access to parallel disks. Algorithmica\u00a035(1), 21\u201355 (2003); A Preliminary version appeared in SODA 2000","journal-title":"Algorithmica"},{"key":"60_CR23","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1145\/1250790.1250829","volume-title":"STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing","author":"K. Talwar","year":"2007","unstructured":"Talwar, K., Wieder, U.: Balanced allocations: the weighted case. In: STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 256\u2013265. ACM, New York (2007)"},{"issue":"4","key":"60_CR24","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":"60_CR25","doi-asserted-by":"crossref","unstructured":"Arbitman, M.N.Y., Segev, G.: De-amortized cuckoo hashing: Provable worst-case performance and experimental results (2009)","DOI":"10.1007\/978-3-642-02927-1_11"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_60","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:22:16Z","timestamp":1558538536000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_60"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_60","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}