Back to papers
Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput
Summary: Defines performance-optimal filtering by jointly modeling lookup cost, avoided work, memory, precision, and negative-query rate—not merely space/FP tradeoffs. Introduces register-blocked and cache-sectorized Bloom filters, showing them overtake Cuckoo at high throughput.
(summarized by gpt-5.6-luna on Jul 24 2026)
Paper ID
h2544a01a07025948
Venue
VLDB
Year
2019
Pagerank
7.4280812e-05
Overall Rank
3,297 | 77.91%
DOI
10.14778/3303753.3303757
PDF
Download
(CC BY-NC-ND 4.0)
Incoming Non-self Citations Over Time
BibTeX Citation
Copy BibTeX
@article{lang_vldb19,
title = {{Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput}},
author = {Lang, Harald and Neumann, Thomas and Kemper, Alfons and Boncz, Peter},
journal = {PVLDB},
series = {{VLDB} '19},
volume = {12},
number = {5},
pages = {502--515},
doi = {10.14778/3303753.3303757},
url = {https://doi.org/10.14778/3303753.3303757},
year = {2019}
}
Incoming Citations (Sorted by Pagerank)
Showing 18 of 18 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
1,991
Chucky: A Succinct Cuckoo Filter for LSM-Tree
2021
SIGMOD
9.2264312e-05
2,827
To Partition, or Not to Partition, That is the Join Question in a Real System
2021
SIGMOD
7.9486247e-05
4,415
Bitvector-aware Query Optimization for Decision Support Queries
2020
SIGMOD
6.5965677e-05
4,646
Stacked Filters: Learning to Filter by Structure
2021
VLDB
6.4725846e-05
4,771
GRF: A Global Range Filter for LSM-Trees with Shape Encoding
2024
SIGMOD
6.412225e-05
4,773
Cuckoo Index: A Lightweight Secondary Index Structure
2020
VLDB
6.4102054e-05
5,082
InfiniFilter: Expanding Filters to Infinity and Beyond
2023
SIGMOD
6.2679091e-05
5,911
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees
2025
SIGMOD
5.9338021e-05
7,264
Pruning in Snowflake: Working Smarter, Not Harder
2025
SIGMOD
5.5557256e-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
9,034
Entropy-Learned Hashing: Constant Time Hashing with Controllable Uniformity
2022
SIGMOD
5.219451e-05
9,162
Rethinking The Compaction Policies in LSM-trees
2025
SIGMOD
5.2035666e-05
9,396
Extending SQL to Return a Subdatabase
2025
SIGMOD
5.1672232e-05
9,682
Sphinx: A Succinct Perfect Hash Index for x86
2025
VLDB
5.1258854e-05
10,183
A four-dimensional Analysis of Partitioned Approximate Filters
2021
VLDB
5.0544167e-05
10,784
Robust Predicate Transfer with Dynamic Execution
2026
VLDB
4.9605343e-05
11,097
Instance-Optimal Acyclic Joins: From Theory to Systems
2026
VLDB
4.9605343e-05
Outgoing Citations (Sorted by Pagerank)
Showing 14 of 14 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Rank
Cited Paper
Year
Venue
Pagerank
15
How Good Are Query Optimizers, Really?
2016
VLDB
0.00061463175
216
Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing
1998
VLDB
0.00024446892
327
Impala: A Modern, Open-Source SQL Engine for Hadoop
2015
CIDR
0.00020904249
402
Monkey: Optimal Navigable Key-Value Store
2017
SIGMOD
0.00019070605
791
Don't Thrash: How to Cache Your Hash on Flash
2012
VLDB
0.00013927839
871
BitWeaving: Fast Scans for Main Memory Data Processing
2013
SIGMOD
0.00013313281
874
Spectral Bloom Filters
2003
SIGMOD
0.00013298839
894
Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation
2016
SIGMOD
0.00013179915
1,117
Adaptive Range Filters for Cold Data: Avoiding Trips to Siberia
2013
VLDB
0.00011928965
1,532
Column Imprints: A Secondary Index Structure
2013
SIGMOD
0.00010312002
1,720
ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout
2015
SIGMOD
9.7828414e-05
1,856
Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity
2018
VLDB
9.4802321e-05
2,081
A General-Purpose Counting Filter: Making Every Bit Count
2017
SIGMOD
9.0581443e-05
2,965
Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation
2018
SIGMOD
7.7894987e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
4,773
Cuckoo Index: A Lightweight Secondary Index Structure
2020
VLDB
2
4,646
Stacked Filters: Learning to Filter by Structure
2021
VLDB
3
8,604
Conditional Cuckoo Filters
2021
SIGMOD
4
7,383
Optimizing Collections of Bloom Filters within a Space Budget
2024
VLDB
5
3,720
Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design
2021
SIGMOD
6
10,695
Breadcrumb Filters: Fast Fully Featured Filters
2026
SIGMOD
7
2,081
A General-Purpose Counting Filter: Making Every Bit Count
2017
SIGMOD
8
1,856
Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity
2018
VLDB
9
6,205
Prefix Filter: Practically and Theoretically Better Than Bloom
2022
VLDB
10
10,183
A four-dimensional Analysis of Partitioned Approximate Filters
2021
VLDB