{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T09:34:24Z","timestamp":1725701664113},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_11","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T11:29:11Z","timestamp":1346153351000},"page":"108-120","source":"Crossref","is-referenced-by-count":5,"title":["Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash"],"prefix":"10.1007","author":[{"given":"Martin","family":"Aum\u00fcller","sequence":"first","affiliation":[]},{"given":"Martin","family":"Dietzfelbinger","sequence":"additional","affiliation":[]},{"given":"Philipp","family":"Woelfel","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Aum\u00fcller, M., Dietzfelbinger, M., Woelfel, P.: Explicit and efficient hash families suffice for cuckoo hashing with a stash. CoRR abs\/1204.4431 (2012)","DOI":"10.1007\/978-3-642-33090-2_11"},{"issue":"3","key":"11_CR2","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1017\/S0963548397003040","volume":"6","author":"N.J. Calkin","year":"1997","unstructured":"Calkin, N.J.: Dependent sets of constant weight binary vectors. Combinatorics, Probability and Computing\u00a06(3), 263\u2013271 (1997)","journal-title":"Combinatorics, Probability and Computing"},{"issue":"2","key":"11_CR3","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"L. Carter","year":"1979","unstructured":"Carter, L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci.\u00a018(2), 143\u2013154 (1979)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"11_CR4","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0020-0190(02)00500-8","volume":"86","author":"L. Devroye","year":"2003","unstructured":"Devroye, L., Morin, P.: Cuckoo hashing: Further analysis. Inf. Process. Lett.\u00a086(4), 215\u2013219 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"11_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1006\/jagm.1997.0873","volume":"25","author":"M. Dietzfelbinger","year":"1997","unstructured":"Dietzfelbinger, M., Hagerup, T., Katajainen, J., Penttonen, M.: A reliable randomized algorithm for the closest-pair problem. J. Algorithms\u00a025(1), 19\u201351 (1997)","journal-title":"J. Algorithms"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/978-3-642-02927-1_30","volume-title":"Automata, Languages and Programming","author":"M. Dietzfelbinger","year":"2009","unstructured":"Dietzfelbinger, M., Rink, M.: Applications of a Splitting Trick. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 354\u2013365. Springer, Heidelberg (2009)"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Schellbach, U.: On risks of using cuckoo hashing with simple universal hash classes. In: 20th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 795\u2013804 (2009)","DOI":"10.1137\/1.9781611973068.87"},{"issue":"1-2","key":"11_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":"11_CR9","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Woelfel, P.: Almost random graphs with simple hash functions. In: Proc. 35th ACM Symp. on Theory of Computing (STOC), New York, NY, USA, pp. 629\u2013638 (2003)","DOI":"10.1145\/780632.780634"},{"issue":"2","key":"11_CR10","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. Theory Comput. Syst.\u00a038(2), 229\u2013248 (2005)","journal-title":"Theory Comput. Syst."},{"key":"11_CR11","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)"},{"issue":"4","key":"11_CR12","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. Comput.\u00a039(4), 1543\u20131561 (2009)","journal-title":"SIAM J. Comput."},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1007\/978-3-642-29344-3_43","volume-title":"LATIN 2012: Theoretical Informatics","author":"T.Q. Klassen","year":"2012","unstructured":"Klassen, T.Q., Woelfel, P.: Independence of Tabulation-Based Hash Classes. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol.\u00a07256, pp. 506\u2013517. Springer, Heidelberg (2012)"},{"issue":"3","key":"11_CR14","first-page":"81","volume":"12","author":"R. Kutzelnigg","year":"2010","unstructured":"Kutzelnigg, R.: A further analysis of cuckoo hashing with a stash and random graphs of excess r. Discr. Math. and Theoret. Comput. Sci.\u00a012(3), 81\u2013102 (2010)","journal-title":"Discr. Math. and Theoret. Comput. Sci."},{"key":"11_CR15","unstructured":"Mitzenmacher, M., Vadhan, S.P.: Why simple hash functions work: exploiting the entropy in a data stream. In: Proc. 19th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 746\u2013755 (2008)"},{"issue":"1","key":"11_CR16","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1137\/060658400","volume":"38","author":"A. Pagh","year":"2008","unstructured":"Pagh, A., Pagh, R.: Uniform hashing in constant time and optimal space. SIAM J. Comput.\u00a038(1), 85\u201396 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"11_CR17","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. Algorithms\u00a051(2), 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: The power of simple tabulation hashing. In: Proc. 43rd ACM Symp. on Theory of Computing (STOC), pp. 1\u201310 (2011)","DOI":"10.1145\/1993636.1993638"},{"issue":"3","key":"11_CR19","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":"11_CR20","unstructured":"Thorup, M., Zhang, Y.: Tabulation based 4-universal hashing with applications to second moment estimation. In: Proc. 15th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 615\u2013624 (2004)"},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zhang, Y.: Tabulation based 5-universal hashing and linear probing. In: Proc. 12th ALENEX, pp. 62\u201376. SIAM (2010)","DOI":"10.1137\/1.9781611972900.7"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Wegman, M.N., Carter, L.: New classes and applications of hash functions. In: Proc. 20th Ann. Symp. on Foundations of Computer Science (FOCS), pp. 175\u2013182. IEEE Computer Society (1979)","DOI":"10.1109\/SFCS.1979.26"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Woelfel, P.: Asymmetric balanced allocation with simple hash functions. In: Proc. 17th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 424\u2013433 (2006)","DOI":"10.1145\/1109557.1109605"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T07:54:43Z","timestamp":1620114883000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}