{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T18:02:35Z","timestamp":1780941755719,"version":"3.54.1"},"reference-count":60,"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>With a single Bloom filter, one can approximately answer set membership queries within a space budget. Practical systems often use collections of Bloom filters to facilitate applications such as data skipping, sideways information passing, and network filtering. While the optimal space-to-accuracy allocation is well-understood for a single filter, jointly optimizing how space is used across a collection of filters is yet to be studied. We pose this problem in the following way: (1) let's assume that each Bloom filter has some likelihood of being queried, and (2) given knowledge of this likelihood, how do we allocate space to minimize the expected false positive rate? In other words, \"hot\" filters are allocated more space, and \"cold\" filters are allocated less space. In this paper, we show how to solve this optimization problem. We first develop the concept of a \"truncated\" Bloom filter and theoretically analyze its false positive rate. We then formulate an optimization problem for a collection of truncated Bloom filters that minimizes the false positive rate across a utility distribution while meeting a strict space budget. Next, we show that the problem is convex and find a fast relaxation. Lastly, we apply our method to data skipping and full-text search, demonstrating its effectiveness across the range of possible space budgets when compared to the state of the art.<\/jats:p>","DOI":"10.14778\/3681954.3682020","type":"journal-article","created":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T16:23:36Z","timestamp":1725035016000},"page":"3551-3564","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Optimizing Collections of Bloom Filters within a Space Budget"],"prefix":"10.14778","volume":"17","author":[{"given":"Gabriel","family":"Mersy","sequence":"first","affiliation":[{"name":"The University of Chicago"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhuo","family":"Wang","sequence":"additional","affiliation":[{"name":"The University of Chicago"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stavros","family":"Sintos","sequence":"additional","affiliation":[{"name":"University of Illinois Chicago"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjay","family":"Krishnan","sequence":"additional","affiliation":[{"name":"The University of Chicago"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,8,30]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"murmurhash3. Retrieved","author":"Appleby Austin","year":"2024","unstructured":"Austin Appleby. 2015. murmurhash3. Retrieved January 9, 2024 from https:\/\/github.com\/aappleby\/smhasher\/blob\/master\/src\/MurmurHash3.cpp"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415560"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588953"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_2_1_5_1","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","author":"Berg Benjamin","unstructured":"Benjamin Berg, Daniel S. Berger, Sara McAllister, Isaac Grosof, Sathya Gunasekar, Jimmy Lu, Michael Uhlar, Jim Carrig, Nathan Beckmann, Mor Harchol-Balter, and Gregory R. Ganger. 2020. The CacheLib Caching Engine: Design and Experiences at Scale. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). USENIX Association, Berkeley, CA, USA, 753--768. https:\/\/www.usenix.org\/conference\/osdi20\/presentation\/berg"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.05.018"},{"key":"e_1_2_1_8_1","volume-title":"Convex optimization","author":"Boyd Stephen P","unstructured":"Stephen P Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press, New York, NY, USA."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/lnms\/1215466757"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms","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 (New Orleans, Louisiana) (SODA '04). Society for Industrial and Applied Mathematics, USA, 30--39."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 11th International Conference on Very Large Data Bases -","volume":"11","author":"Chou Hong-Tai","unstructured":"Hong-Tai Chou and David J. DeWitt. 1985. An Evaluation of Buffer Management Strategies for Relational Database Systems. In Proceedings of the 11th International Conference on Very Large Data Bases - Volume 11 (VLDB '85). VLDB Endowment, Stockholm, Sweden, 127--141."},{"key":"e_1_2_1_13_1","volume-title":"Understanding ClickHouse Data Skipping Indexes. Retrieved","year":"2024","unstructured":"Clickhouse. 2024. Understanding ClickHouse Data Skipping Indexes. Retrieved January 9, 2024 from https:\/\/clickhouse.com\/docs\/en\/optimize\/skipping-indexes"},{"key":"e_1_2_1_14_1","first-page":"2001","volume-title":"Retrieved","author":"State of Connecticut.","year":"2023","unstructured":"State of Connecticut. 2023. Real Estate Sales 2001-2020 GL. Retrieved January 10, 2024 from https:\/\/catalog.data.gov\/dataset\/real-estate-sales-2001-2018"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588726"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2903741"},{"key":"e_1_2_1_18_1","volume-title":"Bloom filter indexes. Retrieved","year":"2024","unstructured":"Databricks. 2023. Bloom filter indexes. Retrieved January 9, 2024 from https:\/\/docs.databricks.com\/en\/optimizations\/bloom-filters.html"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589285"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457273"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436919"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2946645.3007036"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.23919\/ECC.2013.6669541"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554842"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3077136.3080789"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3424573.3424577"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_30_1","volume-title":"Retrieved","author":"Lawrence Berkeley National Laboratory.","year":"1995","unstructured":"Lawrence Berkeley National Laboratory. 1995. NASA-HTTP. Retrieved January 10, 2024 from https:\/\/ita.ee.lbl.gov\/html\/contrib\/NASA-HTTP.html"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544811"},{"key":"e_1_2_1_32_1","volume-title":"ElasticBF: Elastic Bloom Filter with Hotness Awareness for Boosting Read Performance in Large Key-Value Stores. In 2019 USENIX Annual Technical Conference (USENIX ATC 19)","author":"Li Yongkun","year":"2019","unstructured":"Yongkun Li, Chengjin Tian, Fan Guo, Cheng Li, and Yinlong Xu. 2019. ElasticBF: Elastic Bloom Filter with Hotness Awareness for Boosting Read Performance in Large Key-Value Stores. In 2019 USENIX Annual Technical Conference (USENIX ATC 19). USENIX Association, Renton, WA, 739--752. https:\/\/www.usenix.org\/system\/files\/atc19-li-yongkun.pdf"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407830"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.803864"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_2_1_36_1","volume-title":"LSM-Trees Under (Memory) Pressure. In Thirteenth International Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures (ADMS 2022","author":"Mun Ju Hyoung","year":"2022","unstructured":"Ju Hyoung Mun, Zichen Zhu, Aneesh Raman, and Manos Athanassoulis. 2022. LSM-Trees Under (Memory) Pressure. In Thirteenth International Workshop on Accelerating Analytics and Data Management Systems Using Modern Processor and Storage Architectures (ADMS 2022). Sydney, Australia, 23--35. https:\/\/www.adms-conf.org\/2022-camera-ready\/ADMS22_mun.pdf"},{"key":"e_1_2_1_37_1","volume-title":"Retrieved","author":"Ni Jianmo","year":"2018","unstructured":"Jianmo Ni. 2018. Amazon Review Data (2018). Retrieved January 10, 2024 from https:\/\/cseweb.ucsd.edu\/~jmcauley\/datasets\/amazon_v2\/"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D19-1018"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609615"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452841"},{"key":"e_1_2_1_42_1","volume-title":"bloom --- bloom filter index access method. Retrieved","author":"SQL.","year":"2024","unstructured":"PostgreSQL. 2024. F.7. bloom --- bloom filter index access method. Retrieved January 9, 2024 from https:\/\/www.postgresql.org\/docs\/current\/bloom.html"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1594230"},{"key":"e_1_2_1_44_1","volume-title":"Bloom filter. Retrieved","year":"2024","unstructured":"Redis. 2024. Bloom filter. Retrieved January 9, 2024 from https:\/\/redis.io\/docs\/data-types\/probabilistic\/bloom-filter\/"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151108"},{"key":"e_1_2_1_46_1","volume-title":"bitarray. Retrieved","author":"Schnell Ilan","year":"2024","unstructured":"Ilan Schnell. 2023. bitarray. Retrieved January 9, 2024 from https:\/\/pypi.org\/project\/bitarray\/"},{"key":"e_1_2_1_47_1","first-page":"165","article-title":"On the Dispersion of Mixtures","volume":"9","author":"Schweder Tore","year":"1982","unstructured":"Tore Schweder. 1982. On the Dispersion of Mixtures. Scandinavian Journal of Statistics 9, 3 (1982), 165--169. http:\/\/www.jstor.org\/stable\/4615873","journal-title":"Scandinavian Journal of Statistics"},{"key":"e_1_2_1_48_1","volume-title":"Amazon Redshift now leverages Bloom filters to improve data lake query performance by up to 2x. Retrieved","author":"Services Amazon Web","year":"2024","unstructured":"Amazon Web Services. 2020. Amazon Redshift now leverages Bloom filters to improve data lake query performance by up to 2x. Retrieved January 9, 2024 from https:\/\/aws.amazon.com\/about-aws\/whats-new\/2020\/05\/amazon-redshift-now-leverages-bloom-filters-to-improve-data-lake-query-performance\/"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1980.tb01118.x"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.3442"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083658"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598601"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610515"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData50022.2020.9377740"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452811"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611520"},{"key":"e_1_2_1_57_1","volume-title":"Retrieved","author":"State of Washington.","year":"2023","unstructured":"State of Washington. 2023. Electric Vehicle Population Data. Retrieved January 10, 2024 from https:\/\/catalog.data.gov\/dataset\/electric-vehicle-population-data"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367550"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/647055.715773"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3090163.3090167"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3681954.3682020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:28:24Z","timestamp":1725474504000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3681954.3682020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":60,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.14778\/3681954.3682020"],"URL":"https:\/\/doi.org\/10.14778\/3681954.3682020","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"}}]}}