The impact of crawl policy on web search effectiveness

ABSTRACT

Crawl selection policy has a direct influence on Web search effectiveness, because a useful page that is not selected for crawling will also be absent from search results. Yet there has been little or no work on measuring this effect. We introduce an evaluation framework, based on relevance judgments pooled from multiple search engines, measuring the maximum potential NDCG that is achievable using a particular crawl. This allows us to evaluate different crawl policies and investigate important scenarios like selection stability over multiple iterations. We conduct two sets of crawling experiments at the scale of 1~billion and 100~million pages respectively. These show that crawl selection based on PageRank, indegree and trans-domain indegree all allow better retrieval effectiveness than a simple breadth-first crawl of the same size. PageRank is the most reliable and effective method. Trans-domain indegree can outperform PageRank, but over multiple crawl iterations it is less effective and more unstable. Finally we experiment with combinations of crawl selection methods and per-domain page limits, which yield crawls with greater potential NDCG than PageRank.

REFERENCES

• 1: 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]
• 2: R. Baeza-Yates and C. Castillo. Crawling the infinite web. Journal of Web Engineering, 6(1):49--72, 2007.
• 3: Ricardo Baeza-Yates , Carlos Castillo , Mauricio Marin , Andrea Rodriguez, Crawling a country: better strategies than breadth-first for web page ordering, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062768]
• 4: Ziv Bar-Yossef , Andrei Z. Broder , Ravi Kumar , Andrew Tomkins, Sic transit gloria telae: towards an understanding of the web's decay, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988716]
• 5: P. Boldi, and M. Santini, and S. Vigna. Paradoxical effects in pagerank incremental computations. Internet Mathematics, 2(3):387--404, 2005.
• 6: Junghoo Cho , Hector Garcia-Molina, The Evolution of the Web and Implications for an Incremental Crawler, Proceedings of the 26th International Conference on Very Large Data Bases, p.200-209, September 10-14, 2000
• 7: Junghoo Cho , Hector Garcia-Molina , Lawrence Page, Efficient crawling through URL ordering, Computer Networks and ISDN Systems, v.30 n.1-7, p.161-172, April 1, 1998
• 8: Junghoo Cho , Uri Schonfeld, RankMass crawler: a crawler with high personalized pagerank coverage guarantee, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 9: Anirban Dasgupta , Arpita Ghosh , Ravi Kumar , Christopher Olston , Sandeep Pandey , Andrew Tomkins, The discoverability of the web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242630]
• 10: Dennis Fetterly , Nick Craswell , Vishwa Vinay, Measuring the Search Effectiveness of a Breadth-First Crawl, Proceedings of the 31th European Conference on IR Research on Advances in Information Retrieval, April 06-09, 2009, Toulouse, France [doi>10.1007/978-3-642-00958-7_35]
• 11: Dennis Fetterly , Mark Manasse , Marc Najork , Janet Wiener, A large-scale study of the evolution of web pages, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775246]
• 12: Monika R. Henzinger , Allan Heydon , Michael Mitzenmacher , Marc Najork, Measuring index quality using random walks on the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1291-1303, May 17, 1999
• 13: Kalervo Järvelin , Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.422-446, October 2002 [doi>10.1145/582415.582418]
• 14: Hsin-Tsang Lee , Derek Leonard , Xiaoming Wang , Dmitri Loguinov, IRLbot: scaling to 6 billion pages and beyond, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367556]
• 15: Marc A. Najork , Hugo Zaragoza , Michael J. Taylor, Hits on the web: how does it compare?, 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.1277823]
• 16: 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]
• 17: Sandeep Pandey , Christopher Olston, Crawl ordering by search impact, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341535]
• 18: Knut Magne Risvik , Yngve Aasheim , Mathias Lidal, Multi-Tier Architecture for Web Search Engines, Proceedings of the First Conference on Latin American Web Congress, p.132, November 10-12, 2003
• 19: Jaime Teevan , Eytan Adar , Rosie Jones , Michael A. S. Potts, Information re-retrieval: repeat queries in Yahoo's logs, 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.1277770]

INDEX TERMS

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

General Terms:
Experimentation, Measurement

Keywords:
corpus selection, crawl ordering, web crawling