LZW Data Compression on Large Scale and Extreme Distributed Systems

Abstract. Results on the parallel complexity of Lempel-Ziv data compression suggest that the sliding window method is more suitable than the LZW technique on shared memory parallel machines. When instead we address the practical goal of designing distributed algorithms with low communication cost, sliding window compression does not seem to guarantee robustness if we scale up the system. The possibility of imple-menting scalable heuristics is instead offered by LZW compression. In this paper we present two implementations of the LZW technique on a large scale and an extreme distributed system, respectively. They are both derived from a parallel approximation scheme of a bounded memory version of the sequential algorithm