A framework for distributed pattern matching based on multithreading

Abstract EN

Despite of the dramatic evolution in high performance computing we still need to devise new efficient algorithms to speed up the search process.

In this paper, we present a framework for a data-distributed and multithreaded string matching approach in a homogeneous distributed environment.

The main idea of this approach is to have multiple agents that concurrently search the text, each one from different position.

By searching the text from different positions the required pattern can be found more quickly than by searching the text from one position).

Concurrent search can be achieved by two techniques ; the first is by using multithreading on a single processor, in this technique each thread is responsible for searching one part of the text.

The concurrency of the multithreading technique is based on the time sharing principle, so it provides us of an illusion of concurrency not pure concurrency.

The second technique is by having multiprocessor machine or distributed processors to search the text; in this technique all of the processors search the text in a pure concurrent way.

Our approach combines the two concurrent search techniques to form a hybrid one that takes advantage from the two techniques.

The proposed approach manipulates both exact string matching and approximate string matching with k-mismatches.

Experimental results demonstrate that this approach is an efficient solution to the problem in a homogeneous clustered system.