Simple Optimal Parallel Multiple Pattern Matching

S. Muthukrishnan

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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).

Original languageEnglish (US)
Pages (from-to)1-13
Number of pages13
JournalJournal of Algorithms
Volume34
Issue number1
DOIs
StatePublished - Jan 2000

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Simple Optimal Parallel Multiple Pattern Matching'. Together they form a unique fingerprint.

Cite this