Locality in Search Engine Queries and Its Implications for Caching

Caching is a popular technique for reducing both server load and user response time in distributed systems. In this paper, the authors are interested in the question of whether caching might be effective for search engines as well. They study two real search engine traces by examining query locality and its implications for caching. The two search engines studied are Vivisimo and Excite. Their trace analysis results show that queries have significant locality, with query frequency following a Zipf distribution. Very popular queries are shared among different users and can be cached at servers or proxies, while 16 to 22 of the queries are from the same users and should be cached at the user side. Multiple-word queries are shared less often and should be cached mainly at the user side. If caching is to be done at the user side, short-term caching for hours will be enough to cover query temporal locality, while serverproxy caching should be based on longer periods such as days. Most users have small lexicons when submitting queries. Frequent users who submit many search requests tend to reuse a small subset of words to form queries. Thus, with proxy or user side caching, prefetching based on user lexicon looks promising.