Accession Number:

ADA458510

Title:

Locality in Search Engine Queries and Its Implications for Caching

Descriptive Note:

Research paper

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2001-05-01

Pagination or Media Count:

22.0

Abstract:

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.

Subject Categories:

  • Information Science
  • Computer Programming and Software
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE