{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T04:04:10Z","timestamp":1747541050725,"version":"3.40.5"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031929311","type":"print"},{"value":"9783031929328","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-92932-8_19","type":"book-chapter","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:31Z","timestamp":1747468051000},"page":"292-309","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Dynamic Filter and\u00a0Retrieval with\u00a0One Access to\u00a0Modifiable Memory"],"prefix":"10.1007","author":[{"given":"Ioana O.","family":"Bercea","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Even","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomer","family":"Even","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriel Marques","family":"Domingues","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,18]]},"reference":[{"key":"19_CR1","unstructured":"Agarwala, A., Even, G.: A space lower bound for approximate membership with duplicate insertions or deletions of nonelements (2024). https:\/\/arxiv.org\/abs\/2412.19249"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., Segev, G.: Backyard cuckoo hashing: constant worst-case operations with a succinct representation. In: FOCS 2010, pp. 787\u2013796 (2010). see also arXiv:0912.5424v3","DOI":"10.1109\/FOCS.2010.80"},{"issue":"6","key":"19_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3625817","volume":"70","author":"MA Bender","year":"2023","unstructured":"Bender, M.A., Conway, A., Farach-Colton, M., Kuszmaul, W., Tagliavini, G.: Iceberg hashing: optimizing many hash-table criteria at once. JACM 70(6), 1\u201351 (2023)","journal-title":"JACM"},{"key":"19_CR4","doi-asserted-by":"publisher","unstructured":"Bender, M.A., Farach-Colton, M., Goswami, M., Johnson, R., McCauley, S., Singh, S.: Bloom filters, adaptivity, and the dictionary problem. In: FOCS 2018, pp. 182\u2013193 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00026","DOI":"10.1109\/FOCS.2018.00026"},{"key":"19_CR5","doi-asserted-by":"publisher","unstructured":"Bender, M.A., et al.: Don\u2019t thrash: how to cache your hash on flash. PVLDB 5(11), 1627\u20131637 (2012). https:\/\/doi.org\/10.14778\/2350229.2350275","DOI":"10.14778\/2350229.2350275"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Bercea, I.O., Beretta, L., Klausen, J., Houen, J.B.T., Thorup, M.: Locally uniform hashing. In: FOCS 2023. pp. 1440\u20131470 (2023)","DOI":"10.1109\/FOCS57990.2023.00089"},{"key":"19_CR7","unstructured":"Bercea, I.O., Even, G.: Fully-dynamic space-efficient dictionaries and filters with constant number of memory accesses (2019). http:\/\/arxiv.org\/abs\/1911.05060"},{"key":"19_CR8","doi-asserted-by":"publisher","unstructured":"Bercea, I.O., Even, G.: A dynamic space-efficient filter with constant time operations. In: SWAT 2020. LIPIcs, vol.\u00a0162, pp. 1\u201317 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2020.11","DOI":"10.4230\/LIPIcs.SWAT.2020.11"},{"issue":"7","key":"19_CR9","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"BH Bloom","year":"1970","unstructured":"Bloom, B.H.: Space\/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422\u2013426 (1970). https:\/\/doi.org\/10.1145\/362686.362692","journal-title":"Commun. ACM"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Carter, L., Floyd, R., Gill, J., Markowsky, G., Wegman, M.: Exact and approximate membership testers. In: STOC 1978, pp. 59\u201365 (1978)","DOI":"10.1145\/800133.804332"},{"key":"19_CR11","unstructured":"Chazelle, B., Kilian, J., Rubinfeld, R., Tal, A.: The Bloomier filter: an efficient data structure for static support lookup tables. In: SODA 2004, pp. 30\u201339 (2004)"},{"issue":"1","key":"19_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3588726","volume":"1","author":"A Conway","year":"2023","unstructured":"Conway, A., Farach-Colton, M., Johnson, R.: SplinterDB and Maplets: improving the tradeoffs in key-value store compaction policy. Proc. ACM Manage. Data 1(1), 1\u201327 (2023)","journal-title":"Proc. ACM Manage. Data"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Meyer auf\u00a0der Heide, F., Pagh, R., P\u0103tra\u015fcu, M.: De dictionariis dynamicis pauco spatio utentibus. In: LATIN 2006, pp. 349\u2013361 (2006)","DOI":"10.1007\/11682462_34"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Pagh, R.: Succinct data structures for retrieval and approximate membership. In: ICALP 2008, pp. 385\u2013396 (2008)","DOI":"10.1007\/978-3-540-70575-8_32"},{"key":"19_CR15","doi-asserted-by":"publisher","unstructured":"Dietzfelbinger, M., Walzer, S.: Constant-time retrieval with $$o(\\log m)$$ extra bits. In: STACS 2019, pp. 1\u201316 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.24","DOI":"10.4230\/LIPIcs.STACS.2019.24"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Woelfel, P.: Almost random graphs with simple hash functions. In: STOC 2003, pp. 629\u2013638 (2003)","DOI":"10.1145\/780542.780634"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Dillinger, P.C., Manolios, P.: Fast, all-purpose state storage. In: Model Checking Software: 16th International SPIN Workshop 2009, Proceedings 16, pp. 12\u201331 (2009)","DOI":"10.1007\/978-3-642-02652-2_6"},{"key":"19_CR18","unstructured":"Dillinger, P.C., Walzer, S.: Ribbon filter: practically smaller than Bloom and Xor. CoRR abs\/2103.02515 (2021).https:\/\/arxiv.org\/abs\/2103.02515"},{"issue":"2","key":"19_CR19","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. JACM 21(2), 246\u2013260 (1974)","journal-title":"JACM"},{"key":"19_CR20","doi-asserted-by":"publisher","unstructured":"Even, G., Marques Domingues, G.: A micro-architecture that supports the Fano\u2013Elias encoding and a hardware accelerator for approximate membership queries. Microprocessors Microsyst. 105 (2024). https:\/\/doi.org\/10.1016\/j.micpro.2023.104992","DOI":"10.1016\/j.micpro.2023.104992"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"Even, G., Marques Domingues, G., Toutian, P.: Brief announcement: a parallel architecture for dynamic approximate membership. In: SPAA 2023, pp. 291\u2013294 (2023)","DOI":"10.1145\/3558481.3591312"},{"issue":"7","key":"19_CR22","doi-asserted-by":"publisher","first-page":"1311","DOI":"10.14778\/3523210.3523211","volume":"15","author":"T Even","year":"2022","unstructured":"Even, T., Even, G., Morrison, A.: Prefix filter: practically and theoretically better than Bloom. Proc. VLDB Endowment 15(7), 1311\u20131323 (2022)","journal-title":"Proc. VLDB Endowment"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"Fan, B., Andersen, D.G., Kaminsky, M., Mitzenmacher, M.: Cuckoo filter: practically better than bloom. In: CoNEXT, pp. 75\u201388. ACM (2014)","DOI":"10.1145\/2674005.2674994"},{"key":"19_CR24","unstructured":"Fano, R.M.: On the number of bits required to implement an associative memory. memorandum 61. Computer Structures Group, Project MAC, MIT, Cambridge, Mass (1971)"},{"key":"19_CR25","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Willard, D.E.: Blasting through the information theoretic barrier with fusion trees. In: STOC 1990, pp. 1\u20137 (1990)","DOI":"10.1145\/100216.100217"},{"key":"19_CR26","unstructured":"Graf, T.M., Lemire, D.: Xor filters: Faster and smaller than bloom and cuckoo filters. CoRR abs\/1912.08258 (2019). http:\/\/arxiv.org\/abs\/1912.08258"},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"Hagerup, T.: Sorting and searching on the word RAM. In: STACS 1998, pp. 366\u2013398 (1998)","DOI":"10.1007\/BFb0028575"},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"Kirsch, A., Mitzenmacher, M.: Less hashing, same performance: building a better Bloom filter. In: ESA 2006, pp. 456\u2013467 (2006)","DOI":"10.1007\/11841036_42"},{"key":"19_CR29","doi-asserted-by":"publisher","unstructured":"Kuszmaul, W., Walzer, S.: Space lower bounds for dynamic filters and value-dynamic retrieval. In: STOC 2024, pp. 1153\u20131164 (2024). https:\/\/doi.org\/10.1145\/3618260.3649649","DOI":"10.1145\/3618260.3649649"},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"Lovett, S., Porat, E.: A lower bound for dynamic approximate membership data structures. In: FOCS 2010, pp. 797\u2013804 (2010)","DOI":"10.1109\/FOCS.2010.81"},{"key":"19_CR31","doi-asserted-by":"crossref","unstructured":"Mortensen, C.W., Pagh, R., P\u0103tra\u015fcu, M.: On dynamic range reporting in one dimension. In: STOC 2005, pp. 104\u2013111 (2005)","DOI":"10.1145\/1060590.1060606"},{"key":"19_CR32","unstructured":"Pagh, A., Pagh, R., Rao, S.S.: An optimal Bloom filter replacement. In: SODA 2005, pp. 823\u2013829 (2005)"},{"key":"19_CR33","doi-asserted-by":"crossref","unstructured":"Pagh, R., Segev, G., Wieder, U.: How to approximate a set without knowing its size in advance. In: FOCS 2013. pp. 80\u201389 (2013). see also arXiv:1304.1188v2","DOI":"10.1109\/FOCS.2013.17"},{"key":"19_CR34","doi-asserted-by":"crossref","unstructured":"Putze, F., Sanders, P., Singler, J.: Cache-, hash-, and space-efficient Bloom filters. J. Exp. Algorithmics 14, 4\u20134 (2010)","DOI":"10.1145\/1498698.1594230"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-92932-8_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:39Z","timestamp":1747468059000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-92932-8_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031929311","9783031929328"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-92932-8_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"18 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/easyconferences.eu\/ciac2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}