high performance computing on graphics processing units: hgpu.org

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.