Paper Info
Title
Bit-parallel multiple pattern matching
Abstract
Text matching with errors is a regular task in computational biology. We present an extension of the bit-parallel Wu-Manber algorithm [16] to combine several searches for a pattern into a collection of fixed-length words. We further present an OpenCL parallelization of a redundant index on massively parallel multicore processors, within a framework of searching for similarities with seed-based heuristics. We successfully implemented and ran our algorithms on GPU and multicore CPU. Some speedups obtained are more than 60×.
Year
DOI
Venue
2011
10.1007/978-3-642-31500-8_30
PPAM (2)
Keywords
Field
DocType
redundant index,seed-based heuristics,bit-parallel wu-manber algorithm,bit-parallel multiple pattern matching,computational biology,parallel multicore processor,fixed-length word,regular task,multicore cpu,opencl parallelization,pattern matching
Computer science,Massively parallel,Parallel computing,Multicore cpu,Theoretical computer science,Heuristics,Bit parallelism,Pattern matching,Multi-core processor
Conference
Volume
ISSN
Citations 
7204
0302-9743
8
PageRank 
References 
Authors
0.53
12
3
Name
Order
Citations
PageRank
Tuan Tu Tran1362.87
Mathieu Giraud212415.28
Jean-Stéphane Varré312518.73