ISSN:
1432-0541
Keywords:
Key words. String matching, Distributed data structures, BSP model, Parallel computing, Computational complexity.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. Given a text string T[1,n] , the multistring search problem consists of determining which of k pattern strings {X 1 [1,m], X 2 [1,m], . . ., X k [1,m]} , provided on-line, occur in T . We study this problem in the BSP model [27], and then extend our analysis to other coarse-grained parallel computational models. We refer to the relevant and difficult case of long patterns, that is m≥p , where p is the number of available processors, and provide an optimal result with respect to both computation and communication times, attaining a constant number of supersteps. We then study single string search (i.e., k=1 ), and show how the multistring search algorithm can be employed to speed up the process and balance the communication cost. The proposed solution takes a constant number of supersteps, and achieves optimal communication time if the string to be searched is longer than p 2 . Our results are based on the distribution of a proper data structure among the p processors, to reduce and balance the communication cost. We also indicate how short patterns can be efficiently dealt with, through a completely different algorithmic approach.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00008259
Permalink