UNSPECIFIED (2000) Simple optimal parallel multiple pattern matching. JOURNAL OF ALGORITHMS, 34 (1). pp. 1-13. ISSN 0196-6774

Full text not available from this repository.

Abstract

In this paper, we present a simple algorithm for solving the multipattern matching problem, with optimal speedup. The best-known deterministic parallel algorithm for this problem also provides optimal speedup, but relies crucially on a sophisticated construction of an automaton. Since then, Rabin has introduced a simple and elegant parallel algorithm (M. Rabin, in Sequences '91: Methods in Communication, Security, and Computer Science," Springer-Verlag, New York/Berlin, 1993). This is a Monte-carlo algorithm based on finger-print functions and it, too, has optimal speedup. Our algorithm simultaneously achieves the goals of optimal speedup of the deterministic algorithm, as well as the simplicity of the randomized Monte-carlo design cited above. Our algorithm presented here can also be extended to solve the multidimensional pattern-matching problem, also with optimal speedup. Interestingly, the sequential version of the algorithm derived by slowing down our parallel design yields a new and simple (linear-time) algorithm for string matching. It is distinguished by its lack of dependence on failure-functions and its related automata-theoretic variants, periodicities, or special data structures, but essentially uses a carefully constructed divide-and-conquer approach. This approach is systematized by us into the shrink-and-spawn technique, with a range of applications in parallel string and pattern matching in a paper that appears in S. Muthukrishnan and K. Palem (in "Proceedings 5th ACM Symp. on Parallel Algorithms and Architectures, 1993," pp. 69-78). (C) 2000 Academic Press.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Journal or Publication Title:	JOURNAL OF ALGORITHMS
Publisher:	ACADEMIC PRESS INC
ISSN:	0196-6774
Date:	January 2000
Volume:	34
Number:	1
Number of Pages:	13
Page Range:	pp. 1-13
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/13794

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item