Abstract
Emerging applications in multi-media and the Human Genome Project require storage and searching of large databases of strings - a task for which parallelism seems the only hope. In this paper, we consider the parallelism in some of the fundamental problems in compressing strings and in matching large dictionaries of patterns against texts. We present the first work-optimal algorithms for these well-studied problems including the classical dictionary matching problem, optimal compression with a static dictionary and the universal data compression with dynamic dictionary of Lempel and Ziv. All our algorithms are randomized and they are of the Las Vegas type. Furthermore, they are fast, working in time logarithmic in the input size. Additionally, our algorithms seem suitable for a distributed implementation.
| Original language | English (US) |
|---|---|
| Pages | 244-253 |
| Number of pages | 10 |
| State | Published - 1995 |
| Event | Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA'95 - Santa Barbara, CA, USA Duration: Jul 17 1995 → Jul 19 1995 |
Other
| Other | Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA'95 |
|---|---|
| City | Santa Barbara, CA, USA |
| Period | 7/17/95 → 7/19/95 |
ASJC Scopus subject areas
- Software
- Safety, Risk, Reliability and Quality