Optimizing Bloom Filters on Modern GPUs

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: https://github.com/NVIDIA/cuCollections.