Optimizing Bloom Filters for Modern GPU Architectures
Preprint
Abstract
Bloom filters are a fundamental data structure for approximate membership queries, with applications ranging from data analytics to databases and genomics. Several variants have been proposed to accommodate parallel architectures. GPUs, with massive thread-level parallelism and high-bandwidth memory, are a natural fit for accelerating these Bloom filter variants potentially to billions of operations per second. Although CPU-optimized implementations have been well studied, GPU designs remain underexplored. We close this gap by exploring the design space on GPUs along three dimensions: vectorization, thread cooperation, and compute latency. Our evaluation shows that the combination of these optimization points strongly affects throughput, with the largest gains achieved when the filter fits within the GPU's cache domain. We examine how the hardware responds to different parameter configurations and relate these observations to measured performance trends. Crucially, our optimized design overcomes the conventional trade-off between speed and precision, delivering the throughput typically restricted to high-error variants while maintaining the superior accuracy of high-precision configurations. At iso error rate, the proposed method outperforms the state-of-the-art by $11.35\times$ ($15.4\times$) for bulk filter lookup (construction), respectively, achieving above $92\%$ of the practical speed-of-light across a wide range of configurations on a B200 GPU. We propose a modular CUDA/C++ implementation, which will be openly available soon.
Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- DNA Bloom Filter enables anti-contamination and file version control for DNA-based data storageBriefings in Bioinformatics, 2024
- MetaProFi: an ultrafast chunked Bloom filter for storing and querying protein and nucleotide sequence data for accurate identification of functionally relevant genetic variantsBioinformatics, 2023
- KCOSS: an ultra-fast k-mer counter for assembled genome analysisBioinformatics, 2021
- Improving Bloom Filter Performance on Sequence Data Using k -mer Bloom FiltersJournal of Computational Biology, 2017
- Classification of DNA sequences using Bloom filtersBioinformatics, 2010
- A Parallel Algorithm for Error Correction in High-Throughput Short-Read Data on CUDA-Enabled Graphics HardwareJournal of Computational Biology, 2010
- Less hashing, same performance: Building a better Bloom filterRandom Structures & Algorithms, 2008
- Using Bloom Filters for Large Scale Gene Sequence Analysis in HaskellLecture Notes in Computer Science, 2008
- Network Applications of Bloom Filters: A SurveyInternet Mathematics, 2004
- A Reliable Randomized Algorithm for the Closest-Pair ProblemJournal of Algorithms, 1997