Improved robustness of signature-based near-replica detection via lexicon randomization

ABSTRACT

Detection of near duplicate documents is an important problem in many data mining and information filtering applications. When faced with massive quantities of data, traditional duplicate detection techniques relying on direct inter-document similarity computation (e.g., using the cosine measure) are often not feasible given the time and memory performance constraints. On the other hand, fingerprint-based methods, such as I-Match, are very attractive computationally but may be brittle with respect to small changes to document content. We focus on approaches to near-replica detection that are based upon large-collection statistics and present a general technique of increasing their robustness via multiple lexicon randomization. In experiments with large web-page and spam-email datasets the proposed method is shown to consistently outperform traditional I-Match, with the relative improvement in duplicate-document recall reaching as high as 40-60%. The large gains in detection accuracy are offset by only small increases in computational requirements.

REFERENCES

• 1: Peter Bailey , Nick Craswell , David Hawking, Engineering a multi-purpose test collection for web retrieval experiments, Information Processing and Management: an International Journal, v.39 n.6, p.853-871, November 2003 [doi>10.1016/S0306-4573(02)00084-5]
• 2: 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
• 3: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 4: 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
• 5: C. Buckley, C. Cardie, S. Mardisa, M. Mitra, D. Pierce, K. Wagstaff, and J. Walz. The smart/empire tipster ir system. In TIPSTER Phase III Proceedings. Morgan Kaufmann, 2000.
• 6: 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]
• 7: Jack G. Conrad , Xi S. Guo , Cindy P. Schriber, Online duplicate document detection: signature reliability in a dynamic retrieval environment, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956946]
• 8: J. Cooper , A. Coden , E. Brown, A Novel Method for Detecting Similar Documents, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 4, p.101.2, January 07-10, 2002
• 9: Tom Fawcett, "In vivo" spam filtering: a challenge problem for KDD, ACM SIGKDD Explorations Newsletter, v.5 n.2, December 2003 [doi>10.1145/980972.980990]
• 10: 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
• 11: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 12: J. Graham-Cummings. The spammers' compendium. In Proceedings of the Spam Conference, 2003.
• 13: T. Haveliwala, A. Gionis, and P. Indyk. Scalable techniques for clustering the web. In Proceedings of WebDB 2000, 2000.
• 14: D. Hawking. Overview of the TREC-9 web track. In TREC-9 NIST, 2000.
• 15: D. Hawking and N. Craswell. Overview of the trec-2001 web track. In TREC-10 NIST, 2001.
• 16: N. Heintze. Scalable document fingerprinting. In 1996 USENIX Workshop on Electronic Commerce, November 1996.
• 17: 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]
• 18: S. Ilyinsky, M. Kuzmin, A. Melkov, and I. Segalovich. An efficient method to detect duplicates of web documents with the use of inverted index. In Proceedings of the Eleventh International World Wide Web Conference, 2002.
• 19: A. Kołcz, , A. Chowdhury, and J. Alspector. Data duplication: An imbalance problem ? In Proceedings of the ICML'2003 Workshop on Learning from Imbalanced Datasets (II), 2003.
• 20: M. Sanderson. Duplicate detection in the Reuters collection. Technical Report TR-1997-5, Department of Computing Science, University of Glasgow, 1997.
• 21: 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
• 22: Ian Soboroff, Does WT10g look like the web?, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564475]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation, Reliability

Keywords:
data cleaning, deduplication, spam filtering, web mining