Boosting the performance of Web search engines: Caching and prefetching query results by exploiting historical usage data

ABSTRACT

This article discusses efficiency and effectiveness issues in caching the results of queries submitted to a Web search engine (WSE). We propose SDC (Static Dynamic Cache), a new caching strategy aimed to efficiently exploit the temporal and spatial locality present in the stream of processed queries. SDC extracts from historical usage data the results of the most frequently submitted queries and stores them in a static, read-only portion of the cache. The remaining entries of the cache are dynamically managed according to a given replacement policy and are used for those queries that cannot be satisfied by the static portion. Moreover, we improve the hit ratio of SDC by using an adaptive prefetching strategy, which anticipates future requests by introducing a limited overhead over the back-end WSE. We experimentally demonstrate the superiority of SDC over purely static and dynamic policies by measuring the hit ratio achieved on three large query logs by varying the cache parameters and the replacement policy used for managing the dynamic part of the cache. Finally, we deploy and measure the throughput achieved by a concurrent version of our caching system. Our tests show how the SDC cache can be efficiently exploited by many threads that concurrently serve the queries of different users.

REFERENCES

• 1: Luiz André Barroso , Jeffrey Dean , Urs Hölzle, Web Search for a Planet: The Google Cluster Architecture, IEEE Micro, v.23 n.2, p.22-28, March 2003 [doi>10.1109/MM.2003.1196112]
• 2: 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]
• 3: Hölscher, C. 1998. How Internet experts search for information on the Web. In Proceedings of WebNet 98---World Conference on the WWW and Internet & Intranet (Orlando, FL, Nov. 7--12).
• 4: Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
• 5: 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]
• 6: 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]
• 7: 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]
• 8: Markatos, E. P. 2000. On caching search engine results. In Proceedings of the 5th International Web Caching and Content Delivery Workshop. Go online to http://www.iwcw.org/2000/Proceedings/proceedings.html.
• 9: Markatos, E. P. 2001. On caching search engine results. Comput. Commun. 24, 2, 137--143.
• 10: Moffat, A. and Zobel, J. 2004. What does it mean to “measure performance”? In Proceedings of the International Conference on Web Informations Systems, X. Zhou, S. Su, M. P. Papazoglou, M. E. Owlowska, and K. Jeffrey, Eds. Lecture Notes in Computer Science, vol. 3306. Springer, Berlin, Germany, 1--12.
• 11: Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.297-306, May 25-28, 1993, Washington, D.C., United States
• 12: Orlando, S., Perego, R., and Silvestri, F. 2001. Design of a parallel and distributed Web search engine. In ParCo2001: Proceedings of the International Conference Parallel Computing: Advances and Current Issues. Imperial College Press, London, U.K., 197--204.
• 13: 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]
• 14: 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]
• 15: John T. Robinson , Murthy V. Devarakonda, Data cache management using frequency-based replacement, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.134-142, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 16: 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]
• 17: 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]
• 18: Silvestri, F. 2004. High performance issues in Web search engines: Algorithms and techniques. Ph.D. dissertation. Università degli Studi di Pisa---Facoltà di Informatica, Pisa, Italy.
• 19: Amanda Spink , Dietmar Wolfram , Major B. J. Jansen , Tefko Saracevic, Searching the Web: the public and their queries, Journal of the American Society for Information Science and Technology, v.52 n.3, p.226-234, Feb. 1, 2001 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1591>3.3.CO;2-I]
• 20: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 21: Xie, Y. and O'Hallaron, D. 2002. Locality in search engine queries and its implications for caching. In Proceedings of IEEE INFOCOM 2002: The 21st Annual Joint Conference of the IEEE Computer and Communications Societies.

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: Performance evaluation (efficiency and effectiveness); Distributed systems

General Terms:
Design, Experimentation, Performance

Keywords:
Caching, Web search engines, multithreading