A four-dimensional Analysis of Partitioned Approximate Filters

Summary: A four-dimensional benchmark of Bloom, Cuckoo, Morton, and Xor filters evaluates false positives, space, build, and lookup throughput. Radix partitioning yields up to 9×/5× build/lookup gains; register-blocked Bloom maximizes throughput, while Xor favors compact, low-FPR filters. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12600
Venue: VLDB
Year: 2021
Pagerank: 5.1810297e-05
Overall Rank: 10,004 | 31.37%
DOI: 10.14778/3476249.3476286

Incoming Non-self Citations Over Time

Authors

1. Tobias Schmidt (Technical University of Munich)
2. Maximilian Bandle (Technical University of Munich)
3. Jana Giceva (Technical University of Munich)

BibTeX Citation

@article{schmidt_vldb21,
        title = {{A four-dimensional Analysis of Partitioned Approximate Filters}},
        author = {Schmidt, Tobias and Bandle, Maximilian and Giceva, Jana},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {11},
        pages = {2355--2368},
        doi = {10.14778/3476249.3476286},
        url = {https://doi.org/10.14778/3476249.3476286},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,535	Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects	2022	SIGMOD	6.6419266e-05
6,086	Plush: A Write-Optimized Persistent Log-Structured Hash-Table	2022	VLDB	5.9817424e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
29	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.00052093615
330	Impala: A Modern, Open-Source SQL Engine for Hadoop	2015	CIDR	0.0002104801
446	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00018332392
789	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.0001401724
862	Spectral Bloom Filters	2003	SIGMOD	0.00013532857
1,265	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD	0.00011415709
1,278	A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing	2016	VLDB	0.00011362007
1,975	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB	9.3645236e-05
2,043	A General-Purpose Counting Filter: Making Every Bit Count	2017	SIGMOD	9.2674387e-05
3,510	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	7.3561488e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,225	Dynamic Flat Filter: A Unified Framework for Scalable and Stable Fingerprint-Based Filters	2026	SIGMOD
2	4,532	Stacked Filters: Learning to Filter by Structure	2021	VLDB
3	7,469	Optimizing Collections of Bloom Filters within a Space Budget	2024	VLDB
4	8,892	Adaptive Quotient Filters	2024	SIGMOD
5	2,043	A General-Purpose Counting Filter: Making Every Bit Count	2017	SIGMOD
6	3,798	Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design	2021	SIGMOD
7	11,572	New Wine in an Old Bottle: Data-Aware Hash Functions for Bloom Filters	2022	VLDB
8	1,975	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB
9	6,539	Prefix Filter: Practically and Theoretically Better Than Bloom	2022	VLDB
10	3,510	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB