Online duplicate document detection: signature reliability in a dynamic retrieval environment

ABSTRACT

As online document collections continue to expand, both on the Web and in proprietary environments, the need for duplicate detection becomes more critical. Few users wish to retrieve search results consisting of sets of duplicate documents, whether identical duplicates or close matches. Our goal in this work is to investigate the phenomenon and determine one or more approaches that minimize its impact on search results. Recent work has focused on using some form of signature to characterize a document in order to reduce the complexity of document comparisons. A representative technique constructs a 'fingerprint' of the rarest or richest features in a document using collection statistics as criteria for feature selection. One of the challenges of this approach, however, arises from the fact that in production environments, collections of documents are always changing, with new documents, or new versions of documents, arriving frequently, and other documents periodically removed. When an enterprise proceeds to freeze a training collection in order to stabilize the underlying repository of such features and its associated collection statistics, issues of coverage and completeness arise. We show that even with very large training collections possessing extremely high feature correlations before and after updates, underlying fingerprints remain sensitive to subtle changes. We explore alternative solutions that benefit from the development of massive meta-collections made up of sizable components from multiple domains. This technique appears to offer a practical foundation for fingerprint stability. We also consider mechanisms for updating training collections while mitigating signature instability. Our research is divided into three parts. We begin with a study of the distribution of duplicate types in two broad-ranging news collections consisting of approximately 50 million documents. We then examine the utility of document signatures in addressing identical or nearly identical duplicate documents and their sensitivity to collection updates. Finally, we investigate a flexible method of characterizing and comparing documents in order to permit the identification of non-identical duplicates. This method has produced promising results following an extensive evaluation using a production-based test collection created by domain experts.

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: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 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: Jamie Callan , Margaret Connell, Query-based sampling of text databases, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.97-130, April 2001 [doi>10.1145/382979.383040]
• 5: 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]
• 6: 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]
• 7: D. P. Dabney, H. R. Turtle, J. G. Conrad, et. al. System and Method of Processing Formatted Text Documents in a Database. U.S. Patent App. No. 09/120,170, 1999.
• 8: O. Frieder, D. A. Grossman, A. Chowdhury, and G. Frieder. Efficiency considerations for scalable information retrieval servers. Journal of Digital Information, 1(5):26 pgs, Jan. 2000.
• 9: N. Heintze. Scalable document fingerprinting. In Proceedings of the Second USENIX Electronic Commerce Workshop, pages 191--200, Nov. 1996.
• 10: U. Manber. Finding similar files in a large file system. In USENIX Winter 1994 Technical Conference Proceedings (USENIX '94), pages 1--10, Jan. 1994.
• 11: Carmen Miller, Detecting duplicates: a searcher's dream come true, Online, v.14 n.4, p.27-34, Jul. 1990
• 12: M. J. Moroney. Facts from Figures, pages 334--370. Penguin Books, Middlesex, UK, 3rd edition, 1956.
• 13: Seung-Taek Park , David M. Pennock , C. Lee Giles , Robert Krovetz, Analysis of lexical signatures for finding lost or related documents, 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.564381]
• 14: T. A. Phelps and R. Wilensky. Robust hyperlinks: Cheap, everywhere, now. In Proceedings of the 8th Int'l Conference on Digital Documents and Electronic Publishing (DDEP '00). Springer-Verlag, Sept. 2000.
• 15: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 16: 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
• 17: Carol Tenopir , Pamela Cahn, TARGET & FREESTYLE: Dialog and Mead join the relevance ranks, Online, v.18 n.3, p.31-47, May 1994
• 18: P. Thompson, H. Turtle, B. Yang, and J. Flood. uppercase TREC-3 ad hoc experiments using the uppercase WIN system. In Proc. of TREC-3, pages 211--217. NIST, Nov. 1995.
• 19: Howard Turtle, Natural language vs. Boolean query evaluation: a comparison of retrieval performance, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.212-220, July 03-06, 1994, Dublin, Ireland
• 20: Howard Robert Turtle, Inference networks for document retrieval, University of Massachusetts, Amherst, MA, 1991
• 21: U. S. Department of Commerce/National Institute of Standards and Technology. Secure Hash Std, 1995.
• 22: Ellen M. Voorhees , Donna Harman, Overview of the sixth text REtrieval conference (TREC-6), Information Processing and Management: an International Journal, v.36 n.1, p.3-35, Jan. 2000 [doi>10.1016/S0306-4573(99)00043-6]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization
      H.3.3 Information Search and Retrieval
          Subjects: Selection process

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
data management, doc signatures, duplicate document detection