{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:43Z","timestamp":1779174823997,"version":"3.51.4"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>Filter data structures are widely used in various areas of computer science to answer approximate set-membership queries. In many applications, the data grows dynamically, requiring their filters to expand along with the data. However, existing methods for expanding filters cannot maintain stable performance, memory footprint, and false positive rate (FPR) simultaneously. We address this problem with Aleph Filter, which makes the following contributions. (1) It supports all operations (insertions, queries, deletes, etc.) in constant time, no matter how much the data grows. (2) Given an estimate of how much the data will ultimately grow, Aleph Filter provides a memory vs. FPR trade-offs on par with static filters.<\/jats:p>","DOI":"10.14778\/3681954.3682027","type":"journal-article","created":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T16:23:36Z","timestamp":1725035016000},"page":"3644-3656","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Aleph Filter: To Infinity in Constant Time"],"prefix":"10.14778","volume":"17","author":[{"given":"Niv","family":"Dayan","sequence":"first","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioana-Oriana","family":"Bercea","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[{"name":"BARC, University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Paulo S\u00e9rgio Almeida Carlos Baquero Nuno Pregui\u00e7a and David Hutchison. 2007. Scalable Bloom Filters. Inform. Process. Lett. (2007).","DOI":"10.1016\/j.ipl.2006.10.007"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629577"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.3129"},{"key":"e_1_2_1_4_1","volume-title":"Don't Thrash: How to Cache Your Hash on Flash. PVLDB","author":"Bender Michael A.","year":"2012","unstructured":"Michael A. Bender, Martin Farach-Colton, Rob Johnson, Russell Kraner, Bradley C. Kuszmaul, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard P. Spillane, and Erez Zadok. 2012. Don't Thrash: How to Cache Your Hash on Flash. PVLDB (2012)."},{"key":"e_1_2_1_5_1","volume-title":"Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses. SWAT","author":"Bercea Ioana O","year":"2020","unstructured":"Ioana O Bercea and Guy Even. 2020. Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses. SWAT (2020)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Burton H. Bloom. 1970. Space\/Time Trade-offs in Hash Coding with Allowable Errors. CACM (1970).","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213884"},{"key":"e_1_2_1_8_1","first-page":"636","article-title":"Network Applications of Bloom Filters: A Survey","volume":"1","author":"Broder Andrei Z.","year":"2002","unstructured":"Andrei Z. Broder and Michael Mitzenmacher. 2002. Network Applications of Bloom Filters: A Survey. Internet Mathematics 1 (2002), 636--646.","journal-title":"Internet Mathematics"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Larry Carter Robert Floyd John Gill George Markowsky and Mark Wegman. 1978. Exact and Approximate Membership Testers. In STOC.","DOI":"10.1145\/800133.804332"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.48"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196898"},{"key":"e_1_2_1_12_1","volume-title":"Oasis: An Optimal Disjoint Segmented Learned Range Filter. PVLDB","author":"Chen Guanduo","year":"2024","unstructured":"Guanduo Chen, Zhenying He, Meng Li, and Siqiang Luo. 2024. Oasis: An Optimal Disjoint Segmented Learned Range Filter. PVLDB (2024)."},{"key":"e_1_2_1_13_1","volume-title":"The Dynamic Cuckoo Filter. ICNP","author":"Chen Hanhua","year":"2017","unstructured":"Hanhua Chen, Liangyi Liao, Hai Jin, and Jie Wu. 2017. The Dynamic Cuckoo Filter. ICNP (2017)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676499"},{"key":"e_1_2_1_15_1","volume-title":"https:\/\/github.com\/Cyan4973\/xxHash","author":"Collet Yann","year":"2023","unstructured":"Yann Collet. 2023. XXHash. https:\/\/github.com\/Cyan4973\/xxHash (2023)."},{"key":"e_1_2_1_16_1","volume-title":"SplinterDB and Maplets: Improving the Tradeoffs in Key-Value Store Compaction Policy. SIGMOD","author":"Conway Alex","year":"2023","unstructured":"Alex Conway, Mart\u00edn Farach-Colton, and Rob Johnson. 2023. SplinterDB and Maplets: Improving the Tradeoffs in Key-Value Store Compaction Policy. SIGMOD (2023)."},{"key":"e_1_2_1_17_1","volume-title":"Grafite: Taming Adversarial Queries with Optimal Range Filters. SIGMOD","author":"Costa Marco","year":"2024","unstructured":"Marco Costa, Paolo Ferragina, and Giorgio Vinciguerra. 2024. Grafite: Taming Adversarial Queries with Optimal Range Filters. SIGMOD (2024)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_2_1_19_1","volume-title":"InfiniFilter: Expanding Filters to Infinity and Beyond. SIGMOD","author":"Dayan Niv","year":"2023","unstructured":"Niv Dayan, Ioana Bercea, Pedro Reviriego, and Rasmus Pagh. 2023. InfiniFilter: Expanding Filters to Infinity and Beyond. SIGMOD (2023)."},{"key":"e_1_2_1_20_1","volume-title":"Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging. SIGMOD","author":"Dayan Niv","year":"2018","unstructured":"Niv Dayan and Stratos Idreos. 2018. Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging. SIGMOD (2018)."},{"key":"e_1_2_1_21_1","volume-title":"The Log-Structured Merge-Bush & the Wacky Continuum. SIGMOD","author":"Dayan Niv","year":"2019","unstructured":"Niv Dayan and Stratos Idreos. 2019. The Log-Structured Merge-Bush & the Wacky Continuum. SIGMOD (2019)."},{"key":"e_1_2_1_22_1","volume-title":"Chucky: A Succinct Cuckoo Filter for LSM-Tree. SIGMOD","author":"Dayan Niv","year":"2021","unstructured":"Niv Dayan and Moshe Twitto. 2021. Chucky: A Succinct Cuckoo Filter for LSM-Tree. SIGMOD (2021)."},{"key":"e_1_2_1_23_1","volume-title":"Edward Bortnikov, Shmuel Dashevsky, Ofer Frishman, Evgeni Ginzburg, Igal Maly, et al.","author":"Dayan Niv","year":"2021","unstructured":"Niv Dayan, Moshe Twitto, Yuval Rochman, Uri Beitler, Itai Ben Zion, Edward Bortnikov, Shmuel Dashevsky, Ofer Frishman, Evgeni Ginzburg, Igal Maly, et al. 2021. The End of Moore's Law and the Rise of the Data Processor. PVLDB (2021)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1921015"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989327"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436919"},{"key":"e_1_2_1_27_1","volume-title":"Fast Succinct Retrieval and Approximate Membership Using Ribbon. SEA","author":"Dillinger Peter C","year":"2022","unstructured":"Peter C Dillinger, Lorenz H\u00fcbschle-Schneider, Peter Sanders, and Stefan Walzer. 2022. Fast Succinct Retrieval and Approximate Membership Using Ribbon. SEA (2022)."},{"key":"e_1_2_1_28_1","volume-title":"Dillinger and Panagiotis Pete Manolios","author":"Peter","year":"2009","unstructured":"Peter C. Dillinger and Panagiotis Pete Manolios. 2009. Fast, All-Purpose State Storage. SPIN (2009)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523211"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_31_1","volume-title":"Kasper Green Larsen, and Rasmus Pagh","author":"Goswami Mayank","year":"2014","unstructured":"Mayank Goswami, Allan Gr\u00f8nlund, Kasper Green Larsen, and Rasmus Pagh. 2014. Approximate Range Emptiness in Constant Time and Optimal Space. SODA (2014)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3376122"},{"key":"e_1_2_1_33_1","volume-title":"Theory and Network Applications of Dynamic Bloom Filters. INFOCOM","author":"Guo Deke","year":"2006","unstructured":"Deke Guo, Jie Wu, Honghui Chen, and Xueshan Luo. 2006. Theory and Network Applications of Dynamic Bloom Filters. INFOCOM (2006)."},{"key":"e_1_2_1_34_1","volume-title":"The Dynamic Bloom Filters","author":"Guo Deke","year":"2009","unstructured":"Deke Guo, Jie Wu, Honghui Chen, Ye Yuan, and Xueshan Luo. 2009. The Dynamic Bloom Filters. IEEE Trans Knowl Data Eng (2009)."},{"key":"e_1_2_1_35_1","unstructured":"Stratos Idreos Niv Dayan Wilson Qin Mali Akmanalp Sophie Hilgard Andrew Ross James Lennon Varun Jain Harshita Gupta David Li and Zichen Zhu. 2019. Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn. In CIDR."},{"key":"e_1_2_1_36_1","volume-title":"Proteus: A Self-Designing Range Filter. SIGMOD","author":"Knorr Eric R","year":"2022","unstructured":"Eric R Knorr, Baptiste Lemaire, Andrew Lim, Siqiang Luo, Huanchen Zhang, Stratos Idreos, and Michael Mitzenmacher. 2022. Proteus: A Self-Designing Range Filter. SIGMOD (2022)."},{"key":"e_1_2_1_37_1","volume-title":"Jeffrey Dean, and Neoklis Polyzotis.","author":"Kraska Tim","year":"2018","unstructured":"Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The Case for Learned Index Structures. SIGMOD (2018)."},{"key":"e_1_2_1_38_1","volume-title":"Succinct Filters for Sets of Unknown Sizes. ICALP","author":"Liu Mingmou","year":"2020","unstructured":"Mingmou Liu, Yitong Yin, and Huacheng Yu. 2020. Succinct Filters for Sets of Unknown Sizes. ICALP (2020)."},{"key":"e_1_2_1_39_1","volume-title":"Xueshan Luo, and Bangbang Ren.","author":"Luo Lailong","year":"2019","unstructured":"Lailong Luo, Deke Guo, Ori Rottenstreich, Richard TB Ma, Xueshan Luo, and Bangbang Ren. 2019. The Consistent Cuckoo Filter. INFOCOM (2019)."},{"key":"e_1_2_1_40_1","volume-title":"Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores. SIGMOD","author":"Luo Siqiang","year":"2020","unstructured":"Siqiang Luo, Subarna Chatterjee, Rafael Ketsetsidis, Niv Dayan, Wilson Qin, and Stratos Idreos. 2020. Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores. SIGMOD (2020)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975055.4"},{"key":"e_1_2_1_42_1","volume-title":"bloomRF: On performing range-queries in Bloom-Filters with piecewise-monotone hash functions and prefix hashing. EDBT","author":"M\u00f6\u00dfner Bernhard","year":"2022","unstructured":"Bernhard M\u00f6\u00dfner, Christian Riegger, Arthur Bernhardt, and Ilia Petrov. 2022. bloomRF: On performing range-queries in Bloom-Filters with piecewise-monotone hash functions and prefix hashing. EDBT (2022)."},{"key":"e_1_2_1_43_1","volume-title":"How to Approximate a Set Without Knowing its Size in Advance. FOCS","author":"Pagh Rasmus","year":"2013","unstructured":"Rasmus Pagh, Gil Segev, and Udi Wieder. 2013. How to Approximate a Set Without Knowing its Size in Advance. FOCS (2013)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Prashant Pandey Alex Conway Joe Durie Michael A Bender Martin Farach-Colton and Rob Johnson. 2021. Vector Quotient Filters: Overcoming the Time\/Space Trade-Off in Filter Design. In SIGMOD.","DOI":"10.1145\/3448016.3452841"},{"key":"e_1_2_1_46_1","volume-title":"Beyond Bloom: A Tutorial on Future Feature-Rich Filters. SIGMOD","author":"Pandey Prashant","year":"2024","unstructured":"Prashant Pandey, Mart\u00edn Farach-Colton, Niv Dayan, and Huanchen Zhang. 2024. Beyond Bloom: A Tutorial on Future Feature-Rich Filters. SIGMOD (2024)."},{"key":"e_1_2_1_47_1","volume-title":"Addressing for random-access storage. IBM journal of Research and Development","author":"Peterson W Wesley","year":"1957","unstructured":"W Wesley Peterson. 1957. Addressing for random-access storage. IBM journal of Research and Development (1957)."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151108"},{"key":"e_1_2_1_49_1","volume-title":"Cardinality Estimation Adaptive Cuckoo Filters (CE-ACF): Approximate Membership Check and Distinct Query Count for High-Speed Network Monitoring","author":"Reviriego Pedro","year":"2023","unstructured":"Pedro Reviriego, Jim Apple, Alvaro Alonso, Otmar Ertl, and Niv Dayan. 2023. Cardinality Estimation Adaptive Cuckoo Filters (CE-ACF): Approximate Membership Check and Distinct Query Count for High-Speed Network Monitoring. IEEE\/ACM Trans. Netw. (2023)."},{"key":"e_1_2_1_50_1","volume-title":"On the Security of Quotient Filters: Attacks and Potential Countermeasures","author":"Reviriego Pedro","year":"2024","unstructured":"Pedro Reviriego, Miguel Gonz\u00e1lez, Niv Dayan, Gabriel Huecas, Shanshan Liu, and Fabrizio Lombardi. 2024. On the Security of Quotient Filters: Attacks and Potential Countermeasures. IEEE Trans. Comput. (2024)."},{"key":"e_1_2_1_51_1","volume-title":"The LSM Design Space and its Read Optimizations. ICDE","author":"Sarkar Subhadeep","year":"2023","unstructured":"Subhadeep Sarkar, Niv Dayan, and Manos Athanassoulis. 2023. The LSM Design Space and its Read Optimizations. ICDE (2023)."},{"key":"e_1_2_1_52_1","volume-title":"Christian Esteve Rothenberg, and Eemil Lagerspetz","author":"Tarkoma Sasu","year":"2012","unstructured":"Sasu Tarkoma, Christian Esteve Rothenberg, and Eemil Lagerspetz. 2012. Theory and Practice of Bloom Filters for Distributed Systems. IEEE Commun. Surv. Tutor (2012)."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529347"},{"key":"e_1_2_1_54_1","volume-title":"Bamboo Filters: Make Resizing Smooth and Adaptive","author":"Wang Hancheng","year":"2024","unstructured":"Hancheng Wang, Haipeng Dai, Shusen Chen, Meng Li, Rong Gu, Huayi Chai, Jiaqi Zheng, Zhiyuan Chen, Shuaituan Li, Xianjun Deng, et al. 2024. Bamboo Filters: Make Resizing Smooth and Adaptive. IEEE\/ACM Trans. Netw. (2024)."},{"key":"e_1_2_1_55_1","volume-title":"Bamboo Filters: Make Resizing Smooth. In ICDE.","author":"Wang Hancheng","year":"2022","unstructured":"Hancheng Wang, Haipeng Dai, Meng Li, Jun Yu, Rong Gu, Jiaqi Zheng, and Guihai Chen. 2022. Bamboo Filters: Make Resizing Smooth. In ICDE."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654944"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364333"},{"key":"e_1_2_1_59_1","volume-title":"Elastic Bloom Filter: Deletable and Expandable Filter Using Elastic Fingerprints","author":"Wu Yuhan","year":"2021","unstructured":"Yuhan Wu, Jintao He, Shen Yan, Jianyu Wu, Tong Yang, Olivier Ruas, Gong Zhang, and Bin Cui. 2021. Elastic Bloom Filter: Deletable and Expandable Filter Using Elastic Fingerprints. IEEE Trans Comput (2021)."},{"key":"e_1_2_1_60_1","volume-title":"A Scalable Bloom Filter for Membership Queries. GLOBECOM","author":"Xie Kun","year":"2007","unstructured":"Kun Xie, Yinghua Min, Dafang Zhang, Jigang Wen, and Gaogang Xie. 2007. A Scalable Bloom Filter for Membership Queries. GLOBECOM (2007)."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/OJCS.2022.3219631"},{"key":"e_1_2_1_62_1","volume-title":"The Logarithmic Dynamic Cuckoo Filter. ICDE","author":"Zhang Fan","year":"2021","unstructured":"Fan Zhang, Hanhua Chen, Hai Jin, and Pedro Reviriego. 2021. The Logarithmic Dynamic Cuckoo Filter. ICDE (2021)."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3681954.3682027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:25:34Z","timestamp":1725474334000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3681954.3682027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":62,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.14778\/3681954.3682027"],"URL":"https:\/\/doi.org\/10.14778\/3681954.3682027","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"2024-08-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}