Bloom Filter Performance on Graphics Engines

Authors:
  • LMLin Ma
    Lin Ma
  • RCRoger D. Chamberlain
    Roger D. Chamberlain
  • JBJeremy D. Buhler
    Jeremy D. Buhler
  • MFMark A. Franklin
    Mark A. Franklin

Abstract
Bloom filters are a probabilistic technique for large-scale set membership tests. They exhibit no false negative test results but are susceptible to false positive results. They are well-suited to both large sets and large numbers of membership tests. We implement the Bloom filters present in an accelerated version of BLAST, a genome biosequence alignment application, on NVIDIA GPUs and develop an analytic performance model that helps potential users of Bloom filters to quantify the inherent tradeoffs between throughput and false positive rates.

This publication has 17 references indexed in Scilit: