{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T13:36:38Z","timestamp":1770903398953,"version":"3.50.1"},"reference-count":69,"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":[[2025,7,31]]},"abstract":"\n In multiple-choice data structures each element\n \n \\(x\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in a set\n \n \\(S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of\n \n \\(m\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n keys<\/jats:italic>\n is associated with a random set\n \n \\(e(x) \\subseteq [n]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of\n buckets<\/jats:italic>\n with capacity\n \n \\(\\ell\\geq 1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n by hash functions. This setting is captured by the hypergraph\n \n \\(H=([n],\\{e(x)\\mid x \\in S\\})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Accommodating each key in an associated bucket amounts to finding an\n \n \\(\\ell\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -orientation<\/jats:italic>\n of\n \n \\(H\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n assigning to each hyperedge an incident vertex such that each vertex is assigned at most\n \n \\(\\ell\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n hyperedges. If each subhypergraph of\n \n \\(H\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n has minimum degree at most\n \n \\(\\ell\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , then an\n \n \\(\\ell\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -orientation can be found greedily and\n \n \\(H\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is called\n \n \\(\\ell\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -peelable<\/jats:italic>\n . Peelability has a central role in invertible Bloom lookup tables and can speed up the construction of retrieval data structures, perfect hash functions, and cuckoo hash tables.\n <\/jats:p>\n \n Many hypergraphs exhibit sharp density thresholds with respect to\n \n \\(\\ell\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -orientability and\n \n \\(\\ell\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -peelability, i.e., as the density\n \n \\(c=\\frac{m}{n}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n grows past a critical value, the probability of these properties drops from almost\n \n \\(1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n to almost\n \n \\(0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . In fully random\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -uniform hypergraphs the thresholds\n \n \\(c_{\\smash{k,\\ell}}^{*}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for\n \n \\(\\ell\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -orientability significantly exceed the thresholds for\n \n \\(\\ell\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -peelability. In this article, for every\n \n \\(k\\geq 2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(\\ell\\geq 1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n with\n \n \\((k,\\ell)\\neq(2,1)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and every\n \n \\(z>0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , we construct a new family of random\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -uniform hypergraphs with i.i.d. random hyperedges such that\n both<\/jats:italic>\n the\n \n \\(\\ell\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -peelability and the\n \n \\(\\ell\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -orientability thresholds approach\n \n \\(c_{\\smash{k,\\ell}}^{*}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n as\n \n \\(z \\rightarrow \\infty \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . In particular, we achieve\n \n \\(1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -peelability at densities arbitrarily close to\n \n \\(1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , extending the reach of greedy algorithms.\n <\/jats:p>\n \n Our construction is simple: The\n \n \\(n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n vertices are linearly ordered and each hyperedge selects its\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n elements uniformly at random from a random range of\n \n \\(\\frac{n}{z+1}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n consecutive vertices. We thus exploit the phenomenon of\n threshold saturation<\/jats:italic>\n via<\/jats:italic>\n spatial coupling<\/jats:italic>\n discovered in the context of low-density parity-check codes. Once the connection to data structures is in plain sight, a framework by Kudekar, Richardson and Urbanke does the heavy lifting in our proof.\n <\/jats:p>\n \n We demonstrate the usefulness of our construction using our hypergraphs as a drop-in replacement in a retrieval data structure by Botelho et al. This reduces memory usage from\n \n \\(\\approx 1.23m\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits to\n \n \\(\\approx 1.12m\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits (for input size\n \n \\(m\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ). Using\n \n \\(k>3\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n attains, at small sacrifices in running time, further improvements to memory usage.\n <\/jats:p>","DOI":"10.1145\/3711822","type":"journal-article","created":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T11:03:34Z","timestamp":1736420614000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Peeling Close to the Orientability Threshold Spatial Coupling in Hashing-Based Data Structures"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6477-0106","authenticated-orcid":false,"given":"Stefan","family":"Walzer","sequence":"first","affiliation":[{"name":"Department of Computer Science, Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7,28]]},"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","first-page":"352","volume-title":"Proc. DCC","author":"Belazzougui Djamal","year":"2014","unstructured":"Djamal Belazzougui, Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini, and Sebastiano Vigna. 2014. Cache-oblivious peeling of random hypergraphs. In Proc. DCC, 352\u2013361. DOI: 10.1109\/DCC.2014.48"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","unstructured":"Itai Benjamini and Oded Schramm. 2011. Recurrence of distributional limits of finite planar graphs. Springer New York 533\u2013545. DOI: 10.1007\/978-1-4419-9675-6_15","DOI":"10.1007\/978-1-4419-9675-6_15"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_3_2_6_2","first-page":"227","volume-title":"Proc. 23rd WWW \u201914","author":"Boldi Paolo","year":"2014","unstructured":"Paolo Boldi, Andrea Marino, Massimo Santini, and Sebastiano Vigna. 2014. BUbiNG: Massive crawling for the masses. In Proc. 23rd WWW \u201914, 227\u2013228. DOI: 10.1145\/2567948.2577304"},{"key":"e_1_3_2_7_2","unstructured":"Charles Bordenave. 2016. Lecture notes on random graphs and probabilistic combinatorial optimization. Retrieved from https:\/\/www.i2m.univ-amu.fr\/perso\/charles.bordenave\/_media\/coursrg.pdf"},{"key":"e_1_3_2_8_2","unstructured":"Fabiano Cupertino Botelho. 2008. Near-Optimal Space Perfect Hashing Algorithms. Ph.D. Dissertation Federal University of Minas Gerais. Retrieved from http:\/\/cmph.sourceforge.net\/papers\/thesis.pdf"},{"key":"e_1_3_2_9_2","first-page":"139","volume-title":"Proc. 10th WADS","author":"Botelho Fabiano Cupertino","year":"2007","unstructured":"Fabiano Cupertino Botelho, Rasmus Pagh, and Nivio Ziviani. 2007. Simple and space-efficient minimal perfect hash functions. In Proc. 10th WADS, 139\u2013150. DOI: 10.1007\/978-3-540-73951-7_13"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2012.06.002"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_3_2_12_2","first-page":"469","volume-title":"Proc. 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\\) -orientability and a fast algorithm for optimal multiple-choice allocation. In Proc. 18th SODA, 469\u2013476. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283433"},{"key":"e_1_3_2_13_2","first-page":"259","volume-title":"Proc. 16th ESA","author":"Charles Denis Xavier","year":"2008","unstructured":"Denis Xavier Charles and Kumar Chellapilla. 2008. Bloomier filters: A second look. In Proc. 16th ESA, 259\u2013270. DOI: 10.1007\/978-3-540-87744-8_22"},{"key":"e_1_3_2_14_2","unstructured":"Yann Collet. 2020. xxhash\u2014Extremely fast Hash algorithm. Retrieved from https:\/\/github.com\/Cyan4973\/xxHash"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20040"},{"key":"e_1_3_2_16_2","first-page":"213","volume-title":"Proc. 37th ICALP (1)","author":"Dietzfelbinger Martin","year":"2010","unstructured":"Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, and Michael Rink. 2010. Tight thresholds for cuckoo hashing via XORSAT. In Proc. 37th ICALP (1), 213\u2013225. DOI: 10.1007\/978-3-642-14165-2_19"},{"key":"e_1_3_2_17_2","first-page":"385","volume-title":"Proc. 35th ICALP (1)","author":"Dietzfelbinger Martin","year":"2008","unstructured":"Martin Dietzfelbinger and Rasmus Pagh. 2008. Succinct data structures for retrieval and approximate membership (extended abstract). In Proc. 35th ICALP (1), 385\u2013396. DOI: 10.1007\/978-3-540-70575-8_32"},{"key":"e_1_3_2_18_2","first-page":"99","volume-title":"Proc. 7th CSR","author":"Dietzfelbinger Martin","year":"2012","unstructured":"Martin Dietzfelbinger and Michael Rink. 2012. Towards optimal degree-distributions for left-perfect matchings in random bipartite graphs. In Proc. 7th CSR, 99\u2013111. DOI: 10.1007\/978-3-642-30642-6_11"},{"key":"e_1_3_2_19_2","first-page":"24:1","volume-title":"Proc. 36th STACS","author":"Dietzfelbinger Martin","year":"2019","unstructured":"Martin Dietzfelbinger and Stefan Walzer. 2019. Constant-time retrieval with \\(o(\\log M)\\) extra bits. In Proc. 36th STACS, 24:1\u201324:16. DOI: 10.4230\/LIPIcs.STACS.2019.24"},{"key":"e_1_3_2_20_2","first-page":"38:1","volume-title":"Proc. 27th ESA","author":"Dietzfelbinger Martin","year":"2019","unstructured":"Martin Dietzfelbinger and Stefan Walzer. 2019. Dense peelable random uniform hypergraphs. In Proc. 27th ESA, 38:1\u201338:16. DOI: 10.4230\/LIPIcs.ESA.2019.38"},{"key":"e_1_3_2_21_2","first-page":"39:1","volume-title":"Proc. 27th ESA","author":"Dietzfelbinger Martin","year":"2019","unstructured":"Martin Dietzfelbinger and Stefan Walzer. 2019. Efficient Gauss elimination for near-quadratic matrices with one short random block per row, with applications. In Proc. 27th ESA, 39:1\u201339:18. DOI: 10.4230\/LIPIcs.ESA.2019.39"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.SEA.2022.4"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.132"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.782171"},{"key":"e_1_3_2_26_2","first-page":"459","volume-title":"Proc. 18th SODA","author":"Fernholz Daniel","year":"2007","unstructured":"Daniel Fernholz and Vijaya Ramachandran. 2007. The \\(k\\) -orientability thresholds for \\(g_{n},P\\) . In Proc. 18th SODA, 459\u2013468. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283432"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000334"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20426"},{"issue":"4","key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","article-title":"Sharp thresholds of graph properties, and the \\(k\\) -SAT problem","volume":"12","author":"Friedgut Ehud","year":"1999","unstructured":"Ehud Friedgut and Jean Bourgain. 1999. Sharp thresholds of graph properties, and the \\(k\\) -SAT problem. J. Am. Math. Soc. 12, 4 (1999), 1017\u20131054. Retrieved from http:\/\/www.jstor.org\/stable\/2646096","journal-title":"J. Am. Math. Soc."},{"key":"e_1_3_2_30_2","first-page":"1497","volume-title":"Proc. 28th SODA","author":"Frieze Alan","year":"2017","unstructured":"Alan Frieze and Tony Johansson. 2017. On the insertion time of random walk cuckoo hashing. In Proc. 28th SODA, 1497\u20131502. DOI: 10.1137\/1.9781611974782.97"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20427"},{"key":"e_1_3_2_32_2","first-page":"339","volume-title":"Proc. 15th SEA","author":"Genuzio Marco","year":"2016","unstructured":"Marco Genuzio, Giuseppe Ottaviano, and Sebastiano Vigna. 2016. Fast scalable construction of (minimal perfect Hash) functions. In Proc. 15th SEA, 339\u2013352. DOI: 10.1007\/978-3-319-38851-9_23"},{"key":"e_1_3_2_33_2","first-page":"458","volume-title":"Proc. ISIT","author":"Giurgiu Andrei","year":"2012","unstructured":"Andrei Giurgiu, Nicolas Macris, and R\u00fcdiger L. Urbanke. 2012. How to prove the maxwell conjecture via spatial coupling - a proof of concept. In Proc. ISIT, 458\u2013462. DOI: 10.1109\/ISIT.2012.6284230"},{"key":"e_1_3_2_34_2","first-page":"792","volume-title":"Proc. 49th Allerton","author":"Goodrich Michael T.","year":"2011","unstructured":"Michael T. Goodrich and Michael Mitzenmacher. 2011. Invertible bloom lookup tables. In Proc. 49th Allerton, 792\u2013799. DOI: 10.1109\/Allerton.2011.6120248"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3376122"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3510449"},{"key":"e_1_3_2_37_2","first-page":"2453","volume-title":"Proc. ISIT","author":"Hassani Seyed Hamed","year":"2013","unstructured":"Seyed Hamed Hassani, Nicolas Macris, and R\u00fcdiger L. Urbanke. 2013. The space of solutions of coupled XORSAT formulae. In Proc. ISIT, 2453\u20132457. DOI: 10.1109\/ISIT.2013.6620667"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20147"},{"key":"e_1_3_2_39_2","first-page":"601","volume-title":"Proc. 21st ESA","author":"Khosla Megha","year":"2013","unstructured":"Megha Khosla. 2013. Balls Into bins made faster. In Proc. 21st ESA, 601\u2013612. DOI: 10.1007\/978-3-642-40450-4_51"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00595-4"},{"key":"e_1_3_2_41_2","first-page":"873","volume-title":"Proc. ICM, Vol. III","author":"Kim Jeong Han","year":"2006","unstructured":"Jeong Han Kim. 2006. Poisson cloning model for random graphs. In Proc. ICM, Vol. III, 873\u2013898. Retrieved from https:\/\/www.mathunion.org\/fileadmin\/ICM\/Proceedings\/ICM2006.3\/ICM2006.3.ocr.pdf"},{"key":"e_1_3_2_42_2","first-page":"18","article-title":"Statistical-physics-based reconstruction in compressed sensing","volume":"2","author":"Krzakala Florent","year":"2012","unstructured":"Florent Krzakala, Marc M\u00e9zard, Fran\u00e7ois Sausset, Yifan Sun, and Lenka Zdeborov\u00e1. 2012. Statistical-physics-based reconstruction in compressed sensing. Phys. Rev. X 2 (2012), 18.","journal-title":"Phys. Rev. X"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2438870"},{"key":"e_1_3_2_44_2","first-page":"684","volume-title":"Proc. ISIT","author":"Kudekar Shrinivas","year":"2010","unstructured":"Shrinivas Kudekar, Tom Richardson, and R\u00fcdiger L. Urbanke. 2010. Threshold saturation via spatial coupling: Why convolutional LDPC ensembles perform so well over the BEC. In Proc. ISIT, 684\u2013688. DOI: 10.1109\/ISIT.2010.5513587"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2280915"},{"key":"e_1_3_2_46_2","first-page":"131","volume-title":"Proc. 51st Allerton","author":"Leconte Mathieu","year":"2013","unstructured":"Mathieu Leconte. 2013. Double hashing thresholds via local weak convergence. In Proc. 51st Allerton, 131\u2013137. DOI: 10.1109\/Allerton.2013.6736515"},{"key":"e_1_3_2_47_2","first-page":"251","volume-title":"Proc. 23rd SODA","author":"Lelarge Marc","year":"2012","unstructured":"Marc Lelarge. 2012. A new approach to the orientation of random hypergraphs. In Proc. 23rd SODA, 251\u2013264. DOI: 10.1137\/1.9781611973099.23"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.910575"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90162-U"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2018.2889329"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/39.6.547"},{"key":"e_1_3_2_52_2","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001","volume-title":"Information, Physics, and Computation","author":"Mezard Marc","year":"2009","unstructured":"Marc Mezard and Andrea Montanari. 2009. Information, Physics, and Computation. Oxford University Press, Inc., USA."},{"key":"e_1_3_2_53_2","first-page":"1","volume-title":"Proc. 17th ESA","author":"Mitzenmacher Michael","year":"2009","unstructured":"Michael Mitzenmacher. 2009. Some open questions related to cuckoo hashing. In Proc. 17th ESA, 1\u201310. DOI: 10.1007\/978-3-642-04128-0_1"},{"key":"e_1_3_2_54_2","first-page":"29:1","volume-title":"Proc. 16th SWAT","author":"Mitzenmacher Michael","year":"2018","unstructured":"Michael Mitzenmacher, Konstantinos Panagiotou, and Stefan Walzer. 2018. Load thresholds for cuckoo hashing with double hashing. In Proc. 16th SWAT, 29:1\u201329:9. DOI: 10.4230\/LIPIcs.SWAT.2018.29"},{"key":"e_1_3_2_55_2","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher Michael","year":"2017","unstructured":"Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press, New York, NY, USA, 2nd edition.","edition":"2"},{"key":"e_1_3_2_56_2","first-page":"483","volume-title":"Proc. ISIT","author":"Mitzenmacher Michael","year":"2012","unstructured":"Michael Mitzenmacher and George Varghese. 2012. Biff (bloom filter) codes: Fast error correction for large data sets. In Proc. ISIT, 483\u2013487. DOI: 10.1109\/ISIT.2012.6284236"},{"key":"e_1_3_2_57_2","unstructured":"Michael David Mitzenmacher. 1991. The Power of Two Choices in Randomized Load Balancing. Ph.D. Dissertation. Harvard University. Retrieved from https:\/\/www.eecs.harvard.edu\/ michaelm\/postscripts\/mythesis.pdf"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20061"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0036"},{"key":"e_1_3_2_61_2","first-page":"263","volume-title":"Proc. 4th CSR","author":"Porat Ely","year":"2009","unstructured":"Ely Porat. 2009. An optimal bloom filter replacement based on matrix solving. In Proc. 4th CSR, 263\u2013273. DOI: 10.1007\/978-3-642-03351-3_25"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9780511791338"},{"key":"e_1_3_2_63_2","first-page":"356","volume-title":"Proc. 39th SOFSEM","author":"Rink Michael","year":"2013","unstructured":"Michael Rink. 2013. Mixed hypergraphs for linear-time construction of denser hashing-based data structures. In Proc. 39th SOFSEM, 356\u2013368. DOI: 10.1007\/978-3-642-35843-2_31"},{"key":"e_1_3_2_64_2","first-page":"1","volume-title":"IEEE Information Theory Workshop","author":"Schlegel Christian","year":"2013","unstructured":"Christian Schlegel and Marat V. Burnashev. 2013. Thresholds of spatially coupled systems via lyapunov\u2019s method. In IEEE Information Theory Workshop, 1\u20135. DOI: 10.1109\/ITW.2013.6691236"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1587\/transfun.E95.A.974"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1981.1056404"},{"key":"e_1_3_2_67_2","unstructured":"Stefan Walzer. 2020. Experimental comparison of retrieval data structures. Retrieved from https:\/\/github.com\/sekti\/retrieval-test"},{"key":"e_1_3_2_68_2","unstructured":"Stefan Walzer. 2020. Random Hypergraphs for Hashing-Based Data Structures. Ph.D. Dissertation. Technische Universit\u00e4t Ilmenau Germany. Retrieved from https:\/\/www.db-thueringen.de\/receive\/dbt_mods_00047127"},{"key":"e_1_3_2_69_2","first-page":"401","volume-title":"Proc. 21st SAT","author":"Weaver Sean A.","year":"2018","unstructured":"Sean A. Weaver, Hannah J. Roberts, and Michael J. Smith. 2018. XOR-satisfiability set membership filters. In Proc. 21st SAT, 401\u2013418. DOI: 10.1007\/978-3-319-94144-8_24"},{"key":"e_1_3_2_70_2","first-page":"51","volume-title":"Proc. 7th ISTC","author":"Yedla Arvind","year":"2012","unstructured":"Arvind Yedla, Yung-Yih Jian, Phong S. Nguyen, and Henry D. Pfister. 2012. A simple proof of threshold saturation for coupled scalar recursions. In Proc. 7th ISTC, 51\u201355. DOI: 10.1109\/ISTC.2012.6325197"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3711822","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,28]],"date-time":"2025-07-28T11:45:35Z","timestamp":1753703135000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3711822"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,28]]},"references-count":69,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,7,31]]}},"alternative-id":["10.1145\/3711822"],"URL":"https:\/\/doi.org\/10.1145\/3711822","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,28]]},"assertion":[{"value":"2021-03-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}