Winnowing: local algorithms for document fingerprinting

ABSTRACT

Digital content is for copying: quotation, revision, plagiarism, and file sharing all create copies. Document fingerprinting is concerned with accurately identifying copying, including small partial copies, within large sets of documents.We introduce the class of local document fingerprinting algorithms, which seems to capture an essential property of any finger-printing technique guaranteed to detect copies. We prove a novel lower bound on the performance of any local algorithm. We also develop winnowing, an efficient local fingerprinting algorithm, and show that winnowing's performance is within 33% of the lower bound. Finally, we also give experimental results on Web data, and report experience with MOSS, a widely-used plagiarism detection service.

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: 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
• 3: Brenda S. Baker and Udi Manber. Deducing similarities in java sources from bytecodes. In Proc. of Usenix Annual Technical Conf., pages 179--190, 1998.
• 4: 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
• 5: Andrei Broder. On the resemblance and containment of documents. In SEQS: Sequences '91, 1998.
• 6: 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
• 7: The Crystals. Da do run run, 1963.
• 8: Nevin Heintze. Scalable document fingerprinting. In 1996 USENIX Workshop on Electronic Commerce, November 1996.
• 9: James Joyce. Finnegans wake {1st trade ed.}. Faber and Faber (London), 1939.
• 10: Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
• 11: Sergio Leone, Clint Eastwood, Eli Wallach, and Lee Van Cleef. The Good, the Bad and the Ugly / Il Buono, Il Brutto, Il Cattivo (The Man with No Name). Produzioni Europee Associate (Italy) Production, Distributed by United Artists (USA), 1966.
• 12: Udi Manber. Finding similar files in a large file system. In Proceedings of the USENIX Winter 1994 Technical Conference, pages 1--10, San Fransisco, CA, USA, 17--21 1994.
• 13: Peter Mork, Beitao Li, Edward Chang, Junghoo Cho, Chen Li, and James Wang. Indexing tamper resistant features for image copy detection, 1999. URL: citeseer.nj.nec.com/mork99indexing.html.
• 14: Narayanan Shivakumar and Héctor García-Molina. SCAM: A copy detection mechanism for digital documents. In Proceedings of the Second Annual Conference on the Theory and Practice of Digital Libraries, 1995.
• 15: Esko Ukkonen. On-line construction of suffix trees. Algorithmica, 14:249--260, 1995.
• 16: George K. Zipf. The Psychobiology of Language. Houghton Mifltm Co., 1935.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Text analysis
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.1 Document and Text Editing
          Subjects: Document management

General Terms:
Algorithms, Design, Experimentation, Performance