Workshops Archive

Optimizing Bloom Filters on Modern GPUs


Workshop: IA^3 2026 — 16th Workshop on Irregular Applications: Architectures and Algorithms

Authors: Daniel Jünger, Kevin Kristensen, and Yunsong Wang (NVIDIA Corporation); Xiangyao Yu (University of Wisconsin-Madison); and Bertil Schmidt (Johannes Gutenberg University)

Abstract: Bloom filters are a fundamental data structure for approximate membership queries in applications ranging from analytics and databases to genomics. Deployed as prefilters, they eliminate irrelevant data before expensive downstream processing. As data-processing pipelines move onto GPUs, filtering must remain GPU-resident and keep pace with other stages. Although Bloom filters have been extensively optimized for CPUs, few implementations target GPUs, where fixed SIMD layouts map poorly to SIMT hardware and leave performance potential on the table. We present an architecture-aware GPU Bloom filter with tunable vectorization for performance portability across workloads, memory regimes, and GPU architectures. On NVIDIA B200, it sustains over $92\%$ of the measured random-access bound. At comparable false-positive rates, it outperforms the state-of-the-art GPU baseline by $15.4\times$ for lookup and $11.35\times$ for construction. These gains bring accurate Bloom filters to GPU-scale throughput previously reserved for high-error variants. The implementation is openly available in NVIDIA's cuCollections library.


Back to IA^3 2026 — 16th Workshop on Irregular Applications: Architectures and Algorithms Archive Listing

Back to Full Workshop Archive Listing