A parallel bloom filter string searching algorithm on a many-core processor

Wenmei Ong, Vishnu Monn Baskaran, Poh Kit Chong, K. K. Ettikan, Keh Kok Yong

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

2 Citations (Scopus)

Abstract

This paper analyzes the underlying architecture of a serial Bloom filter string searching algorithm to identify the performance impact of this algorithm for large datasets. Then, a parallel multi-core driven Bloom filter algorithm using software application threads is studied as benchmark. Experimental results suggest that for a set of 10 million strings, this algorithm exhibits speedups of up to 3.3× against a serial Bloom filter algorithm, when using an 8-logical processor multi-core architecture. To further improve the speedup, a many-core driven parallel Bloom filter algorithm is proposed using the Compute Unified Device Architecture (CUDA) parallel computing platform. The proposed algorithm segments the string list into blocks of words and threads in generating the bit table for the string searching process, which maximizes computational performance and sustains consistent string searching results. Experimental results suggest that the proposed algorithm extends the speedup to 5.5× against a serial Bloom filter algorithm, when using a 256-core CUDA graphics processing unit architecture.

Original languageEnglish
Title of host publication2013 IEEE Conference on Open Systems, ICOS 2013
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages1-6
Number of pages6
ISBN (Print)9781479902859
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event2013 IEEE Conference on Open Systems 2013 - Kuching, Sarawak, Malaysia
Duration: 2 Dec 20134 Dec 2013
https://ieeexplore.ieee.org/xpl/conhome/6720225/proceeding (Proceedings)

Conference

Conference2013 IEEE Conference on Open Systems 2013
Abbreviated titleICOS 2013
CountryMalaysia
CityKuching, Sarawak
Period2/12/134/12/13
Internet address

Keywords

  • Bloom filter
  • CUDA
  • GPGPU
  • Parallel computing
  • String searching

Cite this