Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
We study the problem of caching query result pages in Web search engines. Popular search engines receive millions of queries per day, and for each query, return a result page to the user who submitted the query. The user may request additional result pages for the same query, submit a new query, or quit searching altogether. An efficient scheme for caching query result pages may enable search engines to lower their response time and reduce their hardware requirements. This work studies query result caching within the framework of the competitive analysis of algorithms. We define a discrete time stochastic model for the manner in which queries are submitted to search engines by multiple user sessions. We then present an adaptation of a known online paging scheme to this model. The expected number of cache misses of the resulting algorithm is no greater than 4 times the expected number of misses that any online caching algorithm will experience under our specific model of query generation. © 2004 Elsevier B.V. All rights reserved.
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989