Implementation of a Bit-parallel Approximate String Matching Algorithm

スポンサーリンク

概要

• 論文の詳細を見る

• Approximate string matching is an important problem in various fields such as natural text searching or when working with large sets of DNA data. We study the bit-parallel approximate string matching algorithms of Baeza-Yates, Navarro1) and of Hyyro2). We show how to implement these in an efficient and natural way for certain parallel architectures. Specifically we compare the sequential and parallel implementations on an AMD Opteron 2.4 GHz and on an Nvidia Tesla processor (GPU) respectively. The speedup in this case is about 50 times, meaning the AMD takes 50 times longer than the T1, when compared for searches of patterns of length 1024 characters in the DNA of the fruit fly, Drosophila Melanogaster (165 million base pairs [characters]). E.g., for edit distance 15, the Tesla was able to find all matches in 8.5 seconds whereas it took 406 seconds for the AMD.

• 2009-05-04

著者

• Mikael Onsjo

  Dep. of Mathematical and Computing Science, Tokyo Institute of Technology

• Osamu Watanabe

  Dep. of Mathematical and Computing Science, Tokyo Institute of Technology

• Mikael Onsjo

  Dep. Of Mathematical And Computing Science Tokyo Institute Of Technology

• Onsjo Mikael

  Dep. Of Mathematical And Computing Science Tokyo Institute Of Technology

• Osamu Watanabe

  Dep. Of Mathematical And Computing Science Tokyo Institute Of Technology

関連論文

• Implementation of a Bit-parallel Approximate String Matching Algorithm
• Implementation of a Bit-parallel Approximate String Matching Algorithm

スポンサーリンク