{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T00:36:21Z","timestamp":1774312581113,"version":"3.50.1"},"reference-count":92,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100011033","name":"Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"publisher","award":["TED2021-130118B-I00"],"award-info":[{"award-number":["TED2021-130118B-I00"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Madrid Community research project TAPIR-CM","award":["P2018\/TCS-4496"],"award-info":[{"award-number":["P2018\/TCS-4496"]}]},{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Filter data structures have been used ubiquitously since the 1970s to answer approximate set-membership queries in various areas of computer science including architecture, networks, operating systems, and databases. Such filters need to be allocated with a given capacity in advance to provide a guarantee over the false positive rate. In many applications, however, the data size is not known in advance, requiring filters to dynamically expand. This paper shows that existing methods for expanding filters exhibit at least one of the following flaws: (1) they entail an expensive scan over the whole data set, (2) they require a lavish memory footprint, (3) their query, delete and\/or insertion performance plummets, (4) their false positive rate skyrockets, and\/or (5)~they cannot expand indefinitely.<\/jats:p>\n          <jats:p>We introduce InfiniFilter, a new method for expanding filters that addresses these shortcomings. InfiniFilter is a hash table that stores a fingerprint for each entry. It doubles in size when it reaches capacity, and it sacrifices one bit from each fingerprint to map it to the expanded hash table. The core novelty is a new and flexible hash slot format that sets longer fingerprints to newer entries. This keeps the average fingerprint length long and thus the false positive rate stable. At the same time, InfiniFilter provides stable insertion\/query\/delete performance as it is comprised of a unified hash table. We implement InfiniFilter on top of Quotient Filter, and we demonstrate theoretically and empirically that it offers superior cost properties compared to existing methods: it better scales performance, the false positive rate, and the memory footprint, all at the same time.<\/jats:p>","DOI":"10.1145\/3589285","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-27","source":"Crossref","is-referenced-by-count":20,"title":["InfiniFilter: Expanding Filters to Infinity and Beyond"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0314-0167","authenticated-orcid":false,"given":"Niv","family":"Dayan","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8430-2441","authenticated-orcid":false,"given":"Ioana","family":"Bercea","sequence":"additional","affiliation":[{"name":"IT University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2540-5234","authenticated-orcid":false,"given":"Pedro","family":"Reviriego","sequence":"additional","affiliation":[{"name":"Universidad Politecnica de Madrid, Madrid, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1516-9306","authenticated-orcid":false,"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Nuno Preguicc a, and David Hutchison","author":"Almeida Paulo S\u00e9","year":"2007","unstructured":"Paulo S\u00e9 rgio Almeida, Carlos Baquero, Nuno Preguicc a, and David Hutchison. 2007. Scalable Bloom Filters. Inform. Process. Lett. (2007)."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629577"},{"key":"e_1_2_2_3_1","unstructured":"Apache. 2023 a. Cassandra. http:\/\/cassandra.apache.org (2023)."},{"key":"e_1_2_2_4_1","unstructured":"Apache. 2023 b. HBase. http:\/\/hbase.apache.org\/ (2023)."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465296"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"R. Barber G. Lohman I. Pandis V. Raman R. Sidle G. Attaluri N. Chainani S. Lightstone and D. Sharpe. 2014. Memory-Efficient Hash Joins. VLDB (2014).","DOI":"10.14778\/2735496.2735499"},{"key":"e_1_2_2_7_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_2_8_1","unstructured":"Ioana O Bercea and Guy Even. 2020. Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses. SWAT."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Flavio Bonomi Michael Mitzenmacher Rina Panigrahy Sushil Singh and George Varghese. 2006. An Improved Construction for Counting Bloom Filters. In ESA.","DOI":"10.1007\/11841036_61"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213884"},{"key":"e_1_2_2_12_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, Vol. 1 (2002), 636--646.","journal-title":"Internet Mathematics"},{"key":"e_1_2_2_13_1","volume-title":"Lang","author":"Canim Mustafa","year":"2010","unstructured":"Mustafa Canim, George A. Mihaila, Bishwaranjan Bhattacharjee, Kenneth A. Ross, and Christian A. Lang. 2010. SSD Bufferpool Extensions for Database Systems. PVLDB (2010)."},{"key":"e_1_2_2_14_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_2_15_1","doi-asserted-by":"crossref","unstructured":"Pedro Celis Per-Ake Larson and J Ian Munro. 1985. Robin Hood Hashing. In FOCS.","DOI":"10.1109\/SFCS.1985.48"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196898"},{"key":"e_1_2_2_17_1","doi-asserted-by":"crossref","unstructured":"Hanhua Chen Liangyi Liao Hai Jin and Jie Wu. 2017. The Dynamic Cuckoo Filter. In ICNP.","DOI":"10.1109\/ICNP.2017.8117563"},{"key":"e_1_2_2_18_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_2_19_1","volume-title":"Benchmarking Cloud Serving Systems with YCSB. SoCC","author":"Cooper Brian F.","year":"2010","unstructured":"Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking Cloud Serving Systems with YCSB. SoCC (2010)."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276980"},{"key":"e_1_2_2_22_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_2_23_1","doi-asserted-by":"crossref","unstructured":"Niv Dayan and Stratos Idreos. 2019. The Log-Structured Merge-Bush & the Wacky Continuum. In SIGMOD.","DOI":"10.1145\/3299869.3319903"},{"key":"e_1_2_2_24_1","volume-title":"Chucky: A Succinct Cuckoo Filter for LSM-Tree. In SIGMOD.","author":"Dayan Niv","year":"2021","unstructured":"Niv Dayan and Moshe Twitto. 2021. Chucky: A Succinct Cuckoo Filter for LSM-Tree. In SIGMOD."},{"key":"e_1_2_2_25_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. VLDB (2021)."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551853"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1921015"},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Biplob Debnath Sudipta Sengupta Jin Li David J Lilja and David HC Du. 2011. BloomFlash: Bloom filter on Flash-Based Storage. In ICDCS.","DOI":"10.1109\/ICDCS.2011.44"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436919"},{"key":"e_1_2_2_30_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_2_31_1","volume-title":"Dillinger and Panagiotis Manolios","author":"Peter","year":"2004","unstructured":"Peter C. Dillinger and Panagiotis Manolios. 2004. Bloom Filters in Probabilistic Verification. FMCAD (2004)."},{"key":"e_1_2_2_32_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. In SPIN."},{"key":"e_1_2_2_33_1","volume-title":"Optimizing Space Amplification in RocksDB. CIDR","author":"Dong Siying","year":"2017","unstructured":"Siying Dong, Mark Callaghan, Leonidas Galanis, Dhruba Borthakur, Tony Savor, and Michael Strum. 2017. Optimizing Space Amplification in RocksDB. CIDR (2017)."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2017.2685530"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523211"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_2_37_1","volume-title":"Broder","author":"Fan Li","year":"2000","unstructured":"Li Fan, Pei Cao, Jussara Almeida, and Andrei Z. Broder. 2000. Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol. IEEE ACM Trans Netw (2000)."},{"key":"e_1_2_2_38_1","volume-title":"Bloom filter Applications in Network Security: A State-of-the-Art Survey. Comput Netw","author":"Geravand Shahabeddin","year":"2013","unstructured":"Shahabeddin Geravand and Mahmood Ahmadi. 2013. Bloom filter Applications in Network Security: A State-of-the-Art Survey. Comput Netw (2013)."},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Bob Goodwin Michael Hopcroft Dan Luu Alex Clemmer Mihaela Curmei Sameh Elnikety and Yuxiong He. 2017. BitFunnel: Revisiting Signatures for Search. In SIGIR.","DOI":"10.1145\/3077136.3080789"},{"key":"e_1_2_2_40_1","volume-title":"https:\/\/github.com\/google\/leveldb\/","author":"DB.","year":"2023","unstructured":"Google. 2023. LevelDB. https:\/\/github.com\/google\/leveldb\/ (2023)."},{"key":"e_1_2_2_41_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. In SODA."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000028"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3376122"},{"key":"e_1_2_2_44_1","doi-asserted-by":"crossref","unstructured":"Deke Guo Jie Wu Honghui Chen and Xueshan Luo. 2006. Theory and Network Applications of Dynamic Bloom Filters. In INFOCOM.","DOI":"10.1109\/INFOCOM.2006.325"},{"key":"e_1_2_2_45_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_2_46_1","unstructured":"HBase. 2013. Online reference. http:\/\/hbase.apache.org\/ (2013)."},{"key":"e_1_2_2_47_1","unstructured":"Stratos Idreos Niv Dayan Wilson Qin Mali Akmanalp Sophie Hilgard Andrew Ross James Lennon Varun Jain Harshita Gupta David Li et al. 2019b. Learning Key-Value Store Design. arXiv preprint arXiv:1907.05443 (2019)."},{"key":"e_1_2_2_48_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. 2019a. Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn. In CIDR."},{"key":"e_1_2_2_49_1","volume-title":"The Periodic Table of Data Structures","author":"Idreos Stratos","year":"2018","unstructured":"Stratos Idreos, Kostas Zoumpatianos, Manos Athanassoulis, Niv Dayan, Brian Hentschel, Michael S. Kester, Demi Guo, Lukas M. Maas, Wilson Qin, Abdul Wasay, and Yiyou Sun. 2018. The Periodic Table of Data Structures. IEEE DEBULL (2018)."},{"key":"e_1_2_2_50_1","volume-title":"Learning Data Structure Alchemy","author":"Idreos Stratos","year":"2019","unstructured":"Stratos Idreos, Kostas Zoumpatianos, Subarna Chatterjee, Wilson Qin, Abdul Wasay, Brian Hentschel, Mike Kester, Niv Dayan, Demi Guo, Minseo Kang, and Yiyou Sun. 2019c. Learning Data Structure Alchemy. IEEE DEBULL (2019)."},{"key":"e_1_2_2_51_1","volume-title":"Less Hashing","author":"Kirsch Adam","year":"2008","unstructured":"Adam Kirsch and Michael Mitzenmacher. 2008. Less Hashing, Same Performance: Building a Better Bloom Filter. Random Struct Algorithms (2008)."},{"key":"e_1_2_2_52_1","volume-title":"Proteus: A Self-Designing Range Filter. In 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. In SIGMOD."},{"key":"e_1_2_2_53_1","volume-title":"Coconut: A Scalable Bottom-Up Approach for Building Data Series Indexes. PVLDB","author":"Kondylakis Haridimos","year":"2018","unstructured":"Haridimos Kondylakis, Niv Dayan, Kostas Zoumpatianos, and Themis Palpanas. 2018. Coconut: A Scalable Bottom-Up Approach for Building Data Series Indexes. PVLDB (2018)."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320233"},{"key":"e_1_2_2_55_1","volume-title":"Coconut: Sortable Summarizations for Scalable Indexes over Static and Streaming Data Series. VLDBJ","author":"Kondylakis Haridimos","year":"2019","unstructured":"Haridimos Kondylakis, Niv Dayan, Kostas Zoumpatianos, and Themis Palpanas. 2019b. Coconut: Sortable Summarizations for Scalable Indexes over Static and Streaming Data Series. VLDBJ (2019)."},{"key":"e_1_2_2_56_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_2_57_1","doi-asserted-by":"crossref","unstructured":"Avinash Lakshman and Prashant Malik. 2010. Cassandra - A Decentralized Structured Storage System. SIGOPS Op. Sys. Rev. (2010).","DOI":"10.1145\/1583991.1584009"},{"key":"e_1_2_2_58_1","doi-asserted-by":"crossref","unstructured":"Harald Lang Thomas Neumann Alfons Kemper and Peter Boncz. 2019. Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput. In VLDB.","DOI":"10.14778\/3303753.3303757"},{"key":"e_1_2_2_59_1","unstructured":"Mingmou Liu Yitong Yin and Huacheng Yu. 2020. Succinct Filters for Sets of Unknown Sizes. In ICALP."},{"key":"e_1_2_2_60_1","volume-title":"Du","author":"Lu Guanlin","year":"2011","unstructured":"Guanlin Lu, Biplob Debnath, and David H. C. Du. 2011. A Forest-Structured Bloom Filter with Flash Memory. MSST (2011)."},{"key":"e_1_2_2_61_1","volume-title":"Ultra-Fast Bloom Filters Using SIMD Techniques. TPDS","author":"Lu Jianyuan","year":"2018","unstructured":"Jianyuan Lu, Ying Wan, Yang Li, Chuwen Zhang, Huichen Dai, Yi Wang, Gong Zhang, and Bin Liu. 2018. Ultra-Fast Bloom Filters Using SIMD Techniques. TPDS (2018)."},{"key":"e_1_2_2_62_1","volume-title":"Umzi: Unified Multi-Zone Indexing for Large-Scale HTAP. In EDBT.","author":"Luo Chen","year":"2019","unstructured":"Chen Luo, Pinar T\u00f6z\u00fcn, Yuanyuan Tian, Ronald Barber, Vijayshankar Raman, and Richard Sidle. 2019b. Umzi: Unified Multi-Zone Indexing for Large-Scale HTAP. In EDBT."},{"key":"e_1_2_2_63_1","volume-title":"Ori Rottenstreich, and Xueshan Luo.","author":"Luo Lailong","year":"2018","unstructured":"Lailong Luo, Deke Guo, Richard TB Ma, Ori Rottenstreich, and Xueshan Luo. 2018. Optimizing Bloom filter: Challenges, solutions, and comparisons. IEEE Commun. Surv. Tutor. (2018)."},{"key":"e_1_2_2_64_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. 2019a. The Consistent Cuckoo Filter. In INFOCOM."},{"key":"e_1_2_2_65_1","volume-title":"Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores. In 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. In SIGMOD."},{"key":"e_1_2_2_66_1","unstructured":"Meta. 2023 a. MyRocks. http:\/\/myrocks.io\/ (2023)."},{"key":"e_1_2_2_67_1","volume-title":"2023 b. RocksDB. https:\/\/github.com\/facebook\/rocksdb","year":"2023","unstructured":"Meta. 2023 b. RocksDB. https:\/\/github.com\/facebook\/rocksdb (2023)."},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.803864"},{"key":"e_1_2_2_69_1","series-title":"SIAM ALENEX.","volume-title":"Adaptive cuckoo filters","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher, Salvatore Pontarelli, and Pedro Reviriego. 2018. Adaptive cuckoo filters. In SIAM ALENEX."},{"key":"e_1_2_2_70_1","volume-title":"O'Neil","author":"O'Neil Patrick E.","year":"1996","unstructured":"Patrick E. O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth J. O'Neil. 1996. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica (1996)."},{"key":"e_1_2_2_71_1","doi-asserted-by":"crossref","unstructured":"Rasmus Pagh Gil Segev and Udi Wieder. 2013. How to Approximate a Set Without Knowing its Size in Advance. In FOCS.","DOI":"10.1109\/FOCS.2013.17"},{"key":"e_1_2_2_72_1","doi-asserted-by":"crossref","unstructured":"Prashant Pandey Michael A Bender Rob Johnson and Rob Patro. 2017. A General-Purpose Counting Filter: Making Every Bit Count. In SIGMOD.","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_2_2_73_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_2_74_1","volume-title":"Ross","author":"Polychroniou Orestis","year":"2014","unstructured":"Orestis Polychroniou and Kenneth A. Ross. 2014. Vectorized Bloom filters for advanced SIMD processors. DAMON (2014)."},{"key":"e_1_2_2_75_1","doi-asserted-by":"crossref","unstructured":"Felix Putze Peter Sanders and Johannes Singler. 2010. Cache- Hash- and Space-Efficient Bloom Filters. JEA (2010).","DOI":"10.1145\/1498698.1594230"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151108"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.21236\/ADA604306"},{"key":"e_1_2_2_78_1","volume-title":"The Deletable Bloom Filter: a New Member of the Bloom Family","author":"Rothenberg Christian Esteve","year":"2010","unstructured":"Christian Esteve Rothenberg, Carlos Macapuna, Fabio Verdi, and Mauricio Magalhaes. 2010. The Deletable Bloom Filter: a New Member of the Bloom Family. IEEE Commun. Lett (2010)."},{"key":"e_1_2_2_79_1","volume-title":"The Variable-Increment Counting Bloom Filter","author":"Rottenstreich Ori","year":"2013","unstructured":"Ori Rottenstreich, Yossi Kanizo, and Isaac Keslassy. 2013. The Variable-Increment Counting Bloom Filter. IEEE ACM Trans Netw (2013)."},{"key":"e_1_2_2_80_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_2_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_2_82_1","doi-asserted-by":"crossref","unstructured":"Dimitrios Skarlatos Apostolos Kokolis Tianyin Xu and Josep Torrellas. 2020. Elastic Cuckoo Page Tables: Rethinking Virtual Memory Translation for Parallelism. In ASPLOS.","DOI":"10.1145\/3373376.3378493"},{"key":"e_1_2_2_83_1","volume-title":"https:\/\/github.com\/speedb-io\/speedb","year":"2023","unstructured":"Speedb. 2023. Speedb. https:\/\/github.com\/speedb-io\/speedb (2023)."},{"key":"e_1_2_2_84_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007276"},{"key":"e_1_2_2_85_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_2_86_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529347"},{"key":"e_1_2_2_87_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364333"},{"key":"e_1_2_2_89_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_2_90_1","doi-asserted-by":"crossref","unstructured":"Kun Xie Yinghua Min Dafang Zhang Jigang Wen and Gaogang Xie. 2007. A Scalable Bloom Filter for Membership Queries. In GLOBECOM.","DOI":"10.1109\/GLOCOM.2007.107"},{"key":"e_1_2_2_91_1","doi-asserted-by":"publisher","DOI":"10.1109\/OJCS.2022.3219631"},{"key":"e_1_2_2_92_1","doi-asserted-by":"crossref","unstructured":"Fan Zhang Hanhua Chen Hai Jin and Pedro Reviriego. 2021. The Logarithmic Dynamic Cuckoo Filter. In ICDE.","DOI":"10.1109\/ICDE51399.2021.00087"},{"key":"e_1_2_2_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589285","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589285","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:54Z","timestamp":1750182534000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":92,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589285"],"URL":"https:\/\/doi.org\/10.1145\/3589285","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}