Predictive caching and prefetching of query results in search engines

ABSTRACT

We study the caching of query result pages in Web search engines. Popular search engines receive millions of queries per day, and efficient policies for caching query results may enable them to lower their response time and reduce their hardware requirements. We present PDC (probability driven cache), a novel scheme tailored for caching search results, that is based on a probabilistic model of search engine users. We then use a trace of over seven million queries submitted to the search engine AltaVista to evaluate PDC, as well as traditional LRU and SLRU based caching schemes. The trace driven simulations show that PDC outperforms the other policies. We also examine the prefetching of search results, and demonstrate that prefetching can increase cache hit ratios by 50% for large caches, and can double the hit ratios of small caches. When integrating prefetching into PDC, we attain hit ratios of over 0.53.

REFERENCES

• 1: L. A. Adamic and B. A. Huberman. The nature of markets in the world wide web. Quarterly Journal of Economic Commerce, 1:5--12, 2000.
• 2: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 3: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 4: P. Cao, J. Zhang, and K. Beach. Active cache: Caching dynamic contents on the web. In Proc. of the IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing (Middleware '98), pages 373--388, 1998.
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: Bernard J. Jansen , Amanda Spink , Tefko Saracevic, Real life, real users, and real needs: a study and analysis of user queries on the web, Information Processing and Management: an International Journal, v.36 n.2, p.207-227, Jan.1.2000 [doi>10.1016/S0306-4573(99)00056-4]
• 7: Björn T. Jónsson , Michael J. Franklin , Divesh Srivastava, Interaction of query evaluation and buffer management for information retrieval, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.118-129, June 01-04, 1998, Seattle, Washington, United States
• 8: Ramakrishna Karedla , J. Spencer Love , Bradley G. Wherry, Caching strategies to improve disk system performance, Computer, v.27 n.3, p.38-46, March 1994 [doi>10.1109/2.268884]
• 9: Achim Kraiss , Gerhard Weikum, Integrated document caching and prefetching in storage hierarchies based on Markov-chain predictions, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.3, p.141-162, August 1998 [doi>10.1007/s007780050060]
• 10: R. Lempel and S. Moran. Optimizing result prefetching in web search engines with segmented indices. In Proc. 28th International Conference on Very Large Data Bases, Hong Kong, China, 2002.
• 11: E. P. Markatos. On caching search engine query results. Proceedings of the 5th International Web Caching and Content Delivery Workshop, May 2000.
• 12: M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Invited Talk in the 39th Annual Allerton Conference on Communication, Control and Computing, October 2001.
• 13: Paricia Correia Saraiva , Edleno Silva de Moura , Novio Ziviani , Wagner Meira , Rodrigo Fonseca , Berthier Riberio-Neto, Rank-preserving two-level caching for scalable search engines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.51-58, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383959]
• 14: C. Silverstein, M. Henzinger, H. Marais, and M. Moricz. Analysis of a very large altavista query log. Technical Report 1998-014, Compaq Systems Research Center, October 1998.
• 15: Athena Vakali, Proxy Cache Replacement Algorithms: A History-Based Approach, World Wide Web, v.4 n.4, p.277-297, 2001 [doi>10.1023/A:1015133818512]
• 16: Yi-Hung Wu , Arbee L. P. Chen, Prediction of Web Page Accesses by Proxy Server Log, World Wide Web, v.5 n.1, p.67-88, 2002 [doi>10.1023/A:1015750423727]
• 17: Qiang Yang , Henry Hanning Zhang, Integrating Web Prefetching and Caching Using Prediction Models, World Wide Web, v.4 n.4, p.299-321, 2001 [doi>10.1023/A:1015185802583]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Experimentation, Performance

Keywords:
caching, query processing and optimization