Graphics Processing Unit Bloom Filters: Classical and Probabilistic

Graphics Processing Units (GPUs) have been used to enhance the speed and efficiency of both data structures and algorithms alike. A common data structure used in Computer Science is the Bloom Filter, which is used in many types of applications including databases and security logging. The Bloom Filter is a lossy data structure that uses several hash functions to store keys into a bit array. A novel, new Bloom Filter meant for use in internet traffic detection called the Probabilistic Bloom Filter has recently been developed. In practice, this new Bloom Filter typically makes use of more hash functions than its classical counterpart. Because both of these data structures contain information that can be inserted in independent batch operations, this makes each data structure a prime target to be parallelized on a Graphics Processing Unit. This paper develops a scalable, optimized Graphics Processing Unit implementation of the classical and Probabilistic Bloom Filters. The results of processing the Bloom Filter on the Graphics Processing Unit (GPU) are compared to processing the same Bloom Filter on the Central Processing Unit (CPU). By processing the data structures on Graphics Processing Units, a substantial decrease in processing time was observed and recorded. For most cases, the decrease in time was linearly proportional to the number of keys inserted and the number of hash functions used.