Parallel and Distributed Implementations of Multiple and Two-Dimensional Pattern Matching Algorithms

Charalampos S. Kouzinopoulos
Department of Applied Informatics, University of Macedonia
University of Macedonia, 2013

   title={Parallel and Distributed Implementations of Multiple and Two-Dimensional Pattern Matching Algorithms},

   author={Kouzinopoulos, Charalampos S},



Download Download (PDF)   View View   Source Source   



String matching is a fundamental problem in the area of scientific computing. When two different one-dimensional strings are taken as an input, the so called "input string" and the so called "pattern", the string matching problem involves the location of all the positions in the input string where the pattern appears. As there has been an increased interest in some form of string matching in order to solve needs very different in nature, different variations of the string matching problem have been introduced over the years. Two such variations are multiple pattern matching and two-dimensional pattern matching. The multiple pattern matching problem involves the location of all the positions in a one-dimensional input string where one or more patterns from a finite pattern set occur and is commonly used by intrusion detection systems, virus scanners and spam filters as well as in the area of computational biology. The two-dimensional pattern matching problem is used to locate all the positions inside a two-dimensional input string where a two-dimensional pattern of a smaller or equal size occurs. It used in some form by OCR systems and for information retrieval from image databases. As textual, biological and image databases continue to grow with an exponential rate over the past years, there is an increased cost involved in terms of execution time and memory resources for the algorithms to process them. There is not a single solution to this problem; instead it can be addressed from different perspectives. This thesis is written with three goals in mind. The first goal involves the classification and survey of the algorithms that solve the multiple and two-dimensional pattern matching problems and the evaluation of the performance of some of the most well known algorithms for different problem parameters, including the size of the input string, the pattern and the alphabet used as well as the size of the pattern set in the case of multiple pattern matching algorithms. Although a theoretical-only study of the algorithms might be appropriate, it is well known that algorithms with an exceptional theoretical performance (i.e. algorithms with a linear or sub-linear theoretical searching phase) can be, in many cases, outperformed by simpler algorithms, depending on the implementation or optimization techniques used, the system architecture and the type of data. The next few chapters, with the help of experimental maps, can help the reader to identify the most practical algorithms for either multiple or two-dimensional pattern matching.
VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)

* * *

* * *

Like us on Facebook

HGPU group

229 people like HGPU on Facebook

Follow us on Twitter

HGPU group

1424 peoples are following HGPU @twitter

* * *

Free GPU computing nodes at hgpu.org

Registered users can now run their OpenCL application at hgpu.org. We provide 1 minute of computer time per each run on two nodes with two AMD and one nVidia graphics processing units, correspondingly. There are no restrictions on the number of starts.

The platforms are

Node 1
  • GPU device 0: nVidia GeForce GTX 560 Ti 2GB, 822MHz
  • GPU device 1: AMD/ATI Radeon HD 6970 2GB, 880MHz
  • CPU: AMD Phenom II X6 @ 2.8GHz 1055T
  • RAM: 12GB
  • OS: OpenSUSE 13.1
  • SDK: nVidia CUDA Toolkit 6.5.14, AMD APP SDK 3.0
Node 2
  • GPU device 0: AMD/ATI Radeon HD 7970 3GB, 1000MHz
  • GPU device 1: AMD/ATI Radeon HD 5870 2GB, 850MHz
  • CPU: Intel Core i7-2600 @ 3.4GHz
  • RAM: 16GB
  • OS: OpenSUSE 12.3
  • SDK: AMD APP SDK 3.0

Completed OpenCL project should be uploaded via User dashboard (see instructions and example there), compilation and execution terminal output logs will be provided to the user.

The information send to hgpu.org will be treated according to our Privacy Policy

HGPU group © 2010-2015 hgpu.org

All rights belong to the respective authors

Contact us: