Bounds for Compression in Streaming Models

Details Bounds for Compression in Streaming Models Bounds for Compression in Streaming Models

2007-11-21

arxiv.org/abs/0711.3338v2

Computer Science

Information Theory

added reduction from sorting to the Burrows-Wheeler Transform; thus, Grohe and Schweikardt's lower bound for short-sorting imp

Scientific paper

Compression algorithms and streaming algorithms are both powerful tools for dealing with massive data sets, but many of the best compression algorithms -- e.g., those based on the Burrows-Wheeler Transform -- at first seem incompatible with streaming. In this paper we consider several popular streaming models and ask in which, if any, we can compress as well as we can with the BWT. We first prove a nearly tight tradeoff between memory and redundancy for the Standard, Multipass and W-Streams models, demonstrating a bound that is achievable with the BWT but unachievable in those models. We then show we can compute the related Schindler Transform in the StreamSort model and the BWT in the Read-Write model and, thus, achieve that bound.

Affiliated with

Also associated with

No associations

Rating

Bounds for Compression in Streaming Models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounds for Compression in Streaming Models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds for Compression in Streaming Models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-414368