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
DOI: 10.1109/ICOS.2013.6735037
关键词: Bloom filter 、 Set (abstract data type) 、 CUDA 、 Parallel computing 、 Speedup 、 Search algorithm 、 String searching algorithm 、 Computer science 、 Parallel algorithm 、 String (computer science)
摘要: This paper analyzes the underlying architecture of a serial Bloom filter string searching algorithm to identify performance impact this for large datasets. Then, parallel multi-core driven using software application threads is studied as benchmark. Experimental results suggest that set 10 million strings, exhibits speedups up 3.3× against algorithm, when an 8-logical processor architecture. To further improve speedup, many-core proposed Compute Unified Device Architecture (CUDA) computing platform. The segments list into blocks words and in generating bit table process, which maximizes computational sustains consistent results. extends speedup 5.5× 256-core CUDA graphics processing unit
sci-hub.se 参考文章(8)
Tyng Yeu Liang, Yu Wei Chang, Hung Fu Li, A CUDA programming toolkit on grids International Journal of Grid and Utility Computing. ,vol. 3, pp. 97- 111 ,(2012) , 10.1504/IJGUC.2012.047760
Cen Zhiwang, Xu Jungang, Sun Jian, A multi-layer bloom filter for duplicated URL detection international conference on advanced computer theory and engineering. ,vol. 1, ,(2010) , 10.1109/ICACTE.2010.5578947
Ronitt Rubinfeld, Bernard Chazelle, Joe Kilian, Ayellet Tal, The Bloomier filter: an efficient data structure for static support lookup tables symposium on discrete algorithms. pp. 30- 39 ,(2004) , 10.5555/982792.982797
Yu Liu, Longjiang Guo, Jinbao Li, Meirui Ren, Keqin Li, Parallel Algorithms for Approximate String Matching with k Mismatches on CUDA international parallel and distributed processing symposium. pp. 2414- 2422 ,(2012) , 10.1109/IPDPSW.2012.298
Lauro B. Costa, Samer Al-Kiswany, Matei Ripeanu, GPU support for batch oriented workloads international performance computing and communications conference. pp. 231- 238 ,(2009) , 10.1109/PCCC.2009.5403809
Arulanand Natarajan, S. Subramanian, K. Premalatha, A comparative study of cuckoo search and bat algorithm for Bloom filter optimisation in spam filtering International Journal of Bio-inspired Computation. ,vol. 4, pp. 89- 99 ,(2012) , 10.1504/IJBIC.2012.047179
N. Sertac Artan, Kaustubh Sinkar, Jalpa Patel, H. Jonathan Chao, Aggregated Bloom Filters for Intrusion Detection and Prevention Hardware global communications conference. pp. 349- 354 ,(2007) , 10.1109/GLOCOM.2007.72
M.Komp, Adhi Harmoko S, Joseph Marie Jacquard, Eniac, Konrad Zuse, Introduction to Algorithms ,(2005)