Design trade-offs for search engine caching

ABSTRACT

In this article we study the trade-offs in designing efficient caching systems for Web search engines. We explore the impact of different approaches, such as static vs. dynamic caching, and caching query results vs. caching posting lists. Using a query log spanning a whole year, we explore the limitations of caching and we demonstrate that caching posting lists can achieve higher hit rates than caching query answers. We propose a new algorithm for static caching of posting lists, which outperforms previous methods. We also study the problem of finding the optimal way to split the static cache between answers and posting lists. Finally, we measure how the changes in the query log influence the effectiveness of static caching, given our observation that the distribution of the queries changes slowly over time. Our results and observations are applicable to different levels of the data-access hierarchy, for instance, for a memory/disk layer or a broker/remote server layer.

REFERENCES

• 1: Vo Ngoc Anh , Alistair Moffat, Pruned query evaluation using pre-computed impacts, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148235]
• 2: Ricardo Baeza-Yates , Aristides Gionis , Flavio Junqueira , Vanessa Murdock , Vassilis Plachouras , Fabrizio Silvestri, The impact of caching on search engines, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277775]
• 3: Baeza-Yates, R., Junqueira, F., Plachouras, V., and Witschel, H. F. 2007. Admission policies for caches of search engine results. In Proceedings of the 14th International Symposium on String Processing and Information Retrieval (SPIRE'07). Lecture Notes in Computer Science, Vol. 4726, 74--85.
• 4: Baeza-Yates, R. and Saint-Jean, F. 2003. A three level search engine index based in query log distribution. In Proceedings of the 10th International Symposium on String Processing and Information Retrieval (SPIRE'03). Lecture Notes in Computer Science, Vol. 2857, 56--65.
• 5: Steven M. Beitzel , Eric C. Jensen , Abdur Chowdhury , David Grossman , Ophir Frieder, Hourly analysis of a very large topically categorized web query log, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009048]
• 6: Paolo Boldi , Bruno Codenotti , Massimo Santini , Sebastiano Vigna, UbiCrawler: a scalable fully distributed web crawler, Software—Practice & Experience, v.34 n.8, p.711-726, 10 July 2004 [doi>10.1002/spe.587]
• 7: Chris Buckley , Alan F. Lewit, Optimization of inverted vector searches, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.97-110, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253515]
• 8: Stefan Büttcher , Charles L. A. Clarke, A document-centric approach to static index pruning in text retrieval systems, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183644]
• 9: Pei Cao , Sandy Irani, Cost-aware WWW proxy caching algorithms, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, p.18-18, December 08-11, 1997, Monterey, California
• 10: Carlos Castillo , Debora Donato , Luca Becchetti , Paolo Boldi , Stefano Leonardi , Massimo Santini , Sebastiano Vigna, A reference collection for web spam, ACM SIGIR Forum, v.40 n.2, p.11-24, December 2006 [doi>10.1145/1189702.1189703]
• 11: P. J. Denning, Working Sets Past and Present, IEEE Transactions on Software Engineering, v.6 n.1, p.64-84, January 1980 [doi>10.1109/TSE.1980.230464]
• 12: Tiziano Fagni , Raffaele Perego , Fabrizio Silvestri , Salvatore Orlando, Boosting the performance of Web search engines: Caching and prefetching query results by exploiting historical usage data, ACM Transactions on Information Systems (TOIS), v.24 n.1, p.51-78, January 2006 [doi>10.1145/1125857.1125859]
• 13: Bernard J. Jansen , Amanda Spink, How are we searching the world wide web?: a comparison of nine search engine transaction logs, Information Processing and Management: an International Journal, v.42 n.1, p.248-263, January 2006 [doi>10.1016/j.ipm.2004.10.007]
• 14: Bernard J. Jansen , Amanda Spink , Judy Bateman , Tefko Saracevic, Real life information retrieval: a study of user queries on the Web, ACM SIGIR Forum, v.32 n.1, p.5-17, Spring 1998 [doi>10.1145/281250.281253]
• 15: Ronny Lempel , Shlomo Moran, Predictive caching and prefetching of query results in search engines, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775156]
• 16: Xiaohui Long , Torsten Suel, Three-level caching for efficient query processing in large Web search engines, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060785]
• 17: Markatos, E. P. 2001. On caching search engine query results. Comput. Commun. 24, 2, 137--143.
• 18: Alexandros Ntoulas , Junghoo Cho, Pruning policies for two-tiered inverted index with correctness guarantee, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277776]
• 19: Ounis, I., Amati, G., Plachouras, V., He, B., Macdonald, C., and Lioma, C. 2006. Terrier: a high performance and scalable information retrieval platform. In SIGIR Workshop on Open Source Information Retrieval.
• 20: Stefan Podlipnig , Laszlo Böszörmenyi, A survey of Web cache replacement strategies, ACM Computing Surveys (CSUR), v.35 n.4, p.374-398, December 2003 [doi>10.1145/954339.954341]
• 21: Vijay V. Raghavan , Hayri Sever, On the reuse of past optimal queries, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.344-350, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215381]
• 22: 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]
• 23: Craig Silverstein , Hannes Marais , Monika Henzinger , Michael Moricz, Analysis of a very large web search engine query log, ACM SIGIR Forum, v.33 n.1, p.6-12, Fall 1999 [doi>10.1145/331403.331405]
• 24: D. R. Slutz , I. L. Traiger, A note on the calculation of average working set size, Communications of the ACM, v.17 n.10, p.563-565, Oct. 1974 [doi>10.1145/355620.361167]
• 25: Trevor Strohman , Howard Turtle , W. Bruce Croft, Optimization strategies for complex queries, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076074]
• 26: Yohannes Tsegay , Andrew Turpin , Justin Zobel, Dynamic index pruning for effective caching, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321592]
• 27: Ian H. Witten , Timothy C. Bell , Alistair Moffat, Managing Gigabytes: Compressing and Indexing Documents and Images, John Wiley & Sons, Inc., New York, NY, 1994
• 28: Xie, Y. and O'Hallaron, D. R. 2002. Locality in search engine queries and its implications for caching. In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'02).
• 29: Young, N. E. 2002. On-line file caching. Algorithmica 33, 3, 371--383.
• 30: Jiangong Zhang , Xiaohui Long , Torsten Suel, Performance of compressed inverted list caching in search engines, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367550]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems; Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design

Keywords:
Caching, Web search, query logs