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: 13751
Venue: VLDB
Year: 2024
Pagerank: 5.609743e-05
Overall Rank: 7,469 | 48.76%
DOI: 10.14778/3681954.3682020

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 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,475	Mnemosyne: Dynamic Workload-Aware BF Tuning via Accurate Statistics in LSM trees	2025	SIGMOD	5.4171036e-05
9,836	Towards Functional Decomposition of Storage Formats	2025	CIDR	5.2110542e-05
10,613	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	5.093636e-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.00069513174
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
66	The Snowflake Elastic Data Warehouse	2016	SIGMOD	0.00038561587
135	An Evaluation of Buffer Management Strategies for Relational Database Systems	1985	VLDB	0.00030209257
446	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00018332392
520	Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores	2020	VLDB	0.00017136828
789	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.0001401724
857	SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data	2017	VLDB	0.00013568886
1,044	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.0001244236
1,954	Chucky: A Succinct Cuckoo Filter for LSM-Tree	2021	SIGMOD	9.4208165e-05
2,043	A General-Purpose Counting Filter: Making Every Bit Count	2017	SIGMOD	9.2674387e-05
3,571	Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads	2017	VLDB	7.2991953e-05
3,773	SplinterDB and Maplets: Improving the Tradeoffs in Key-Value Store Compaction Policy	2023	SIGMOD	7.1384476e-05
3,798	Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design	2021	SIGMOD	7.1165678e-05
4,073	Stable Learned Bloom Filters for Data Streams	2020	VLDB	6.9242783e-05
4,532	Stacked Filters: Learning to Filter by Structure	2021	VLDB	6.6436681e-05
4,782	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.5115802e-05
4,960	InfiniFilter: Expanding Filters to Infinity and Beyond	2023	SIGMOD	6.4280133e-05
5,284	SQLite: Past, Present, and Future	2022	VLDB	6.2827906e-05
6,042	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.9970052e-05
6,556	Hierarchical Residual Encoding for Multiresolution Time Series Compression	2023	SIGMOD	5.8404094e-05
8,056	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.4983582e-05
8,413	Conditional Cuckoo Filters	2021	SIGMOD	5.4306049e-05

Semantically Similar Papers

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