Paper Info
Title
On compressing the textual web
Abstract
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 known compressed-storage solutions with the new algorithmic technology of compressed self-indexes [NM07]. 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 are novel for the large spectrum of tested approaches and the size of datasets, and 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 [Yan et al, sigir 09 and www 09].
Year
DOI
Venue
2010
10.1145/1718487.1718536
WSDM
Keywords
Field
DocType
raw web page,large web collection,large part,web structure,large spectrum,compressed-storage solution,textual web,data compression,typical scenario,web page,web application,indexation,compression algorithm,software development,spectrum,burrows wheeler transform,search engine,lossless data compression,web pages
Data mining,Web page,Information retrieval,Burrows–Wheeler transform,Computer science,Raw data,Software,Huffman coding,Web application,Data compression,Lossless compression
Conference
Citations 
PageRank 
References 
22
0.96
49
Authors
2
Name
Order
Citations
PageRank
Paolo Ferragina189251.19
Giovanni Manzini21584111.42