  Compression techniques that support fast random access are a core component
of any information system. Current state-of-the-art methods group documents
into fixed-sized blocks and compress each block with a general-purpose adaptive
algorithm such as GZIP. Random access to a specific document then requires
decompression of a block. The choice of block size is critical: it trades
between compression effectiveness and document retrieval times. In this paper
we present a scalable compression method for large document collections that
allows fast random access. We build a representative sample of the collection
and use it as a dictionary in a LZ77-like encoding of the rest of the
collection, relative to the dictionary. We demonstrate on large collections,
that using a dictionary as small as 0.1% of the collection size, our algorithm
is dramatically faster than previous methods, and in general gives much better
compression.
