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) : Xie, Yinglian ; O'Hallaron, David


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a458510.pdf


Report Date : May 2001


Pagination or Media Count : 22


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 server/proxy 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.


Descriptors :   *DATA MANAGEMENT , *REDUCTION , *SEARCHING , *INFORMATION RETRIEVAL , *CLIENT SERVER SYSTEMS , *INTERNET , *WORKLOAD , OPTIMIZATION , USER NEEDS , VOCABULARY , RANKING , STATISTICAL ANALYSIS , PERFORMANCE(ENGINEERING) , SHARING , REACTION TIME , EFFICIENCY


Subject Categories : Information Science
      Computer Programming and Software
      Computer Systems


Distribution Statement : APPROVED FOR PUBLIC RELEASE