Optimal crawling strategies for web search engines

ABSTRACT

Web Search Engines employ multiple so-called crawlers to maintain local copies of web pages. But these web pages are frequently updated by their owners, and therefore the crawlers must regularly revisit the web pages to maintain the freshness of their local copies. In this paper, we propose a two-part scheme to optimize this crawling process. One goal might be the minimization of the average level of staleness over all web pages, and the scheme we propose can solve this problem. Alternatively, the same basic scheme could be used to minimize a possibly more important search engine embarrassment level metric: The frequency with which a client makes a search engine query and then clicks on a returned url only to find that the result is incorrect. The first part our scheme determines the (nearly) optimal crawling frequencies, as well as the theoretically optimal times to crawl each web page. It does so within an extremely general stochastic framework, one which supports a wide range of complex update patterns found in practice. It uses techniques from probability theory and the theory of resource allocation problems which are highly computationally efficient -- crucial for practicality because the size of the problem in the web environment is immense. The second part employs these crawling frequencies and ideal crawl times as input, and creates an optimal achievable schedule for the crawlers. Our solution, based on network flow theory, is exact as well as highly efficient. An analysis of the update patterns from a highly accessed and highly dynamic web site is used to gain some insights into the properties of page updates in practice. Then, based on this analysis, we perform a set of detailed simulation experiments to demonstrate the quality and speed of our approach.

REFERENCES

• 1: R. Ahuja, T. Magnanti and J. Orlin, Network Flows, Prentice Hall, 1993.
• 2: A. Arasu, J. Cho, H. Garcia-Molina, A. Paepcke and S. Raghavan, "Searching the Web", ACM Transactions on Internet Technology, 1(1), 2001.
• 3: Jacek Blazewicz, Scheduling in Computer and Manufacturing Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 4: A. Broder, Personal communication.
• 5: J. Challenger, P. Dantzig, A. Iyengar, M. S. Squillante, and L. Zhang. Efficiently serving dynamic data at highly accessed web sites. Preprint, May 2001.
• 6: Junghoo Cho , Hector Garcia-Molina, Synchronizing a database to improve freshness, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.117-128, May 15-18, 2000, Dallas, Texas, United States
• 7: E. Coffman, Z. Liu and R. Weber, "Optimal Robot Scheduling for Web Search Engines", INRIA Research Report, 1997.
• 8: F. Douglas, A. Feldmann and B. Krishnamurthy, "Rate of Change and other Metrics: A Live Study of the World Wide Web", USENIX Symposium on Internetworking Technologies and Systems, 1999.
• 9: B. Fox, "Discrete Optimization via Marginal Analysis", Management Science, 13:210--216, 1966.
• 10: G. Frederickson and D. Johnson, "The Complexity of Selection and Ranking in X+Y and Matrices with Sorted Columns", Journal of Computer and System Science, 24:197--208, 1982.
• 11: Zvi Galil , Nimrod Megiddo, A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort, Journal of the ACM (JACM), v.26 n.1, p.58-64, Jan. 1979 [doi>10.1145/322108.322114]
• 12: Toshihide Ibaraki , Naoki Katoh, Resource allocation problems: algorithmic approaches, MIT Press, Cambridge, MA, 1988
• 13: International Business Machines Corporation, Optimization Subroutine Library Guide and Reference, IBM, 1995.
• 14: N. Katoh and T. Ibaraki, "Resource Allocation Problems", in Handbook of Combinatorial Optimization, D-Z. Du and P. Pardalos, editors, Kluwer Academic Press, 2000.
• 15: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 16: Arun K. Iyengar , Mark S. Squillante , Li Zhang, Analysis and characterization of large-scale Web server access patterns and performance, World Wide Web, v.2 n.1-2, p.85-100, 1999 [doi>10.1023/A:1019244621570]
• 17: S. Lawrence and C. Giles, "Accessibility of Information on the Web", Nature, 400:107--109, 1999.
• 18: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 19: Venkata N. Padmanabhan , Lili Qiu, The content and access dynamics of a busy Web site: findings and implications, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.111-123, August 28-September 01, 2000, Stockholm, Sweden
• 20: M. Pinedo, Scheduling: Theory, Algorithms and Systems, Prentice-Hall, 1995.
• 21: James Pitkow , Peter Pirolli, Life, death, and lawfulness on the electronic frontier, Proceedings of the SIGCHI conference on Human factors in computing systems, p.383-390, March 22-27, 1997, Atlanta, Georgia, United States [doi>10.1145/258549.258805]
• 22: W. Press, B. Flannery, S. Teukolsky and W. Vetterling, Numerical Recipes, Cambridge University Press, 1986.
• 23: S. M. Ross. Stochastic Processes. John Wiley and Sons, Second Edition, 1997.
• 24: K. Sigman. Stationary Marked Point Processes: An Intuitive Approach. Chapman and Hall, 1995.
• 25: M. Squillante, D. Yao and L. Zhang, "Web Traffic Modeling and Web Server Performance Analysis", IEEE Conference on Decision and Control, 1999.
• 26: J. Talim, Z. Liu, P. Nain and E. Coffman, "Optimizing the Number of Robots for Web Search Engines", Telecommunication Systems Journal, 17(1-2):234-243, 2001.
• 27: Craig E. Wills , Mikhail Mikhailov, Towards a better understanding of Web resources and server responses for improved caching, Proceeding of the eighth international conference on World Wide Web, p.1231-1243, May 1999, Toronto, Canada
• 28: R. W. Wolff. Stochastic Modeling and the Theory of Queues. Prentice Hall, 1989.
• 29: G. Zipf, Human Behavior and the Principle of Least Effort, Addison-Wesley, 1949.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Design, Performance, Theory