PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Fagni T., Orlando S., Palmerini P., Perego R., Silvestri F. A hybrid strategy for caching Web search engine results. Accettato alla conferenza WWW2003, The Twelfth International World Wide Web Conference, 20-24 May 2003, Budapest, HUNGARY, Technical report, 2003.
 
 
Abstract
(English)
This paper discusses the design and implementation of an efficient caching system aimed to exploit the locality present in the queries submitted to a Web search engine. Previous works showed that there is a significative temporal locality in the queries, and demonstrated that caching query results is a viable strategy to increase search engine throughput. We enhance previous proposals in several directions. First we propose the adoption of a hybrid strategy for caching, where the results of the most frequently submitted queries are maintained in a static cache of fixed size, and only the queries that cannot be satisfied by the static cache compete for the use of a dynamic cache. We experimentally demonstrate the superiority of our hybrid strategy over a purely static or dynamic caching policy by evaluating the hit-rate achieved on three large query logs by varying the size of the cache, the percentage of static cache entries, and the replacement policy used for managing dynamic cache entries. Moreover, we show that search engine query logs also exhibit spatial locality, since users often require subsequent pages of results for the same query. Our caching system also take advantage of this type of locality by exploiting a sort of adaptive prefetching strategy. Finally, differently from other works, we accurately evaluate cost and scalability of our cache implementation.
Subject Caching
Search engines
Query log analysis
Performance
C.4 PERFORMANCE OF SYSTEMS
D.1.3 Concurrent Programming
H.3.3 Information Search and Retrieval
H.3.4 Systems and Software
H.3.5 Online Information Services
I.6 SIMULATION AND MODELING


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional