Bloom filter performance on graphics engines

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

doi:10.1109/ICPP.2011.27

Bloom filter performance on graphics engines

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-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 language	English
Title of host publication	Proceedings - 2011 International Conference on Parallel Processing, ICPP 2011
Pages	522-531
Number of pages	10
DOIs	https://doi.org/10.1109/ICPP.2011.27
State	Published - 2011
Event	40th International Conference on Parallel Processing, ICPP 2011 - Taipei City, Taiwan, Province of China Duration: Sep 13 2011 → Sep 16 2011

Publication series

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

Conference

Conference	40th International Conference on Parallel Processing, ICPP 2011
Country/Territory	Taiwan, Province of China
City	Taipei City
Period	09/13/11 → 09/16/11

Keywords

BLAST
Bloom filter
NVIDIA GPU

Access to Document

10.1109/ICPP.2011.27

Cite this

@inproceedings{8393d3398e474458a20e670a1b87a257,

title = "Bloom filter performance on graphics engines",

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.",

keywords = "BLAST, Bloom filter, NVIDIA GPU",

author = "Lin Ma and Chamberlain, {Roger D.} and Buhler, {Jeremy D.} and Franklin, {Mark A.}",

year = "2011",

doi = "10.1109/ICPP.2011.27",

language = "English",

isbn = "9780769545103",

series = "Proceedings of the International Conference on Parallel Processing",

pages = "522--531",

booktitle = "Proceedings - 2011 International Conference on Parallel Processing, ICPP 2011",

note = "null ; Conference date: 13-09-2011 Through 16-09-2011",

}

Ma, L, Chamberlain, RD, Buhler, JD & Franklin, MA 2011, Bloom filter performance on graphics engines. in Proceedings - 2011 International Conference on Parallel Processing, ICPP 2011., 6047220, Proceedings of the International Conference on Parallel Processing, pp. 522-531, 40th International Conference on Parallel Processing, ICPP 2011, Taipei City, Taiwan, Province of China, 09/13/11. https://doi.org/10.1109/ICPP.2011.27

Bloom filter performance on graphics engines. / Ma, Lin; Chamberlain, Roger D.; Buhler, Jeremy D. et al.

Proceedings - 2011 International Conference on Parallel Processing, ICPP 2011. 2011. p. 522-531 6047220 (Proceedings of the International Conference on Parallel Processing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Bloom filter performance on graphics engines

AU - Ma, Lin

AU - Chamberlain, Roger D.

AU - Buhler, Jeremy D.

AU - Franklin, Mark A.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - BLAST

KW - Bloom filter

KW - NVIDIA GPU

UR - http://www.scopus.com/inward/record.url?scp=80155140241&partnerID=8YFLogxK

U2 - 10.1109/ICPP.2011.27

DO - 10.1109/ICPP.2011.27

M3 - Conference contribution

AN - SCOPUS:80155140241

SN - 9780769545103

T3 - Proceedings of the International Conference on Parallel Processing

SP - 522

EP - 531

BT - Proceedings - 2011 International Conference on Parallel Processing, ICPP 2011

Y2 - 13 September 2011 through 16 September 2011

ER -

Bloom filter performance on graphics engines

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this