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.5431911e-05
Overall Rank: 7,358 | 50.53%
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 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,640	Mnemosyne: Dynamic Workload-Aware BF Tuning via Accurate Statistics in LSM trees	2025	SIGMOD	5.2972383e-05
10,022	Towards Functional Decomposition of Storage Formats	2025	CIDR	5.0941658e-05
10,915	Reaching the Pinnacle of TPC-DS: Co-design of Architecture, Executor, and Storage in TDSQL	2026	VLDB	4.9793485e-05
11,060	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.9793485e-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.00068998927
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046284649
52	The Snowflake Elastic Data Warehouse	2016	SIGMOD	0.00041219077
128	An Evaluation of Buffer Management Strategies for Relational Database Systems	1985	VLDB	0.00030411805
400	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00019129175
459	Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores	2020	VLDB	0.00017856221
789	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.0001397781
816	SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data	2017	VLDB	0.00013687311
1,036	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00012377471
1,980	Chucky: A Succinct Cuckoo Filter for LSM-Tree	2021	SIGMOD	9.2595896e-05
2,071	A General-Purpose Counting Filter: Making Every Bit Count	2017	SIGMOD	9.0866982e-05
3,592	Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads	2017	VLDB	7.1835842e-05
3,680	SplinterDB and Maplets: Improving the Tradeoffs in Key-Value Store Compaction Policy	2023	SIGMOD	7.1029718e-05
3,703	Stable Learned Bloom Filters for Data Streams	2020	VLDB	7.0842566e-05
3,712	Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design	2021	SIGMOD	7.078249e-05
4,625	Stacked Filters: Learning to Filter by Structure	2021	VLDB	6.4969374e-05
4,756	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.43221e-05
4,758	SQLite: Past, Present, and Future	2022	VLDB	6.4318211e-05
5,081	InfiniFilter: Expanding Filters to Infinity and Beyond	2023	SIGMOD	6.2854372e-05
5,854	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.9708829e-05
6,682	Hierarchical Residual Encoding for Multiresolution Time Series Compression	2023	SIGMOD	5.7093663e-05
8,199	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.3788727e-05
8,580	Conditional Cuckoo Filters	2021	SIGMOD	5.3100462e-05

Semantically Similar Papers

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