The discoverability of the web

ABSTRACT

Previous studies have highlighted the high arrival rate of new contenton the web. We study the extent to which this new content can beefficiently discovered by a crawler. Our study has two parts. First,we study the inherent difficulty of the discovery problem using amaximum cover formulation, under an assumption of perfect estimates oflikely sources of links to new content. Second, we relax thisassumption and study a more realistic setting in which algorithms mustuse historical statistics to estimate which pages are most likely toyield links to new content. We recommend a simple algorithm thatperforms comparably to all approaches we consider.We measure the emphoverhead of discovering new content, defined asthe average number of fetches required to discover one new page. Weshow first that with perfect foreknowledge of where to explore forlinks to new content, it is possible to discover 90% of all newcontent with under 3% overhead, and 100% of new content with 9%overhead. But actual algorithms, which do not have access to perfectforeknowledge, face a more difficult task: one quarter of new contentis simply not amenable to efficient discovery. Of the remaining threequarters, 80% of new content during a given week may be discoveredwith 160% overhead if content is recrawled fully on a monthly basis.

REFERENCES

• 1: Peter Auer , Nicolò Cesa-Bianchi , Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning, v.47 n.2-3, p.235-256, May-June 2002 [doi>10.1023/A:1013689704352]
• 2: A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.
• 3: Brian E. Brewington , George Cybenko, How dynamic is the Web?, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.257-276, June 2000
• 4: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
• 5: 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
• 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: Fred Douglis , Anja Feldmann , Balachander Krishnamurthy , Jeffrey Mogul, Rate of change and other metrics: a live study of the world wide web, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, p.14-14, December 08-11, 1997, Monterey, California
• 9: J. ECoffman, Z. Liu, and R. R. Weber. Optimal robot scheduling for web search engines. Journal of Scheduling, 1(1):15--29, 1998.
• 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: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 13: Dennis Fetterly , Mark Manasse , Marc Najork, On the Evolution of Clusters of Near-Duplicate Web Pages, Proceedings of the First Conference on Latin American Web Congress, p.37, November 10-12, 2003
• 14: Dennis Fetterly , Mark Manasse , Marc Najork , Janet L. Wiener, A large-scale study of the evolution of web pages, Software—Practice & Experience, v.34 n.2, p.213-237, February 2004 [doi>10.1002/spe.577]
• 15: J. Gittins. Bandit Processes and Dynamic Allocation Indices. John Wiley, 1989.
• 16: Michael J. Kearns, Computational Complexity of Machine Learning, MIT Press, Cambridge, MA, 1990
• 17: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1481-1493, May 17, 1999
• 18: M. Mitzenmacher. A brief history of lognormal and power law distributions. Internet Mathematics, 1(2):226--251, 2004.
• 19: 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]
• 20: 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]
• 21: 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]
• 22: 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]
• 23: Petr Slavik , Eugene Kleinberg, Approximation algorithms for set cover and related problems, State University of New York at Buffalo, Buffalo, NY, 1998
• 24: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 25: 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.m Miscellaneous

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
crawling, discovery, greedy, max cover, set cover