The Library
Simple optimal parallel multiple pattern matching
Tools
UNSPECIFIED (2000) Simple optimal parallel multiple pattern matching. JOURNAL OF ALGORITHMS, 34 (1). pp. 1-13. ISSN 0196-6774.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 | ||||
Official Date: | January 2000 | ||||
Dates: |
|
||||
Volume: | 34 | ||||
Number: | 1 | ||||
Number of Pages: | 13 | ||||
Page Range: | pp. 1-13 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |