Do not crawl in the dust: different urls with similar text

ABSTRACT

We consider the problem of DUST: Different URLs with Similar Text. Such duplicate URLs are prevalent in web sites, as web server software often uses aliases and redirections, and dynamically generates the same page from various different URLrequests. We present a novel algorithm, DustBuster, for uncovering DUST; that is, for discovering rules that transform a given URL to others that are likely to have similar content. DustBuster mines DUST effectively from previous crawl logs or web server logs, without examining page contents. Verifying these rules via sampling requires fetching few actual web pages. Search engines can benefit from information about DUST to increase the effectiveness of crawling, reduce indexing overhead, and improve the quality of popularity statistics such as PageRank.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: Z. Bar-Yossef, I. Keidar, and U. Schonfeld. Do not crawl in the DUST: different URLs with similar text. Technical Report CCIT Report #601, Dept. Electrical Engineering, Technion, 2006.
• 3: Krishna Bharat , Andrei Broder, Mirror, mirror on the Web: a study of host pairs with replicated content, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1579-1590, May 17, 1999
• 4: K. Bharat, A. Z. Broder, J. Dean, and M. R. Henzinger. A comparison of techniques to find mirrored hosts on the WWW. IEEE Data Engin. Bull., 23(4):21--26, 2000.
• 5: M. Bognar. A survey on abstract rewriting. Available online at: www.di.ubi.pt/~desousa/1998-1999/logica/mb.ps, 1995.
• 6: Sergey Brin , James Davis , Héctor García-Molina, Copy detection mechanisms for digital documents, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.398-409, May 22-25, 1995, San Jose, California, United States
• 7: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 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: E. Di Iorio, M. Diligenti, M. Gori, M. Maggini, and A. Pucci. Detecting Near-replicas on the Web by Content and Hyperlink Analysis. In Proc. 11th WWW, 2003.
• 10: 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
• 11: Héctor García-Molina , Luis Gravano , Narayanan Shivakumar, dSCAM: finding document copies across multiple databases, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.68-79, December 18-20, 1996, Miami Beach, Florida, United States
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Google Inc. Google sitemaps. http://sitemaps.google.com.
• 14: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 15: Timothy C. Hoad , Justin Zobel, Methods for identifying versioned and plagiarized documents, Journal of the American Society for Information Science and Technology, v.54 n.3, p.203-215, February 1, 2003 [doi>10.1002/asi.10170]
• 16: N. Jain, M. Dahlin, and R. Tewari. Using bloom filters to refine web search results. In Proc. 7th WebDB, pages 25--30, 2005.
• 17: Terence Kelly , Jeffrey Mogul, Aliasing on the world wide web: prevalence and performance implications, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511484]
• 18: S. J. Kim, H. S. Jeong, and S. H. Lee. Reliable evaluations of URL normalization. In Proc. 4th ICCSA, pages 609--617, 2006.
• 19: H. Liang. A URL-String-Based Algorithm for Finding WWW Mirror Host. Master's thesis, Auburn University, 2001.
• 20: Frank McCown , Michael L. Nelson, Evaluation of crawling policies for a web-repository crawler, Proceedings of the seventeenth conference on Hypertext and hypermedia, August 22-25, 2006, Odense, Denmark [doi>10.1145/1149941.1149972]
• 21: Uri Schonfeld , Ziv Bar-Yossef , Idit Keidar, Do not crawl in the DUST: different URLs with similar text, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135992]
• 22: Narayanan Shivakumar , Hector Garcia-Molina, Finding Near-Replicas of Documents and Servers on the Web, Selected papers from the International Workshop on The World Wide Web and Databases, p.204-212, March 27-28, 1998

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
URL normalization, anti-aliasing, crawling, duplicate detection, search engines