On Caching Search Engine Results

In this paper we explore the problem of Caching of Search Engine Query Results in order to reduce the computing and I/O requirements needed to support the functionality of a search engine of the world-wide web. Based on traces from search engines we show that there is significant locality in the queries asked, that is, 20-30% of the queries have been previously submitted by the same or a different user. Using trace-driven simulation we show that medium-sized caches can hold most of the frequently-submitted queries. Finally, we propose and evaluate a new cache replacement algorithm named LRU-2S, that takes into account both the frequency and the recency of access to a page when making a replacement decision