On Compressing the Textual Web December 8, 2009

Favorite:

Google Tech Talk
November 24, 2009

ABSTRACT

Presented by Paolo Ferragina.

Nowadays we know how to effectively compress most basic components of any modern search engine, such as, the graphs arising from the Web structure and/or its usage, the posting lists, and the dictionary of terms. But we are not aware of any study which has deeply addressed the issue of compressing the raw Web pages. Many Web applications use simple compression algorithms--- e.g. gzip, or word-based Move-to-Front or Huffman coders--- and conclude that, even compressed, raw data take more space than Inverted Lists.

In this paper we investigate two typical scenarios of use of data compression for large Web collections. In the first scenario, the compressed pages are stored on disk and we only need to support the fast scanning of large parts of the compressed collection (such as for map-reduce paradigms). In the second scenario, we consider the fast access to individual pages of the compressed collection that is distributed among the RAMs of many PCs (such as for search engines and miners). For the first scenario, we provide a thorough experimental comparison among state-of-the-art compressors thus indicating pros and cons of the available solutions. For the second scenario, we compare compressed-storage solutions with the new algorithmic technology of Compressed Self-Indexes [see e.g. Navarro-Makinen, ACM Comp. Surveys 07].

Our results show that Web pages are more compressible than expected and, consequently, that some common beliefs in this area should be reconsidered. Our results provide a threefold contribution: a non-trivial baseline for designing new compressed-storage solutions, a guide for software developers faced with Web-page storage, and a natural complement to the recent figures on InvertedList-compression achieved by [Suel et al, SIGIR & WWW 09].

[joint work with G. Manzini, the paper will appear in the Procs of WSDM 2010]