Bloom Filter Performance on Graphics Engines
Authors:
- Lin MaLMLin Ma
- Roger D. ChamberlainRCRoger D. Chamberlain
- Jeremy D. BuhlerJBJeremy D. Buhler
- Mark A. FranklinMFMark A. Franklin
- 1 September 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 522-531
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
This publication has 17 references indexed in Scilit:
- DecGPU: distributed error correction on massively parallel graphics processing units using CUDA and MPIBMC Bioinformatics, 2011
- Classification of DNA sequences using Bloom filtersBioinformatics, 2010
- Single pass streaming BLAST on FPGAsParallel Computing, 2007
- Efficient hardware hashing functions for high performance computersIEEE Transactions on Computers, 1997
- Basic Local Alignment Search ToolJournal of Molecular Biology, 1990
- A tale of three spelling checkersSoftware: Practice and Experience, 1990
- Join and Semijoin Algorithms for a Multiprocessor Database MachineACM Transactions on Database Systems, 1984
- Designing a Bloom filter for differential file accessCommunications of the ACM, 1982
- Development of a Spelling ListIEEE Transactions on Communications, 1982
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970