Near-duplicate detection by instance-level constrained clustering

ABSTRACT

For the task of near-duplicated document detection, both traditional fingerprinting techniques used in database community and bag-of-word comparison approaches used in information retrieval community are not sufficiently accurate. This is due to the fact that the characteristics of near-duplicated documents are different from that of both "almost-identical" documents in the data cleaning task and "relevant" documents in the search task. This paper presents an instance-level constrained clustering approach for near-duplicate detection. The framework incorporates information such as document attributes and content structure into the clustering process to form near-duplicate clusters. Gathered from several collections of public comments sent to U.S. government agencies on proposed new regulations, the experimental results demonstrate that our approach outperforms other near-duplicate detection algorithms and as about as effective as human assessors.

REFERENCES

• 1: 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
• 2: Y. Bernstein and J. Zobel, A scalable system for identifying co-derivative documents. In Proceedings of the String Processing and Information Retrieval Symposium (SPIRE), page 55--67, Padova, Italy, September 2004.
• 3: 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
• 4: 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]
• 5: 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]
• 6: K. Gwet. Kappa Statistic is not Satisfactory for Assessing the Extent of Agreement between Raters. Statistical Methods for Inter-rater Reliability Assessment, No.1, April 2002.
• 7: 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]
• 8: Dan Klein , Sepandar D. Kamvar , Christopher D. Manning, From Instance-level Constraints to Space-Level Constraints: Making the Most of Prior Knowledge in Data Clustering, Proceedings of the Nineteenth International Conference on Machine Learning, p.307-314, July 08-12, 2002
• 9: 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]
• 10: Donald Metzler , Yaniv Bernstein , W. Bruce Croft , Alistair Moffat , Justin Zobel, Similarity measures for tracking information flow, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099695]
• 11: NIST, "Secure Hash Standard", Federal Information Processing Standards Publication 180--1, 1995.
• 12: N. Shivakumar and H. Garcia-Molina. SCAM: a copy detection mechanism for digital documents. In Proc. International Conference on Theory and Practice of Digital Libraries, Austin, Texas, June 1995.
• 13: S.W. Shulman, E-Rulemaking: Issues in Current Research and Practice. International Journal of Public Administration 28: 621--641. 2005.
• 14: Kiri Wagstaff , Claire Cardie, Clustering with Instance-level Constraints, Proceedings of the Seventeenth International Conference on Machine Learning, p.1103-1110, June 29-July 02, 2000
• 15: E. P. Xing, A. Y. Ng, M. I. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. In Advances in Neural Information Processing Systems, 2003.
• 16: Hui Yang , Jamie Callan, Near-duplicate detection for eRulemaking, Proceedings of the 2005 national conference on Digital government research, May 15-18, 2005, Atlanta, Georgia
• 17: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to Ad Hoc information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.334-342, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384019]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
clustering, duplicate detection, public comments