Highly efficient dictionary matching in parallel

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.