Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient Two-Dimensional Parallel Pattern Matching with Scaling
| Content Provider | Semantic Scholar |
|---|---|
| Author | Mongelli, Henrique |
| Copyright Year | 2007 |
| Abstract | Given a text and a pattern, the problem of pattern matching consists of determining all the positions of the text where the pattern occurs. When the text and the pattern are matrices, the matching is termed bidimensional. There are variations of this problem where we allow the matching using a somehow modified pattern. In this paper we assume that the pattern can be scaled. We propose a new parallel algorithm for this problem, under the CGM (Coarse Grained Multicomputer) model. This algorithm requires linear loca l computing time in the input, linear memory and uses only one communication round, during which at most a linear amount of data is exchanged. To the best of our knowledge, there are no known parallel algorithms for the bidimensional pattern matching problem with scaling in the literature. This proposed algorithm was implemented on a parallel machine and the experimental results obtained were very promising and showed significant speedups. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.researchgate.net/profile/Henrique_Mongelli/publication/2549497_Efficient_Two-Dimensional_Parallel_Pattern_Matching_with_Scaling/links/0a85e53584fdd2738b000000.pdf |
| Alternate Webpage(s) | http://www.ime.usp.br/~song/papers/pdcs01.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
