Optimizing Collections of Bloom Filters within a Space Budget

Summary: Allocate a fixed space budget across Bloom filters to minimize expected false positives given per-filter query frequencies; introduce and analyze "truncated" Bloom filters. Prove convexity, give a fast relaxation, and demonstrate gains for data-skipping and full-text search versus prior methods. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13563
Venue: VLDB
Year: 2024
Pagerank: 4.6857816e-05
Overall Rank: 7,663 | 46.70%
DOI: 10.14778/3681954.3682020

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,529	Mnemosyne: Dynamic Workload-Aware BF Tuning via Accurate Statistics in LSM trees	2025	SIGMOD	4.32934e-05
9,701	Towards Functional Decomposition of Storage Formats	2025	CIDR	4.3008468e-05
10,315	CounterSnake: A lossless and generalized compression framework for diverse sketches	2026	VLDB	4.1945683e-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
21	C-Store: A Column-oriented DBMS	2005	VLDB	0.00086087497
102	The Case for Learned Index Structures	2018	SIGMOD	0.00049545203
128	An Evaluation of Buffer Management Strategies for Relational Database Systems	1985	VLDB	0.00044535268
167	The Snowflake Elastic Data Warehouse	2016	SIGMOD	0.00039180521
609	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.0001923446
746	Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores	2020	VLDB	0.00017326979
1,248	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.00013046661
1,366	SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data	2017	VLDB	0.00012357685
1,477	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00011770865
2,798	Chucky: A Succinct Cuckoo Filter for LSM-Tree	2021	SIGMOD	8.1080111e-05
2,843	A General-Purpose Counting Filter: Making Every Bit Count	2017	SIGMOD	8.0257314e-05
4,276	Looking Ahead Makes Query Plans Robust: Making the Initial Case with In-Memory Star Schema Data Warehouse Workloads	2017	VLDB	6.2976602e-05
4,446	Stable Learned Bloom Filters for Data Streams	2020	VLDB	6.1800659e-05
4,945	SplinterDB and Maplets: Improving the Tradeoffs in Key-Value Store Compaction Policy	2023	SIGMOD	5.8157107e-05
4,994	Stacked Filters: Learning to Filter by Structure	2021	VLDB	5.78027e-05
5,315	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	5.5723424e-05
5,516	Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design	2021	SIGMOD	5.4628856e-05
5,739	InfiniFilter: Expanding Filters to Infinity and Beyond	2023	SIGMOD	5.3471718e-05
6,192	SQLite: Past, Present, and Future	2022	VLDB	5.1641743e-05
6,466	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.0528281e-05
8,222	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	4.5555621e-05
8,373	Hierarchical Residual Encoding for Multiresolution Time Series Compression	2023	SIGMOD	4.5329467e-05
8,502	Conditional Cuckoo Filters	2021	SIGMOD	4.4972336e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,994	Stacked Filters: Learning to Filter by Structure	2021	VLDB	5.78027e-05
3,838	Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters	2006	SIGMOD	6.7134945e-05
8,178	A Shifting Bloom Filter Framework for Set Queries	2016	VLDB	4.5672537e-05
4,158	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	6.3994318e-05
11,374	New Wine in an Old Bottle: Data-Aware Hash Functions for Bloom Filters	2022	VLDB	4.1945683e-05
6,831	Prefix Filter: Practically and Theoretically Better Than Bloom	2022	VLDB	4.9130458e-05
9,842	A four-dimensional Analysis of Partitioned Approximate Filters	2021	VLDB	4.2722447e-05
781	Spectral Bloom Filters	2003	SIGMOD	0.00016741046
9,189	Including Bloom Filters in Bottom-up Optimization	2025	SIGMOD	4.3769978e-05
4,446	Stable Learned Bloom Filters for Data Streams	2020	VLDB	6.1800659e-05