Highly efficient dictionary matching in parallel

S. Muthukrishnan, K. Palem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

We present highly efficient parallel algorithms for several well-studied dictionary matching problems. Our algorithms are faster and more efficient in terms of their parallel work, compared to previously known results. For static dictionary matching, we present an algorithm that preprocesses the dictionary and matches the text in O(logm) parallel time and 0(M + n log m) work, given any dictionary of size M whose longest pattern is m characters long, and a text of size n. We have further improved this algorithm to solve static dictionary matching with only 0((M + n)vlog m) work, if the characters are drawn from an alphabet of constant size. A distinguishing feature of these algorithms and the one stated below for matching in higher dimensions, is that in contrast with previous work, the running times, and work overheads when applicable, are dependent only on the length of the longest pattern m. We present a parallel algorithm for d-dimensional dictionary matching that runs in O(logm) time and matches the text in 0(M + nlogm) work for any fixed d. We present a new and more efficient parallel algorithm for dynamic dictionary matching. Insertions into and deletions from the dictionary, as well as matching the text can be done with optimal speedup in 0(A log M) work and 0(log M) time. Here, A denotes the length of the string to be inserted, deleted or matched into a dictionary of size M. All of the above algorithms are designed by applying the shrink-and-spawn technique that we introduce in this paper. We also show that this technique leads to parallel algorithms that only do optimal (linear) work, for multi-dimensional pattern matching and related problems [KLP89,Rab93]. Our algorithms are deterministic, as those in [KLP89], but however, are much simpler and preserve the efficiency as well as the speed of those presented there.

Original languageEnglish (US)
Title of host publicationProceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
PublisherAssociation for Computing Machinery, Inc
Pages69-78
Number of pages10
ISBN (Electronic)0897915992, 9780897915991
DOIs
StatePublished - Aug 1 1993
Event5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993 - Velen, Germany
Duration: Jun 30 1993Jul 2 1993

Publication series

NameProceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993

Other

Other5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
CountryGermany
CityVelen
Period6/30/937/2/93

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Highly efficient dictionary matching in parallel'. Together they form a unique fingerprint.

Cite this