Optimizing Collections of Bloom Filters within a Space Budget

Summary: Optimizes space allocation across queried Bloom-filter collections: introduces truncated filters, a convex utility-weighted formulation, and a fast relaxation that improves false positives for data skipping and full-text search under strict budgets. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hdb23cf7ffba8011a
Venue: VLDB
Year: 2024
Pagerank: 5.5222465e-05
Overall Rank: 7,383 | 50.52%
DOI: 10.14778/3681954.3682020
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Gabriel Mersy (University of Chicago)
2. Zhuo Wang (University of Chicago)
3. Stavros Sintos (University of Illinois Chicago)
4. Sanjay Krishnan (University of Chicago)

BibTeX Citation

@article{mersy_vldb24,
        title = {{Optimizing Collections of Bloom Filters within a Space Budget}},
        author = {Mersy, Gabriel and Wang, Zhuo and Sintos, Stavros and Krishnan, Sanjay},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {11},
        pages = {3551--3564},
        doi = {10.14778/3681954.3682020},
        url = {https://doi.org/10.14778/3681954.3682020},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,666	Mnemosyne: Dynamic Workload-Aware BF Tuning via Accurate Statistics in LSM trees	2025	SIGMOD	5.277223e-05
10,065	Towards Functional Decomposition of Storage Formats	2025	CIDR	5.0749178e-05
10,985	Reaching the Pinnacle of TPC-DS: Co-design of Architecture, Executor, and Storage in TDSQL	2026	VLDB	4.9605343e-05
11,130	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 23 of 23 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00068985264
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046249672
52	The Snowflake Elastic Data Warehouse	2016	SIGMOD	0.00041439488
126	An Evaluation of Buffer Management Strategies for Relational Database Systems	1985	VLDB	0.00030358639
402	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00019070605
462	Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores	2020	VLDB	0.00017825062
791	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.00013927839
814	SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data	2017	VLDB	0.00013697533
1,039	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00012349128
1,991	Chucky: A Succinct Cuckoo Filter for LSM-Tree	2021	SIGMOD	9.2264312e-05
2,081	A General-Purpose Counting Filter: Making Every Bit Count	2017	SIGMOD	9.0581443e-05
3,602	Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads	2017	VLDB	7.1572829e-05
3,692	SplinterDB and Maplets: Improving the Tradeoffs in Key-Value Store Compaction Policy	2023	SIGMOD	7.0761873e-05
3,709	Stable Learned Bloom Filters for Data Streams	2020	VLDB	7.0586477e-05
3,720	Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design	2021	SIGMOD	7.0516727e-05
4,646	Stacked Filters: Learning to Filter by Structure	2021	VLDB	6.4725846e-05
4,773	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.4102054e-05
4,777	SQLite: Past, Present, and Future	2022	VLDB	6.4075995e-05
5,082	InfiniFilter: Expanding Filters to Infinity and Beyond	2023	SIGMOD	6.2679091e-05
5,856	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.9514226e-05
6,700	Hierarchical Residual Encoding for Multiresolution Time Series Compression	2023	SIGMOD	5.6877938e-05
8,222	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.3585489e-05
8,604	Conditional Cuckoo Filters	2021	SIGMOD	5.2899825e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,646	Stacked Filters: Learning to Filter by Structure	2021	VLDB
2	3,559	Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters	2006	SIGMOD
3	6,958	A Shifting Bloom Filter Framework for Set Queries	2016	VLDB
4	3,297	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB
5	11,931	New Wine in an Old Bottle: Data-Aware Hash Functions for Bloom Filters	2022	VLDB
6	6,205	Prefix Filter: Practically and Theoretically Better Than Bloom	2022	VLDB
7	10,183	A four-dimensional Analysis of Partitioned Approximate Filters	2021	VLDB
8	874	Spectral Bloom Filters	2003	SIGMOD
9	7,949	Including Bloom Filters in Bottom-up Optimization	2025	SIGMOD
10	3,709	Stable Learned Bloom Filters for Data Streams	2020	VLDB