document: Compressed web indexes Web search engines use indexes to efficiently retrieve pages containing specified query terms , as well as pages linking to specified pages . The problem of compressed indexes that permit such fast retrieval has a long history . We consider the problem : assuming that the terms in ( or links to ) a page are generated from a probability distribution , how well compactly can we build such indexes that allow fast retrieval ? Of particular interest is the case when the probability distribution is Zipfian ( or a similar power law ) , since these are the distributions that arise on the web . We obtain sharp bounds on the space requirement of Boolean indexes for text documents that follow Zipf 's law . In the process we develop a general technique that applies to any probability distribution , not necessarily a power law ; this is the first analysis of compression in indexes under arbitrary distributions . Our bounds lead to quantitative versions of rules of thumb that are folklore in indexing . Our experiments on several document collections show that the distribution of terms appears to follow a double-Pareto law rather than Zipf 's law . Despite widely varying sets of documents , the index sizes observed in the experiments conform well to our theoretical predictions .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O