{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T05:15:47Z","timestamp":1724303747548},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,7,31]]},"abstract":"\n We consider a natural variation of cuckoo hashing proposed by Lehman and Panigrahy (2009). Each of\n cn<\/jats:italic>\n objects is assigned\n k<\/jats:italic>\n = 2 intervals of size \u2113 in a linear hash table of size\n n<\/jats:italic>\n and both starting points are chosen independently and uniformly at random. Each object must be placed into a table cell within its intervals, but each cell can only hold one object. Experiments suggested that this scheme outperforms the variant with\n blocks<\/jats:italic>\n in which intervals are aligned at multiples of \u2113. In particular, the\n load threshold<\/jats:italic>\n is higher, i.e., the load\n c<\/jats:italic>\n that can be achieved with high probability. For instance, Lehman and Panigrahy (2009) empirically observed the threshold for \u2113 = 2 to be around 96.5% as compared to roughly 89.7% using blocks. They pinned down the asymptotics of the thresholds for large \u2113, but the precise values resisted rigorous analysis.\n <\/jats:p>\n \n We establish a method to determine these load thresholds for all \u2113 \u2265 2, and, in fact, for general\n k<\/jats:italic>\n \u2265 2. For instance, for\n k<\/jats:italic>\n = \u2113 = 2, we get \u2248 96.4995%. We employ a theorem due to Leconte, Lelarge, and Massouli\u00e9 (2013), which adapts methods from statistical physics to the world of hypergraph orientability. In effect, the orientability thresholds for our graph families are determined by belief propagation equations for certain graph limits. As a side note, we provide experimental evidence suggesting that placements can be constructed in linear time using an adapted version of an algorithm by Khosla (2013).\n <\/jats:p>","DOI":"10.1145\/3589558","type":"journal-article","created":{"date-parts":[[2023,3,31]],"date-time":"2023-03-31T11:34:57Z","timestamp":1680262497000},"page":"1-22","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Load Thresholds for Cuckoo Hashing with Overlapping Blocks"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-6477-0106","authenticated-orcid":false,"given":"Stefan","family":"Walzer","sequence":"first","affiliation":[{"name":"Universit\u00e4t zu K\u00f6ln, Cologne, North Rhine-Westphalia, Germany"}]}],"member":"320","published-online":{"date-parts":[[2023,5,5]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-09444-0_1"},{"key":"e_1_3_2_3_2","volume-title":"Analysis of the Linear Probing Variant of Cuckoo Hashing","author":"Beyer Stephan","year":"2012","unstructured":"Stephan Beyer. 2012. Analysis of the Linear Probing Variant of Cuckoo Hashing. Master\u2019s Thesis. Technische Universit\u00e4t Ilmenau. Retrieved from http:\/\/gso.gbv.de\/DB=2.1\/PPNSET?PPN=685166759."},{"key":"e_1_3_2_4_2","first-page":"469","volume-title":"Proceedings of the 18th SODA","author":"Cain Julie Anne","year":"2007","unstructured":"Julie Anne Cain, Peter Sanders, and Nicholas C. Wormald. 2007. The random graph threshold for \\(k\\) -orientiability and a fast algorithm for optimal multiple-choice allocation. In Proceedings of the 18th SODA. 469\u2013476. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283433."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_19"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_14"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"e_1_3_2_8_2","first-page":"459","volume-title":"Proceedings of the 18th SODA","author":"Fernholz Daniel","year":"2007","unstructured":"Daniel Fernholz and Vijaya Ramachandran. 2007. The \\(k\\) -orientability Thresholds for \\(G_{n,p}\\) . In Proceedings of the 18th SODA. 459\u2013468. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283432."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1195-x"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.93"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_30"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20426"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20427"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806705"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20147"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_51"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00595-4"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2013.6736515"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.3"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_60"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.23"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SWAT.2018.29"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20061"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2012.41"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589558","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T12:56:08Z","timestamp":1683291368000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589558"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,5]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3589558"],"URL":"https:\/\/doi.org\/10.1145\/3589558","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,5]]},"assertion":[{"value":"2018-10-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-07","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}