document: Three-level caching for efficient query processing in large Web search engines Large web search engines have to answer thousands of queries per second with interactive response times . Due to the sizes of the data sets involved , often in the range of multiple terabytes , a single query may require the processing of hundreds of megabytes or more of index data . To keep up with this immense workload , large search engines employ clusters of hundreds or thousands of machines , and a number of techniques such as caching , index compression , and index and query pruning are used to improve scalability . In particular , two-level caching techniques cache results of repeated identical queries at the frontend , while index data for frequently used query terms are cached in each node at a lower level . We propose and evaluate a three-level caching scheme that adds an intermediate level of caching for additional performance gains . This intermediate level attempts to exploit frequently occurring pairs of terms by caching intersections or projections of the corresponding inverted lists . We propose and study several offline and online algorithms for the resulting weighted caching problem , which turns out to be surprisingly rich in structure . Our experimental evaluation based on a large web crawl and real search engine query log shows significant performance gains for the best schemes , both in isolation and in combination with the other caching levels . We also observe that a careful selection of cache admission and eviction policies is crucial for best overall performance .
doc_bio_tags: O B O O O O O 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 B O O O O O O O O O O O O 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 B 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 B O O O O O O O O O O O O O O O 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 B O O O O O O O O O O O O O O O O O O O O O O