Crawl ordering by search impact

ABSTRACT

We study how to prioritize the fetching of new pages under the objective of maximizing the quality of search results. In particular, our objective is to fetch new pages that have the most impact, where the impact of a page is equal to the number of times the page appears in the top K search results for queries, for some constant K, e.g., K = 10. Since the impact of a page depends on its relevance score for queries, which in turn depends on the page content, the main difficulty lies in estimating the impact of the page before actually fetching it. Hence, impact must be estimated based on the limited information that is available prior to fetching page content, e.g., the URL string, number of in-links, referring anchortext

We formally characterize this problem and study its hardness. We leverage our formalism to design a new impact-driven crawling policy, and demonstrate its effectiveness using real world data. Our technique ensures that the crawler acquires content relevant to "tail topics" that are obscure but of interest to some users, rather than just redundantly accumulating content on popular topics.

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: 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
• 3: G. Casella and R. L. Berger. Statistical Inference. Duxbury, 2001.
• 4: Soumen Chakrabarti , Alan Frieze , Juan Vera, The influence of search engines on preferential attachment, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 5: Soumen Chakrabarti , Martin van den Berg , Byron Dom, Focused crawling: a new approach to topic-specific Web resource discovery, Proceedings of the eighth international conference on World Wide Web, p.1623-1640, May 1999, Toronto, Canada
• 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: 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 , Sourashis Roy, Impact of search engines on page popularity, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988676]
• 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: 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]
• 11: 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]
• 12: Subhash Khot, Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.136-145, October 17-19, 2004 [doi>10.1109/FOCS.2004.59]
• 13: 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]
• 14: 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]
• 15: Sandeep Pandey , Christopher Olston, User-centric Web crawling, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060805]
• 16: Matthew Richardson , Amit Prakash , Eric Brill, Beyond PageRank: machine learning for static ranking, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135881]
• 17: Search's Long Tail. http://blog.searchenginewatch.com/blog/050314-164653.
• 18: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 19: Ian Witten, Data Mining, Elsevier Science Inc., New York, NY, 2005
• 20: 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]
• 21: K. Yi, H. Yu, J. Yang, G. Xia, and Y. Chen. Efficient Maintenance of Materialized Top-k Views. In Proc. International Conference on Data Engineering, 2003.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
crawl ordering, impact-driven crawling, web crawling