{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T06:16:06Z","timestamp":1725776166329},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649649","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1153-1164","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Space Lower Bounds for Dynamic Filters and Value-Dynamic Retrieval"],"prefix":"10.1145","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-3855-3036","authenticated-orcid":false,"given":"William","family":"Kuszmaul","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge, USA"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-6477-0106","authenticated-orcid":false,"given":"Stefan","family":"Walzer","sequence":"additional","affiliation":[{"name":"KIT, Karlsruhe, Germany"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"A Bloom Filter Survey: Variants for Different Domain Applications. CoRR, abs\/2106.12189","author":"Abdennebi Anes","year":"2021","unstructured":"Anes Abdennebi and Kamer Kaya. 2021. A Bloom Filter Survey: Variants for Different Domain Applications. CoRR, abs\/2106.12189 (2021), arxiv:2106.12189."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.80"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_66"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976489.2"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00026"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519969"},{"key":"e_1_3_2_1_8_1","volume-title":"Bloom filters. a tutorial, analysis, and survey","author":"Blustein James","year":"2002","unstructured":"James Blustein and Amal El-Maazawi. 2002. Bloom filters. a tutorial, analysis, and survey. Halifax, NS: Dalhousie University, 1\u201331. https:\/\/cdn.dal.ca\/content\/dam\/dalhousie\/pdf\/faculty\/computerscience\/technical-reports\/CS-2002-10.pdf"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804332"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. SIAM, 30\u201339","author":"Chazelle Bernard","year":"2004","unstructured":"Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, and Ayellet Tal. 2004. The Bloomier filter: an efficient data structure for static support lookup tables. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. SIAM, 30\u201339. http:\/\/dl.acm.org\/citation.cfm?id=982792.982797"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2017.8117563"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676499"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_34"},{"volume-title":"Latin American Symposium on Theoretical Informatics. 349\u2013361","author":"Demaine Erik D","key":"e_1_3_2_1_15_1","unstructured":"Erik D Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai P\u01cetra\u015fcu. 2006. De Dictionariis Dynamicis Pauco Spatio Utentibus: (lat. On Dynamic Dictionaries Using Little Space). In Latin American Symposium on Theoretical Informatics. 349\u2013361."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74871-7_2"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_32"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_30"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2019.24"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.SEA.2022.4"},{"key":"e_1_3_2_1_21_1","volume-title":"Dillinger and Stefan Walzer","author":"Peter","year":"2021","unstructured":"Peter C. Dillinger and Stefan Walzer. 2021. Ribbon filter: practically smaller than Bloom and Xor. CoRR, abs\/2103.02515 (2021), arxiv:2103.02515."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0605009"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00055"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3376122"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44693-1_28"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2021.60"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2020.79"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/120867044"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2018.2889329"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737454"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69900-9"},{"key":"e_1_3_2_1_33_1","unstructured":"Michael Mitzenmacher. 2018. A Model for Learned Bloom Filters and Optimizing by Sandwiching. 462\u2013471. https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/0f49c89d1e7298bb9930789c8ed59d48-Abstract.html"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","unstructured":"Michael Mitzenmacher Salvatore Pontarelli and Pedro Reviriego. 2020. Adaptive Cuckoo Filters. 20 pages. https:\/\/doi.org\/10.1145\/3339504 10.1145\/3339504","DOI":"10.1145\/3339504"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060606"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2910180"},{"volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. SIAM, 823\u2013829","author":"Pagh Anna","key":"e_1_3_2_1_37_1","unstructured":"Anna Pagh, Rasmus Pagh, and S. Srinivasa Rao. 2005. An optimal Bloom filter replacement. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. SIAM, 823\u2013829. http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070548"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JALGOR.2003.12.002"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.17"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452841"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.4108\/EAI.19-6-2018.155865"},{"key":"e_1_3_2_1_43_1","volume-title":"Role of Bloom Filter in Big Data Research: A Survey. CoRR, abs\/1903.06565","author":"Patgiri Ripon","year":"2019","unstructured":"Ripon Patgiri, Sabuzima Nayak, and Samir Kumar Borgohain. 2019. Role of Bloom Filter in Big Data Research: A Survey. CoRR, abs\/1903.06565 (2019), arxiv:1903.06565."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03351-3_25"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.KNOSYS.2019.104987"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.031611.00024"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649649","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T21:22:44Z","timestamp":1718918564000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649649"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":46,"alternative-id":["10.1145\/3618260.3649649","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649649","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}