Detecting near-duplicates for web crawling

ABSTRACT

Near-duplicate web documents are abundant. Two such documents differ from each other in a very small portion that displays advertisements, for example. Such differences are irrelevant for web search. So the quality of a web crawler increases if it can assess whether a newly crawled web page is a near-duplicate of a previously crawled web page or not. In the course of developing a near-duplicate detection system for a multi-billion page repository, we make two research contributions. First, we demonstrate that Charikar's fingerprinting technique is appropriate for this goal. Second, we present an algorithmic technique for identifying existing f-bit fingerprints that differ from a given fingerprint in at most k bit-positions, for small k. Our technique is useful for both online queries (single fingerprints) and all batch queries (multiple fingerprints). Experimental evaluation over real data confirms the practicality of our design.

REFERENCES

• 1: Arvind Arasu , Junghoo Cho , Hector Garcia-Molina , Andreas Paepcke , Sriram Raghavan, Searching the Web, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.2-43, Aug. 2001 [doi>10.1145/383034.383035]
• 2: Arvind Arasu , Hector Garcia-Molina , Stanford University, Extracting structured data from Web pages, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872799]
• 3: Abdullah N. Arslan , Ömer Egecioglu, Dictionary Look-Up within Small Edit Distance, Proceedings of the 8th Annual International Conference on Computing and Combinatorics, p.127-136, August 15-17, 2002
• 4: Brenda S. Baker, A theory of parameterized pattern matching: algorithms and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.71-80, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167115]
• 5: B. S. Baker, On finding duplication and near-duplication in large software systems, Proceedings of the Second Working Conference on Reverse Engineering, p.86, July 14-16, 1995
• 6: Krishna Bharat , Andrei Broder, Mirror, mirror on the Web: a study of host pairs with replicated content, Proceeding of the eighth international conference on World Wide Web, p.1579-1590, May 1999, Toronto, Canada
• 7: Krishna Bharat , Andrei Broder , Jeffrey Dean , Monika R. Henzinger, A comparison of techniques to find mirrored hosts on the WWW, Journal of the American Society for Information Science, v.51 n.12, p.1114-1122, Oct. 2000 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1025>3.0.CO;2-0]
• 8: 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
• 9: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 10: Gerth Stølting Brodal , Leszek Gasieniec, Approximate Dictionary Queries, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.65-74, June 10-12, 1996
• 11: Gerth Stølting Brodal , S. Venkatesh, Improved bounds for dictionary look-up with one error, Information Processing Letters, v.75 n.1-2, p.57-59, July 2000 [doi>10.1016/S0020-0190(00)00079-X]
• 12: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 13: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276781]
• 14: 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
• 15: Andrei Z. Broder , Marc Najork , Janet L. Wiener, Efficient URL caching for world wide web crawling, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775247]
• 16: Soumen Chakrabarti, Mining the Web: Discovering Knowledge from HyperText Data, Science & Technology Books, 2002
• 17: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 18: Zhiyuan Chen , Nick Koudas , Flip Korn , S. Muthukrishnan, Selectively estimation for Boolean queries, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.216-225, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335225]
• 19: 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
• 20: Abdur Chowdhury , Ophir Frieder , David Grossman , Mary Catherine McCabe, Collection statistics for fast duplicate document detection, ACM Transactions on Information Systems (TOIS), v.20 n.2, p.171-191, April 2002 [doi>10.1145/506309.506311]
• 21: Finding Interesting Associations without Support Pruning, Proceedings of the 16th International Conference on Data Engineering, p.489, February 28-March 03, 2000
• 22: Jack G. Conrad , Cindy P. Schriber, Constructing a text corpus for inexact duplicate detection, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009131]
• 23: James W. Cooper , Anni R. Coden , Eric W. Brown, Detecting similar documents using salient terms, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584835]
• 24: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 25: Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1467-1479, May 17, 1999
• 26: S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman. Indexing by latent semantic analysis. J American Society for Information Science, 41(6):391--407, 1990.
• 27: Michelangelo Diligenti , Frans Coetzee , Steve Lawrence , C. Lee Giles , Marco Gori, Focused Crawling Using Context Graphs, Proceedings of the 26th International Conference on Very Large Data Bases, p.527-534, September 10-14, 2000
• 28: Danny Dolev , Yuval Harari , Nathan Linial , Noam Nisan , Michal Parnas, Neighborhood preserving hashing and approximate queries, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.251-259, January 23-25, 1994, Arlington, Virginia, United States
• 29: Sanjay Ghemawat , Howard Gobioff , Shun-Tak Leung, The Google file system, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 30: Aristides Gionis , Dimitrios Gunopulos , Nick Koudas, Efficient and tumble similar set retrieval, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.247-258, May 21-24, 2001, Santa Barbara, California, United States
• 31: D. Greene, MParnas, and FYao. Multi-index hashing for information retrieval. In Proc. 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pages 722--731, 1994.
• 32: Khaled M. Hammouda , Mohamed S. Kamel, Efficient Phrase-Based Document Indexing for Web Document Clustering, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1279-1296, October 2004 [doi>10.1109/TKDE.2004.58]
• 33: T. H. Haveliwala, A. Gionis, and P. Indyk. Scalable techniques for clustering the web. In Proc. 3rd Intl. Workshop on the Web and Databases (WebDB 2000), pages 129--134, May 2000.
• 34: Taher H. Haveliwala , Aristides Gionis , Dan Klein , Piotr Indyk, Evaluating strategies for similarity search on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511502]
• 35: Monika Henzinger, Finding near-duplicate web pages: a large-scale evaluation of algorithms, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148222]
• 36: 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]
• 37: D. A. Huffman. A method for the construction of minimum-redundancy codes. In Proc. Institute of Radio Engineering, volume 40, pages 1098--1102, Sept. 1952.
• 38: Sachindra Joshi , Neeraj Agrawal , Raghu Krishnapuram , Sumit Negi, A bag of paths model for measuring structural similarity in Web documents, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956822]
• 39: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 40: Aleksander Kołcz , Abdur Chowdhury , Joshua Alspector, Improved robustness of signature-based near-replica detection via lexicon randomization, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014127]
• 41: 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
• 42: Udi Manber, Finding similar files in a large file system, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.2-2, January 17-21, 1994, San Francisco, California
• 43: Filippo Menczer , Gautam Pant , Padmini Srinivasan , Miguel E. Ruiz, Evaluating topic-driven web crawlers, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.241-249, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383995]
• 44: M. Minsky and S. Papert. Perceptrons. MIT Press, 1969.
• 45: Athicha Muthitacharoen , Benjie Chen , David Mazières, A low-bandwidth network file system, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 46: 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]
• 47: W. Pugh and M. R. Henzinger. Detecting duplicate and near-duplicate files. United States Patent 6,658,423, granted on Dec 2, 2003, 2003.
• 48: Sean Quinlan , Sean Dorward, Venti: A New Approach to Archival Storage, Proceedings of the Conference on File and Storage Technologies, p.89-101, January 28-30, 2002
• 49: M. O. Rabin. Fingerprinting by random polynomials. Technical Report Report TR-15-81, Center for Research in Computing Techonlogy, Harvard University, 1981.
• 50: Saul Schleimer , Daniel S. Wilkerson , Alex Aiken, Winnowing: local algorithms for document fingerprinting, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872770]
• 51: N. Shivakumar and H. Garcia-Molina. SCAM: A copy detection mechanism for digital documents. In Proceedings of the 2nd International Conference on Theory and Practice of Digital Libraries, 1995.
• 52: A. Yao and F. Yao. The complexity of searching in an ordered random table. In Proc. 17th Annual Symposium on Foundations of Computer Science (FOCS 1976), pages 173--177, 1976.
• 53: Andrew C. Yao , Frances F. Yao, Dictionary look-up with one error, Journal of Algorithms, v.25 n.1, p.194-202, Oct. 1997 [doi>10.1006/jagm.1997.0875]

INDEX TERMS

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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms; Permutations and combinations

General Terms:
Algorithms

Keywords:
fingerprint, hamming distance, near-duplicate, search, similarity, sketch, web crawl, web document