Parallel compression with cooperative dictionary construction

Abstract

It is often desirable to compress or decompress relatively small blocks of data at high bandwidth and low latency (for example, for data fetches across a high speed network). Sequential compression may not satisfy the speed requirement, while simply splitting the block into smaller subblocks for parallel compression yields poor compression performance due to small dictionary sizes. We here consider an intermediate approach, where multiple compressors jointly construct a dictionary. The result is parallel speedup, with compression performance similar to the sequential case.