Optimizing result prefetching in web search engines with segmented indices

ABSTRACT

We study the process in which search engines with segmented indices serve queries. In particular, we investigate the number of result pages that search engines should prepare during the query processing phase.Search engine users have been observed to browse through very few pages of results for queries that they submit. This behavior of users suggests that prefetching many results upon processing an initial query is not efficient, since most of the prefetched results will not be requested by the user who initiated the search. However, a policy that abandons result prefetching in favor of retrieving just the first page of search results might not make optimal use of system resources either.We argue that for a certain behavior of users, engines should prefetch a constant number of result pages per query. We define a concrete query processing model for search engines with segmented indices, and analyze the cost of such prefetching policies. Based on these costs, we show how to determine the constant that optimizes the prefetching policy. Our results are mostly applicable to local index partitions of the inverted files, but are also applicable to processing short queries in global index architectures.

REFERENCES

• 1: Arvind Arasu , Junghoo Cho , Hector Garcia-Molina , Andreas Paepcke , Sriram Raghavan, Searching the Web, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.2-43, Aug. 2001 [doi>10.1145/383034.383035]
• 2: Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced Allocations, SIAM Journal on Computing, v.29 n.1, p.180-200, Feb. 2000 [doi>10.1137/S0097539795288490]
• 3: 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]
• 4: 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
• 5: Broder, A. 2000. Web search. Invited talk at the 9th Text Retrieval Conference (TREC-9), Gaithersburg, Maryland, November.
• 6: Brendon Cahoon , Kathryn S. McKinley , Zhihong Lu, Evaluating the performance of distributed architectures for information retrieval using a variety of workloads, ACM Transactions on Information Systems (TOIS), v.18 n.1, p.1-43, Jan. 2000 [doi>10.1145/333135.333136]
• 7: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 8: Artur Czumaj , Volker Stemann, Randomized Allocation Processes, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.194, October 19-22, 1997
• 9: Feller, W. 1970. An Introduction to Probability Theory and Its Applications. John Wiley & Sons.
• 10: David Hawking, Scalable Text Retrieval for Large Digital Libraries, Proceedings of the First European Conference on Research and Advanced Technology for Digital Libraries, p.127-145, September 01-03, 1997
• 11: 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]
• 12: Byeong-Soo Jeong , Edward Omiecinski, Inverted File Partitioning Schemes in Multiple Disk Systems, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.142-153, February 1995 [doi>10.1109/71.342125]
• 13: Johnson, N. L. and Kotz, S. I. 1977. Urn Models and their Application. John Wiley & Sons, Inc.
• 14: Johnson, N. L. and Young, D. H. 1960. Some applications of two approximations to the multinomial distribution. Biometrika 47, 463--469.
• 15: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 16: Kolchin, V. F., Sevast'yanov, B. A., and Chistyakov, V. P. 1978. Random Allocations. V. H. Winston & Sons.
• 17: Lawrence, S. and Giles, C. L. 1998. Searching the world wide web. Science 280, April.
• 18: 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]
• 19: Markatos, E. P. 2000. On caching search engine query results. In Proceedings of the 5th International Web Caching and Content Delivery Workshop, May.
• 20: Sergey Melnik , Sriram Raghavan , Beverly Yang , Hector Garcia-Molina, Building a distributed full-text index for the Web, Proceedings of the 10th international conference on World Wide Web, p.396-406, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372095]
• 21: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 22: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes in C: the art of scientific computing, Cambridge University Press, New York, NY, 1988
• 23: Berthier A. Ribeiro-Neto , Ramurti A. Barbosa, Query performance for tightly coupled distributed digital libraries, Proceedings of the third ACM conference on Digital libraries, p.182-190, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276695]
• 24: Berthier A. Ribeiro-Neto , Joao Paulo Kitajima , Gonzalo Navarro , Cláudio R. G. Sant'Ana , Nivio Ziviani, Parallel Generation of Inverted Files for Distributed Text Collections, Proceedings of the XVIII International Conference of the Chilean Computer Science Society, p.149, November 12-14, 1998
• 25: Silverstein, C., Henzinger, M., Marais, H., and Moricz, M. 1998. Analysis of a very large altavista query log. Tech. Rep. 1998-014, Compaq Systems Research Center. October.
• 26: Anthony Tomasic , Hector Garcia-Molina, Performance of inverted indices in shared-nothing distributed text document informatioon retrieval systems, Proceedings of the second international conference on Parallel and distributed information systems, p.8-17, January 1993, San Diego, California, United States
• 27: J. L. Wolf , M. S. Squillante , P. S. Yu , J. Sethuraman , L. Ozsen, Optimal crawling strategies for web search engines, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511465]

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
      H.3.5 On-line Information Services
          Subjects: Web-based services
      H.3.7 Digital Libraries
          Subjects: Systems issues

General Terms:
Algorithms, Performance, Theory

Keywords:
Distributed inverted indices, prefetching, search engines