Winnowing
Saul Schleimer, Daniel Shawcross Wilkerson, Alex Aiken · Proceedings - ACM-SIGMOD International Conference on Management of Data · 2003
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.
Cited by 1,095 works. doi:10.1145/872757.872770
Authors
References
- Syntactic clustering of the Web
- Finding similar files in a large file system
- On the resemblance and containment of documents
- Efficient randomized pattern-matching algorithms
- Copy detection mechanisms for digital documents
- On-line construction of suffix trees
- SCAM: A Copy Detection Mechanism for Digital Documents
- On finding duplication and near-duplication in large software systems
- Searching the Web
- The Psycho-Biology of Language