Crawling a country: better strategies than breadth-first for web page ordering

ABSTRACT

This article compares several page ordering strategies for Web crawling under several metrics. The objective of these strategies is to download the most "important" pages "early" during the crawl. As the coverage of modern search engines is small compared to the size of the Web, and it is impossible to index all of the Web for both theoretical and practical reasons, it is relevant to index at least the most important pages.We use data from actual Web pages to build Web graphs and execute a crawler simulator on those graphs. As the Web is very dynamic, crawling simulation is the only way to ensure that all the strategies considered are compared under the same conditions. We propose several page ordering strategies that are more efficient than breadth- first search and strategies based on partial Pagerank calculations.

REFERENCES

• 1: Robotcop. www.robotcop.org, 2002.
• 2: HT://Dig. http://www.htdig.org/, 2004. GPL software.
• 3: Serge Abiteboul , Mihai Preda , Gregory Cobena, Adaptive on-line page importance computation, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775192]
• 4: S. Ailleret. Larbin. http://larbin.sourceforge.net/index-eng.html, 2004. GPL software.
• 5: 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]
• 6: R. Baeza-Yates and C. Castillo. Balancing volume, quality and freshness in web crawling. In Soft Computing Systems - Design, Management and Applications, pages 565--572, Santiago, Chile, 2002. IOS Press Amsterdam.
• 7: R. Baeza-Yates and C. Castillo. Crawling the infinite Web: Five levels are enough. In Proceedings of the third Workshop on Web Graphs (WAW), volume 3243 of Lecture Notes in Computer Science, pages 156--167, Rome, Italy, October 2004. Springer.
• 8: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 9: Ricardo A. Baeza-Yates , Felipe Saint-Jean , Carlos Castillo, Web Structure, Dynamics and Page Quality, Proceedings of the 9th International Symposium on String Processing and Information Retrieval, p.117-130, September 11-13, 2002
• 10: 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]
• 11: P. Boldi, M. Santini, and S. Vigna. Do your worst to make the best: Paradoxical effects in pagerank incremental computations. In Proceedings of the third Workshop on Web Graphs (WAW), volume 3243 of Lecture Notes in Computer Science, pages 168--180, Rome, Italy, October 2004. Springer.
• 12: O. Brandman, J. Cho, H. Garcia-Molina, and N. Shivakumar. Crawler-friendly web servers. In Proceedings of the Workshop on Performance and Architecture of Web Servers (PAWS), Santa Clara, California, USA, June 2000.
• 13: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 14: Robin Burke, Salticus: guided crawling for personal digital libraries, Proceedings of the 1st ACM/IEEE-CS joint conference on Digital libraries, p.88-89, January 2001, Roanoke, Virginia, United States [doi>10.1145/379437.379455]
• 15: M. Burner. Crawling towards eternity - building an archive of the world wide web. Web Techniques, 2(5), May 1997.
• 16: Carlos Castillo , Mauricio Marin , Andrea Rodriguez , Ricardo Baeza-Yates, Scheduling Algorithms for Web Crawling, Proceedings of the WebMedia & LA-Web 2004 Joint Conference 10th Brazilian Symposium on Multimedia and the Web 2nd Latin American Web Congress, p.10-17, October 12-15, 2004
• 17: S. Chakrabarti. Mining the Web. Morgan Kaufmann Publishers, 2003.
• 18: Soumen Chakrabarti , Martin van den Berg , Byron Dom, Focused crawling: a new approach to topic-specific Web resource discovery, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1623-1640, May 17, 1999
• 19: J. Cho and R. Adams. Page quality: In search of an unbiased Web ranking. Technical report, UCLA Computer Science, 2004.
• 20: 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
• 21: Junghoo Cho , Hector Garcia-Molina, Parallel crawlers, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511464]
• 22: Junghoo Cho , Hector Garcia-Molina , Lawrence Page, Efficient crawling through URL ordering, Proceedings of the seventh international conference on World Wide Web 7, p.161-172, April 1998, Brisbane, Australia
• 23: Junghoo Cho , Narayanan Shivakumar , Hector Garcia-Molina, Finding replicated Web collections, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.355-366, May 15-18, 2000, Dallas, Texas, United States
• 24: Nick Craswell , Francis Crimmins , David Hawking , Alistair Moffat, Performance and cost tradeoffs in Web search, Proceedings of the fifteenth Australasian database conference, p.161-169, January 01, 2004, Dunedin, New Zealand
• 25: Artur Czumaj , Ian Finch , Leszek Gąsieniec , Alan Gibbons , Paul Leng , Wojciech Rytter , Michele Zito, Efficient web searching using temporal factors, Theoretical Computer Science, v.262 n.1-2, p.569-582, July 2001 [doi>10.1016/S0304-3975(00)00366-2]
• 26: Altigran S. da Silva , Eveline A. Veloso , Paulo B. Golghe , Berthier Ribeiro-Neto , Alberto H. F. Laender , Nivio Ziviani, CoBWeb A Crawler for the Brazilian Web, Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware, p.184, September 21-24, 1999
• 27: L. Dacharay. WebBase. http://freesoftware.fsf.org/webbase/, 2002. GPL Software.
• 28: Michelangelo Diligenti , Frans Coetzee , Steve Lawrence , C. Lee Giles , Marco Gori, Focused Crawling Using Context Graphs, Proceedings of the 26th International Conference on Very Large Data Bases, p.527-534, September 10-14, 2000
• 29: Stephen Dill , Ravi Kumar , Kevin S. Mccurley , Sridhar Rajagopalan , D. Sivakumar , Andrew Tomkins, Self-similarity in the web, ACM Transactions on Internet Technology (TOIT), v.2 n.3, p.205-223, August 2002 [doi>10.1145/572326.572328]
• 30: R. W. Edward G. Coffman, Z. Liu. Optimal robot scheduling for web search engines. Journal of Scheduling, 1(1):15--29, 1998.
• 31: Jenny Edwards , Kevin McCurley , John Tomlin, An adaptive model for optimizing performance of an incremental web crawler, Proceedings of the 10th international conference on World Wide Web, p.106-113, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371960]
• 32: D. Eichmann. The RBSE spider: balancing effective search against web load. In Proceedings of the first World Wide Web Conference, Geneva, Switzerland, May 1994.
• 33: Nadav Eiron , Kevin S. McCurley , John A. Tomlin, Ranking the web frontier, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988714]
• 34: Dennis Fetterly , Mark Manasse , Marc Najork, Spam, damn spam, and statistics: using statistical analysis to locate spam web pages, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017077]
• 35: Younès Hafri , Chabane Djeraba, High performance crawling system, Proceedings of the 6th ACM SIGMM international workshop on Multimedia information retrieval, October 15-16, 2004, New York, NY, USA [doi>10.1145/1026711.1026760]
• 36: Monika R. Henzinger , Allan Heydon , Michael Mitzenmacher , Marc Najork, On near-uniform URL sampling, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.295-308, June 2000, Amsterdam, The Netherlands
• 37: Michael Hersovici , Michal Jacovi , Yoelle S. Maarek , Dan Pelleg , Menanchem Shtalhaim , Sigalit Ur, The shark-search algorithm. An application: tailored Web site mapping, Proceedings of the seventh international conference on World Wide Web 7, p.317-326, April 1998, Brisbane, Australia
• 38: Allan Heydon , Marc Najork, Mercator: A scalable, extensible Web crawler, World Wide Web, v.2 n.4, p.219-229, 1999 [doi>10.1023/A:1019213109274]
• 39: M. G. Kendall. Rank Correlation Methods. Griffin, London, England, 1970.
• 40: M. Koster. Robots in the web: threat or treat ? ConneXions, 9(4), April 1995.
• 41: O. A. McBryan. GENVL and WWWW: Tools for taming the web. In Proceedings of the first World Wide Web Conference, Geneva, Switzerland, May 1994.
• 42: Andrew Kachites McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, Automating the Construction of Internet Portals with Machine Learning, Information Retrieval, v.3 n.2, p.127-163, July 2000 [doi>10.1023/A:1009953814988]
• 43: Filippo Menczer , Gautam Pant , Padmini Srinivasan , Miguel E. Ruiz, Evaluating topic-driven web crawlers, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.241-249, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383995]
• 44: Robert C. Miller , Krishna Bharat, SPHINX: a framework for creating personal, site-specific Web crawlers, Proceedings of the seventh international conference on World Wide Web 7, p.119-130, April 1998, Brisbane, Australia
• 45: Marc Najork , Janet L. Wiener, Breadth-first crawling yields high-quality pages, Proceedings of the 10th international conference on World Wide Web, p.114-118, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371965]
• 46: Alexandros Ntoulas , Junghoo Cho , Christopher Olston, What's new on the web?: the evolution of the web from a search engine perspective, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988674]
• 47: L. Page, S. Brin, R. Motwani, and T. Winograd. The Pagerank citation algorithm: bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 48: G. Pant, S. Bradshaw, and F. Menczer. Search engine-crawler symbiosis. In Proceedings of the European Conference on Digital Libraries (ECDL), volume 2769 of Lecture Notes in Computer Science, pages 221--232. Springer, August 2003.
• 49: B. Pinkerton. Finding what people want: Experiences with the WebCrawler. In Proceedings of the First World Wide Web Conference, Geneva, Switzerland, May 1994.
• 50: Sriram Raghavan , Hector Garcia-Molina, Crawling the Hidden Web, Proceedings of the 27th International Conference on Very Large Data Bases, p.129-138, September 11-14, 2001
• 51: K. M. Risvik and R. Michelsen. Search engines and web dynamics. Computer Networks, 39(3), June 2002.
• 52: Design and Implementation of a High-Performance Distributed Web Crawler, Proceedings of the 18th International Conference on Data Engineering, p.357, February 26-March 01, 2002
• 53: J. Talim , Z. Liu , Ph. Nain , E. G. Coffman, Jr., Controlling the robots of Web search engines, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.236-244, June 2001, Cambridge, Massachusetts, United States
• 54: Pang-Ning Tan , Vipin Kumar, Discovery of Web Robot Sessions Based on their Navigational Patterns, Data Mining and Knowledge Discovery, v.6 n.1, p.9-35, January 2002 [doi>10.1023/A:1013228602957]
• 55: The Economist. Country Profiles, 2002.
• 56: United Nations. Population Division, 2002.
• 57: United Nations. Human Development Reports, 2003.
• 58: Demetrios Zeinalipour-Yazti , Marios D. Dikaiakos, Design and Implementation of a Distributed Crawler and Filtering Processor, Proceedings of the 5th International Workshop on Next Generation Information Technologies and Systems, p.58-74, June 24-25, 2002
• 59: H. Zhang, A. Goel, R. Govindan, K. Mason, and B. V. Roy. Making eigenvector-based reputation systems robust to collusion. In Proceedings of the third Workshop on Web Graphs (WAW), volume 3243 of Lecture Notes in Computer Science, pages 92--104, Rome, Italy, October 2004. Springer.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Experimentation, Measurement, Performance

Keywords:
scheduling policy, web crawler, web page importance