Bloom filter performance on graphics engines

Lin Ma, Roger D. Chamberlain, Jeremy D. Buhler, Mark A. Franklin

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

28 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings - 2011 International Conference on Parallel Processing, ICPP 2011
Pages522-531
Number of pages10
DOIs
StatePublished - 2011
Event40th International Conference on Parallel Processing, ICPP 2011 - Taipei City, Taiwan, Province of China
Duration: Sep 13 2011Sep 16 2011

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Conference

Conference40th International Conference on Parallel Processing, ICPP 2011
Country/TerritoryTaiwan, Province of China
CityTaipei City
Period09/13/1109/16/11

Keywords

  • BLAST
  • Bloom filter
  • NVIDIA GPU

Fingerprint

Dive into the research topics of 'Bloom filter performance on graphics engines'. Together they form a unique fingerprint.

Cite this