document: Inverted index compression via online document routing Modern search engines are expected to make documents searchable shortly after they appear on the ever changing Web . To satisfy this requirement , the Web is frequently crawled . Due to the sheer size of their indexes , search engines distribute the crawled documents among thousands of servers in a scheme called local index-partitioning , such that each server indexes only several million pages . To ensure documents from the same host ( e.g. , www.nytimes.com ) are distributed uniformly over the servers , for load balancing purposes , random routing of documents to servers is common . To expedite the time documents become searchable after being crawled , documents may be simply appended to the existing index partitions . However , indexing by merely appending documents , results in larger index sizes since document reordering for index compactness is no longer performed . This , in turn , degrades search query processing performance which depends heavily on index sizes . A possible way to balance quick document indexing with efficient query processing , is to deploy online document routing strategies that are designed to reduce index sizes . This work considers the effects of several online document routing strategies on the aggregated partitioned index size . We show that there exists a tradeoff between the compression of a partitioned index and the distribution of documents from the same host across the index partitions ( i.e. , host distribution ) . We suggest and evaluate several online routing strategies with regard to their compression , host distribution , and complexity . In particular , we present a term based routing algorithm which is shown analytically to provide better compression results than the industry standard random routing scheme . In addition , our algorithm demonstrates comparable compression performance and host distribution while having much better running time complexity than other document routing heuristics . Our findings are validated by experimental evaluation performed on a large benchmark collection of Web pages .
doc_bio_tags: O B I 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 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 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 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 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