{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:55:27Z","timestamp":1775638527958,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:p>\n            Many applications of approximate membership query data structures, or\n            <jats:italic>filters<\/jats:italic>\n            , require only an\n            <jats:italic>incremental<\/jats:italic>\n            filter that supports insertions but not deletions. However, the design space of incremental filters is missing a \"sweet spot\" filter that combines space efficiency, fast queries, and fast insertions. Incremental filters, such as the Bloom and blocked Bloom filter, are not space efficient. Dynamic filters (i.e., supporting deletions), such as the cuckoo or vector quotient filter, are space efficient but do not exhibit consistently fast insertions and queries.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we propose the\n            <jats:italic>prefix filter<\/jats:italic>\n            , an incremental filter that addresses the above challenge: (1) its space (in bits) is similar to state-of-the-art dynamic filters; (2) query throughput is high and is comparable to that of the cuckoo filter; and (3) insert throughput is high with overall build times faster than those of the vector quotient filter and cuckoo filter by 1.39X--1.46X and 3.2X--3.5X, respectively. We present a rigorous analysis of the prefix filter that holds also for practical set sizes (i.e.,\n            <jats:italic>n<\/jats:italic>\n            = 2\n            <jats:sup>25<\/jats:sup>\n            ). The analysis deals with the probability of failure, false positive rate, and probability that an operation requires accessing more than a single cache line.\n          <\/jats:p>","DOI":"10.14778\/3523210.3523211","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T22:23:21Z","timestamp":1655936601000},"page":"1311-1323","source":"Crossref","is-referenced-by-count":14,"title":["Prefix filter"],"prefix":"10.14778","volume":"15","author":[{"given":"Tomer","family":"Even","sequence":"first","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Even","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Morrison","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2021. Intel Architecture Instruction Set Extensions and Future Features. https:\/\/software.intel.com\/sites\/default\/files\/managed\/c5\/15\/architecture-instruction-set-extensions-programming-reference.pdf.  2021. Intel Architecture Instruction Set Extensions and Future Features. https:\/\/software.intel.com\/sites\/default\/files\/managed\/c5\/15\/architecture-instruction-set-extensions-programming-reference.pdf."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304062"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.80"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254766"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_2_1_6_1","volume-title":"Bercea and Guy Even","author":"Ioana","year":"2019","unstructured":"Ioana O. Bercea and Guy Even . 2019 . Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses. CoRR abs\/1911.05060 (2019). arXiv:1911.05060 http:\/\/arxiv.org\/abs\/1911.05060 Ioana O. Bercea and Guy Even. 2019. Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses. CoRR abs\/1911.05060 (2019). arXiv:1911.05060 http:\/\/arxiv.org\/abs\/1911.05060"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SWAT.2020.11"},{"key":"e_1_2_1_8_1","volume-title":"Bercea and Guy Even","author":"Ioana","year":"2020","unstructured":"Ioana O. Bercea and Guy Even . 2020 . A Dynamic Space-Efficient Filter with Constant Time Operations. CoRR abs\/2005.01098 (2020). arXiv:2005.01098 https:\/\/arxiv.org\/abs\/2005.01098 Ioana O. Bercea and Guy Even. 2020. A Dynamic Space-Efficient Filter with Constant Time Operations. CoRR abs\/2005.01098 (2020). arXiv:2005.01098 https:\/\/arxiv.org\/abs\/2005.01098"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645912.671296"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213884"},{"key":"e_1_2_1_12_1","volume-title":"18th USENIX Conference on File and Storage Technologies (FAST 20)","author":"Cao Zhichao","unstructured":"Zhichao Cao , Siying Dong , Sagar Vemuri , and David H.C. Du . 2020. Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook . In 18th USENIX Conference on File and Storage Technologies (FAST 20) . 209--223. Zhichao Cao, Siying Dong, Sagar Vemuri, and David H.C. Du. 2020. Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook. In 18th USENIX Conference on File and Storage Technologies (FAST 20). 209--223."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804332"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_15_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Conway Alex","year":"2018","unstructured":"Alex Conway , Martin Farach-Colton , and Philip Shilane . 2018 . Optimal Hashing in External Memory. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). 39:1--39:14. Alex Conway, Martin Farach-Colton, and Philip Shilane. 2018. Optimal Hashing in External Memory. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). 39:1--39:14."},{"key":"e_1_2_1_16_1","volume-title":"SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores. In 2020 USENIX Annual Technical Conference (USENIX ATC 20)","author":"Conway Alexander","year":"2020","unstructured":"Alexander Conway , Abhishek Gupta , Vijay Chidambaram , Martin Farach-Colton , Richard Spillane , Amy Tai , and Rob Johnson . 2020 . SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores. In 2020 USENIX Annual Technical Conference (USENIX ATC 20) . 49--63. Alexander Conway, Abhishek Gupta, Vijay Chidambaram, Martin Farach-Colton, Richard Spillane, Amy Tai, and Rob Johnson. 2020. SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores. In 2020 USENIX Annual Technical Conference (USENIX ATC 20). 49--63."},{"key":"e_1_2_1_17_1","unstructured":"Graham Cormode Minos Garofalakis Peter J. Haas and Chris Jermaine. 2011. . Now Foundations and Trends.  Graham Cormode Minos Garofalakis Peter J. Haas and Chris Jermaine. 2011. . Now Foundations and Trends."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196927"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457273"},{"key":"e_1_2_1_21_1","unstructured":"Martin Dietzfelbinger. [n.d.]. Universal Hashing via Integer Arithmetic Without Primes Revisited.  Martin Dietzfelbinger. [n.d.]. Universal Hashing via Integer Arithmetic Without Primes Revisited."},{"key":"e_1_2_1_22_1","first-page":"3","article-title":"Optimizing Space Amplification in RocksDB","volume":"3","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 . In CIDR , Vol. 3. 3 . Siying Dong, Mark Callaghan, Leonidas Galanis, Dhruba Borthakur, Tony Savor, and Michael Strum. 2017. Optimizing Space Amplification in RocksDB. In CIDR, Vol. 3. 3.","journal-title":"CIDR"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2017.2685530"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"e_1_2_1_25_1","volume-title":"Prefix Filter: Practically and Theoretically Better Than Bloom. arXiv e-prints abs\/2203.17139","author":"Even Tomer","year":"2022","unstructured":"Tomer Even , Guy Even , and Adam Morrison . 2022 . Prefix Filter: Practically and Theoretically Better Than Bloom. arXiv e-prints abs\/2203.17139 (2022). arXiv:2203.17139 [cs.DS] http:\/\/arxiv.org\/abs\/2203.17139 Tomer Even, Guy Even, and Adam Morrison. 2022. Prefix Filter: Practically and Theoretically Better Than Bloom. arXiv e-prints abs\/2203.17139 (2022). arXiv:2203.17139 [cs.DS] http:\/\/arxiv.org\/abs\/2203.17139"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Bin Fan David G. Andersen and Michael Kaminsky. 2014. Cuckoo Filter C++ implementation. https:\/\/github.com\/efficient\/cuckoofilter  Bin Fan David G. Andersen and Michael Kaminsky. 2014. Cuckoo Filter C++ implementation. https:\/\/github.com\/efficient\/cuckoofilter","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_28_1","volume-title":"On the number of bits required to implement an associative memory. Memorandum 61","author":"Fano Robert Mario","year":"1971","unstructured":"Robert Mario Fano . 1971. On the number of bits required to implement an associative memory. Memorandum 61 . Computer Structures Group , Project MAC, MIT, Cambridge, Mass. ( 1971 ). Robert Mario Fano. 1971. On the number of bits required to implement an associative memory. Memorandum 61. Computer Structures Group, Project MAC, MIT, Cambridge, Mass. (1971)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741973"},{"key":"e_1_2_1_30_1","volume-title":"Fast Filter: Fast approximate membership filter implementations (C++). https:\/\/github.com\/FastFilter\/fastfilter_cpp","author":"Graf Thomas Mueller","year":"2018","unstructured":"Thomas Mueller Graf and Daniel Lemire . 2018 . Fast Filter: Fast approximate membership filter implementations (C++). https:\/\/github.com\/FastFilter\/fastfilter_cpp Thomas Mueller Graf and Daniel Lemire. 2018. Fast Filter: Fast approximate membership filter implementations (C++). https:\/\/github.com\/FastFilter\/fastfilter_cpp"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3376122"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_33_1","volume-title":"Searching and sorting. Reading MA: Addison-Wisley","author":"Knuth Donald E","year":"1973","unstructured":"Donald E Knuth . 1973. The art of computer programming , vol. 3 : Searching and sorting. Reading MA: Addison-Wisley ( 1973 ). Donald E Knuth. 1973. The art of computer programming, vol. 3: Searching and sorting. Reading MA: Addison-Wisley (1973)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592820"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00555-y"},{"key":"e_1_2_1_37_1","volume-title":"Faster Population Counts using AVX2 Instructions. CoRR abs\/1611.07612","author":"Mula Wojciech","year":"2016","unstructured":"Wojciech Mula , Nathan Kurz , and Daniel Lemire . 2016. Faster Population Counts using AVX2 Instructions. CoRR abs\/1611.07612 ( 2016 ). arXiv:1611.07612 http:\/\/arxiv.org\/abs\/1611.07612 Wojciech Mula, Nathan Kurz, and Daniel Lemire. 2016. Faster Population Counts using AVX2 Instructions. CoRR abs\/1611.07612 (2016). arXiv:1611.07612 http:\/\/arxiv.org\/abs\/1611.07612"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_1_40_1","volume-title":"A Fast x86 Implementation of Select. CoRR abs\/1706.00990","author":"Pandey Prashant","year":"2017","unstructured":"Prashant Pandey , Michael A. Bender , and Rob Johnson . 2017. A Fast x86 Implementation of Select. CoRR abs\/1706.00990 ( 2017 ). arXiv:1706.00990 http:\/\/arxiv.org\/abs\/1706.00990 Prashant Pandey, Michael A. Bender, and Rob Johnson. 2017. A Fast x86 Implementation of Select. CoRR abs\/1706.00990 (2017). arXiv:1706.00990 http:\/\/arxiv.org\/abs\/1706.00990"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452841"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Prashant Pandey Alex Conway and Rob Johnson. 2021. Vector Quotient Filter C++ implementation. https:\/\/github.com\/splatlab\/vqf  Prashant Pandey Alex Conway and Rob Johnson. 2021. Vector Quotient Filter C++ implementation. https:\/\/github.com\/splatlab\/vqf","DOI":"10.1145\/3448016.3452841"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2021.101756"},{"key":"e_1_2_1_44_1","first-page":"4","article-title":"Cache-, hash-, and space-efficient bloom filters","volume":"14","author":"Putze Felix","year":"2010","unstructured":"Felix Putze , Peter Sanders , and Johannes Singler . 2010 . Cache-, hash-, and space-efficient bloom filters . Journal of Experimental Algorithmics (JEA) 14 (2010), 4 -- 4 . Felix Putze, Peter Sanders, and Johannes Singler. 2010. Cache-, hash-, and space-efficient bloom filters. Journal of Experimental Algorithmics (JEA) 14 (2010), 4--4.","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132765"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151108"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592804"},{"key":"e_1_2_1_49_1","unstructured":"Maysam Yabandeh. 2017. Partitioned Index\/Filters. https:\/\/rocksdb.org\/blog\/2017\/05\/12\/partitioned-index-filter.html.  Maysam Yabandeh. 2017. Partitioned Index\/Filters. https:\/\/rocksdb.org\/blog\/2017\/05\/12\/partitioned-index-filter.html."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3523210.3523211","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:48:26Z","timestamp":1672224506000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3523210.3523211"}},"subtitle":["practically and theoretically better than bloom"],"short-title":[],"issued":{"date-parts":[[2022,3]]},"references-count":49,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["10.14778\/3523210.3523211"],"URL":"https:\/\/doi.org\/10.14778\/3523210.3523211","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,3]]}}}