Bringing your dead links back to life: a comprehensive approach and lessons learned

ABSTRACT

This paper presents an experimental study of the automatic correction of broken (dead) Web links focusing, in particular, on links broken by the relocation ofWeb pages. Our first contribution is that we developed an algorithm that incorporates a comprehensive set of heuristics, some of which are novel, in a single unified framework. The second contribution is that we conducted a relatively large-scale experiment, and analysis of our results revealed the characteristics of the problem of finding movedWeb pages. We demonstrated empirically that the problem of searching for moved pages is different from typical information retrieval problems. First, it is impossible to identify the final destination until the page is moved, so the index-server approach is not necessarily effective. Secondly, there is a large bias about where the new address is likely to be and crawler-based solutions can be effectively implemented, avoiding the need to search the entire Web. We analyzed the experimental results in detail to show how important each heuristic is in real Web settings, and conducted statistical analyses to show that our algorithm succeeds in correctly finding new links for more than 70% of broken links at 95% confidence level.

REFERENCES

• 1: Helen Ashman , Hugh Davis , Jim Whitehead , Steve Caughey, Missing the 404: link integrity on the World Wide Web, Computer Networks and ISDN Systems, v.30 n.1-7, p.761-762, April 1, 1998
• 2: Helen Ashman, Electronic document addressing: dealing with change, ACM Computing Surveys (CSUR), v.32 n.3, p.201-212, Sept. 2000 [doi>10.1145/367701.367702]
• 3: 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]
• 4: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Computer Networks and ISDN Systems, v.29 n.8-13, p.1157-1166, Sep. 1997
• 5: M. Beynon, A. Flegg: Hypertext Request Integrity and User Experience. US Patent Application Publication, US 2004/0267726 A1, Dec, 2004.
• 6: M. Beynon, A. Flegg: Guaranteeing Hypertext Link Integrity. US Patent Application Publication, US 2005/0021997 A1, Jan. 2005.
• 7: Ziv Bar-Yossef , Idit Keidar , Uri Schonfeld, Do not crawl in the dust: different urls with similar text, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242588]
• 8: 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
• 9: Seung-Taek Park , David M. Pennock , C. Lee Giles , Robert Krovetz, Analysis of lexical signatures for improving information persistence on the World Wide Web, ACM Transactions on Information Systems (TOIS), v.22 n.4, p.540-572, October 2004 [doi>10.1145/1028099.1028101]
• 10: Hugh C. Davis, Referential integrity of links in open hypermedia systems, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.207-216, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276650]
• 11: Hugh C. Davis, Hypertext link integrity, ACM Computing Surveys (CSUR), v.31 n.4es, Dec. 1999 [doi>10.1145/345966.346026]
• 12: R. P. Dellavalle, E. J. hester, L. F. Heilig, A. L. Drake, J. W. Kuntzman, M. Graber, L. M. Schilling: Going, Going, Gone: Lost Internet References, Science 302(31), 2003: 787--788
• 13: Xin Dong , Alon Halevy , Jayant Madhavan, Reference reconciliation in complex information spaces, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066168]
• 14: Devanshu Dhyani , Wee Keong Ng , Sourav S. Bhowmick, A survey of Web metrics, ACM Computing Surveys (CSUR), v.34 n.4, p.469-503, December 2002 [doi>10.1145/592642.592645]
• 15: Roy T. Fielding, Maintaining distributed hypertext infostructures: welcome to MOMspider's Web, Computer Networks and ISDN Systems, v.27 n.2, p.193-204, Nov. 1994
• 16: David Ingham , Steve Caughey , Mark Little, Fixing the “broken-link” problem: the W3Objects approach, Computer Networks and ISDN Systems, v.28 n.7-11, p.1255-1268, May 1996
• 17: Katsumi Tanaka , N. Nishikawa , S. Hirayama , K. Nanba, Query Pairs as Hypertext Links, Proceedings of the Seventh International Conference on Data Engineering, p.456-463, April 08-12, 1991
• 18: Toshinari Iida, Natsumi Sawa, Atsuyuki Morishima, Shigeo Sugimoto, Hiroyuki Kitagawa. Efficient Search for Moved Web Pages. Proc. DEWS2007, 7 pages, 2007 (in Japanese).
• 19: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 20: Google Technology. http://www.google.com/technology/.
• 21: GVU Center, College of Computing Georgia Institute of Technology. GVU's 10th WWW User Survey. http://www.gvu.gatech.edu/user_surveys/survey-1998-10/.
• 22: A. Mood, F. Graybill, D. Boes. Introduction to the theory of statistics. McGraw-Hill, 1974.
• 23: A. Morishima, et al. Automatic Correction of Broken Web Links (full version of this paper) Technical Report, University of Tsukuba.
• 24: Thomas A. Phelps, Robert Wilensky: Robust Hyperlinks: Cheap, Everywhere, Now. DDEP/PODDP 2000: 28--43
• 25: Persistent URL Home Page. http://purl.oclc.org/.
• 26: RFC2396. Uniform Resource Identifiers (URI): Generic Syntax. http://www.ietf.org/rfc/rfc2396.txt.
• 27: Jonathan Shakes , Marc Langheinrich , Oren Etzioni, Dynamic reference sifting: a case study in the homepage domain, Computer Networks and ISDN Systems, v.29 n.8-13, p.1193-1204, Sep. 1997
• 28: L. Huxley, E. Place, D. Boyd and P. Cross. Planet SOSIG - A spring-clean for SOSIG: a systematic approach to collection management. http://www.ariadne.ac.uk/issue33/planet-sosig/.
• 29: Ellen Spertus , Lynn Andrea Stein, Squeal: a structured query language for the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.95-103, June 2000
• 30: Xenu's Link Sleuth. http://www.cs.washington.edu/lab/sw/LinkSleuth.html.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
broken links, integrity management