Winnowing: local algorithms for document fingerprinting

S. SchleimerD. WilkersonA. Aiken

article2003SIGMOD1,391 citations

Introduces the winnowing algorithm, a local document fingerprinting technique behind the widely used MOSS system that provides formal guarantees for detecting shared substrings while minimizing the number of stored hash values.

Listen

Digital documents are easily replicated, modified, and reused across platforms, driving a strong operational need for reliable detection of both exact and partial text duplication. Conventional copy-detection strategies frequently rely on document fingerprinting, which hashes short overlapping character sequences known as k-grams and selects a sample of those hashes. However, standard sampling approaches—such as keeping only hashes matching a fixed modulo value—lack mathematical guarantees, leaving unpredictable gaps where extensive duplicated passages can completely escape detection.

The article introduces and evaluates "winnowing," a local document-fingerprinting algorithm designed to guarantee the detection of any shared substring meeting a user-defined length threshold. It establishes a theoretical performance baseline for local fingerprinting algorithms and demonstrates winnowing's efficiency in both controlled benchmarks and production systems.

The authors evaluated the framework through theoretical proofs and empirical tests. To ensure credibility across different environments, they tested the method on 8 megabytes of randomized text, a production-scale dataset of 500,000 web pages encompassing nearly 2 billion computed hashes, and operational longitudinal data from MOSS, a widely used software similarity and plagiarism detection service. The algorithm maintains guarantees by evaluating sliding windows of hashes and systematically choosing the minimum hash within each window, ensuring that document matches depend solely on local text content rather than global position.

The article yields four core findings. First, winnowing provides a strict detection guarantee, identifying at least one shared marker in any matching passage of length w + k − 1, where w is the window size and k is the substring length. Second, winnowing achieves an expected fingerprint density of 2 / (w + 1), performing within 33% of the theoretical lower bound of 1.5 / (w + 1) proven for all local algorithms. Third, while standard modulo-based sampling fails to select fingerprints over long non-random stretches—evidenced by a run of nearly 30,000 characters without a single selected hash in web data—winnowing reliably captures samples across all segments. Fourth, repetitive, low-entropy content creates redundant minimums that degrade efficiency; the authors resolved this by introducing "robust winnowing," an enhancement that breaks ties by preserving previously selected hashes to keep sampling density bounded at 1 / w.

These findings indicate that document similarity systems can guarantee copy detection while maintaining highly compact indexes and low computational overhead. Decoupling document-specific normalization front-ends from the core hashing engine minimizes software complexity and engineering costs when supporting diverse file types. Furthermore, querying databases with variable window sizes enables flexible trade-offs between rapid resemblance checks and thorough containment audits.

Organizations implementing copy or plagiarism detection should adopt robust winnowing to avoid index bloat on repetitive data and use 64-bit rolling hash functions to prevent accidental collisions. Systems should separate format-specific preprocessing—such as removing whitespace or normalizing variable names—from the language-agnostic fingerprinting pipeline. Operations should also filter out known boilerplate, like standard license text, by pre-indexing template materials to suppress non-actionable matches.

The theoretical model relies on the assumption of uniformly distributed hash values; although real-world data deviates from this assumption due to repetitive text patterns, robust winnowing effectively neutralizes this limitation. Because k-gram matching provides coarse initial boundaries, users requiring exact substring borders may need a secondary refinement step, such as suffix trees, on detected pairs. Overall, multi-year production evidence from MOSS confirms high confidence in the algorithm's reliability, reporting no false positives and robust deterrence against illicit copying.

University of California Berkeley University of Illinois Chicago detection algorithm document similarity engine document fingerprinting local fingerprinting algorithm robust winnowing

Schleimer et al (2003).pdf

Paper: Similarity Search in High Dimensions via Hashing, Aristides Gionis et al. (1999). Introduces locality-sensitive hashing to map high-dimensional data points to hash buckets with collision guarantees, establishing the broader randomized hashing paradigm that underpins local document fingerprinting algorithms.
Paper: Fast subsequence matching in time-series databases, Christos Faloutsos et al. (1994). Establishes sliding-window indexing mechanisms for robust subsequence matching, providing foundational sliding-window principles applied in local fingerprint selection.

Paper: Inverted files for text search engines, Justin Zobel et al. (2006). Provides a comprehensive study of inverted files and index compression techniques essential for indexing and rapidly querying large collections of document fingerprints generated by winnowing.
Paper: An Improved Data Stream Summary: The Count-Min Sketch and Its Applications, Graham Cormode et al. (2005). Introduces the Count-Min Sketch to efficiently summarize high-volume streaming data with bounded error, advancing compact approximate counting over streams of hashed document features.
Paper: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm, Philippe Flajolet et al. (2007). Presents a near-optimal cardinality estimation algorithm via hash-based register analysis, extending sublinear randomized hashing techniques to multi-stream multiset tracking.
Paper: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Alexandr Andoni et al. (2008). Surveys and advances near-optimal approximate nearest-neighbor hashing algorithms, building further theoretical bounds on randomized hash-based similarity search.
Paper: Duplicate Record Detection: A Survey, Ahmed K. Elmagarmid et al. (2007). Surveys duplicate record detection and matching techniques across databases, integrating token-level and character-level similarity methods into broader record-linkage architectures.

Cover for 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 fingerprinting 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.

Topics

detection algorithm document similarity engine fingerprint hash value hashing sliding windows software software complexity trade

Keywords

document fingerprinting local fingerprinting algorithm robust winnowing copy detection plagiarism detection service string matching

1. INTRODUCTION
2. BACKGROUND AND RELATED WORK
2.1 Desirable properties
2.2 Karp-Rabin String Matching
2.3 All-to-all matching
2.4 Other techniques
3. WINNOWING
3.1 Expected Density
3.1.1 Comparison to 0 mod p at same density
3.1.2 Comparison to 0 mod p with guarantee
3.2 Queries
4. LOCAL ALGORITHMS
5. EXPERIMENTS
5.1 Experiments with Web Data
5.2 Plagiarism Detection
6. CONCLUSIONS
7. ACKNOWLEDGMENTS
8. REFERENCES

Knowls

Knowl 1 — The Winnowing Algorithm for Document Fingerprinting
model/method
Winnowing is a local document fingerprinting algorithm designed to detect shared substrings between documents while bounding the number of retained fingerprints. Given text preprocessed to discard formatting or semantic noise, the document is decomposed into contiguous substrings of length $k$ ( $k$ -grams), and a hash value $h_i$ is computed for each $k$ -gram at index $i$ , yielding a sequence $h_1, h_2, \dots, h_n$ .

Let $k$ be the noise threshold (minimum match length of interest) and $t$ be the guarantee threshold (the shortest substring match guaranteed to be detected), where $t \ge k$ . The window size is set to: $w = t - k + 1$

For every window of $w$ consecutive hashes $W_i = (h_i, h_{i+1}, \dots, h_{i+w-1})$ for $1 \le i \le n - w + 1$ , the algorithm selects the minimum hash value. If multiple positions within the window share the minimum value, the rightmost occurrence is selected. The set of all uniquely selected hashes across all windows, stored alongside their document positions, constitutes the document fingerprints.

Because every substring of length at least $t$ contains at least $w$ consecutive $k$ -grams (and therefore spans at least one complete window of length $w$ ), winnowing guarantees that at least one identical fingerprint is selected from both copies of any shared substring of length $\ge t$ .
Knowl 2 — Expected Fingerprint Density of Winnowing
theoretical result
Under the assumption that $k$ -gram hash values are independent and uniformly distributed random variables over a sufficiently large domain where ties within small windows have negligible probability, the expected density $d$ (the expected proportion of computed $k$ -gram hashes selected as fingerprints) of the winnowing algorithm with window size $w$ is: $d = \frac{2}{w + 1}$

This density is derived by charging each selected fingerprint to the leftmost window that selects it. For any two adjacent overlapping windows $W_{i-1}$ and $W_i$ , which together span a union interval of $w + 1$ hashes, window $W_i$ is charged for selecting a new fingerprint if and only if the minimum hash in the union interval is located at the leftmost position (index $i-1$ ) or at the rightmost position (index $i+w-1$ ). Each of these two disjoint events occurs with probability $\frac{1}{w+1}$ , giving an expected charge of $\frac{2}{w+1}$ per window.
Knowl 3 — Local Document Fingerprinting Algorithms and Substring Match Guarantee
definition
A document fingerprinting algorithm is defined as local if its selection of a fingerprint from any window of $w$ consecutive hashes $h_i, \dots, h_{i+w-1}$ is determined strictly by a selection function: $S: H^w \to \{0, 1, \dots, w-1\}$ where $H$ is the set of possible hash values. For every window $h_i, \dots, h_{i+w-1}$ , the algorithm selects the hash at position $i + S(h_i, \dots, h_{i+w-1})$ as a fingerprint without relying on global position or document-level coordinates.

Any local algorithm with window size $w = t - k + 1$ is guaranteed to detect all matching pairs of substrings of length at least $t$ across documents (where $k$ is the $k$ -gram noise threshold). Because a shared substring of length $\ge t$ contains at least $w$ consecutive $k$ -gram hashes, it contains at least one identical full window $W$ , and the locality of $S$ ensures the identical fingerprint is chosen in both documents.
Knowl 4 — Theoretical Lower Bound on the Density of Local Fingerprinting Algorithms
theoretical result
For any local fingerprinting algorithm operating on independent and uniformly distributed random hash inputs with noise threshold $k$ and guarantee threshold $t = w + k - 1$ (window size $w$ ), the fingerprint density $d$ satisfies the lower bound: $d \ge \frac{1.5}{w + 1}$

By applying the Cauchy-Schwarz inequality to the collision probability across overlapping windows, this bound can be strengthened to: $d \ge \frac{1.5 + \frac{1}{2w}}{w + 1}$

Because the winnowing algorithm achieves an expected density of $d = \frac{2}{w+1}$ , its density is within $33\%$ of the theoretical lower bound for any local fingerprinting algorithm.
Knowl 5 — Robust Winnowing for Low-Entropy Sequences
algorithm
Standard winnowing selects a new fingerprint in almost every window on low-entropy strings (e.g., long sequences of repeating characters where every $k$ -gram hash is identical) because the rightmost minimum advances with each step, causing the density to approach $1$ . Robust winnowing modifies the tie-breaking rule to favor previously selected hashes:
Input: A sequence of hashes $h_1, h_2, \dots, h_n$ and window size $w$
Output: A set of selected fingerprints with global positions
for each window $W_i = (h_i, h_{i+1}, \dots, h_{i+w-1})$ from $i = 1$ to $n - w + 1$ :
    Find the minimum hash value in $W_i$
    if the minimum hash value equals the hash selected in $W_{i-1}$ and that hash index is still in $W_i$ :
        Select the same hash instance as in $W_{i-1}$
    else:
        Select the rightmost occurrence of the minimum hash in $W_i$
    Record the selected hash and its document position if not previously recorded
On repetitive strings of identical hashes, robust winnowing reduces fingerprint density from asymptotically $1$ to $\frac{1}{w}$ (one fingerprint per window length). For any matching substring of length $\ge t = w + k - 1$ , robust winnowing guarantees selecting the same hash value in both occurrences within a distance of at most $w - 1$ positions.
Knowl 6 — Circular Buffer Implementation of the Winnowing Algorithm
algorithm
Winnowing can be implemented in $O(1)$ amortized time per hash using a circular buffer of size $w$ . A full scan of the window is required only when the previous minimum leaves the window:
Input: Stream of hashes from next_hash() and window size $w$
Output: Document fingerprints emitted via record(hash, position)
Initialize circular array $h$ of size $w$ with all elements set to $\infty$
$r \leftarrow 0$
$\text{min} \leftarrow 0$
while more hashes are available:
     $r \leftarrow (r + 1) \bmod w$
     $h[r] \leftarrow \text{next\_hash}()$
    if $\text{min} = r$ :
        for $i \leftarrow (r - 1) \bmod w$ down to $r$ (circular leftward scan):
            if $h[i] < h[\text{min}]:$
                 $\text{min} \leftarrow i$
        record( $h[\text{min}]$ , global_pos( $\text{min}, r, w$ ))
    else:
        if $h[r] \le h[\text{min}]:$
             $\text{min} \leftarrow r$
            record( $h[\text{min}]$ , global_pos( $\text{min}, r, w$ ))
In the common case where the previous minimum remains in the current window, only a single comparison against the new hash $h[r]$ is performed. Replacing $h[r] \le h[\text{min}]$ with $h[r] < h[\text{min}]$ converts this procedure into robust winnowing.
Knowl 7 — Density Analysis of Safe 0 mod p Fingerprinting
theoretical result
The Safe $0 \bmod p$ algorithm modifies modular hash sampling to guarantee detection of matches of length $\ge t = w + k - 1$ by classifying hashes as:
- Good: if the hash is $0 \bmod p$
- Bad: if the hash and the $w-1$ hashes to its left are not Good
- Ugly: otherwise
All non-Ugly (Good or Bad) hashes are selected as fingerprints. For independent uniformly distributed hashes with $P = 1/p$ , the probability of a position being non-Ugly is $f(P) \approx P + e^{-wP}$ . Minimizing $f(P)$ yields the optimal probability parameter: $P_0 = \frac{\ln w}{w}$

At this optimal setting, the minimum expected density of Safe $0 \bmod p$ is: $f(P_0) = \frac{1 + \ln w}{w}$

This density is strictly higher than winnowing's expected density of $\frac{2}{w+1}$ for all practical window sizes $w$ .
Knowl 8 — Match Detection Failure Rate of 0 mod p Sampling at Equivalent Density
theoretical result
When selecting fingerprints by choosing hashes satisfying $h \equiv 0 \pmod p$ with parameter $p = 1/d = (w + 1)/2$ (matching the expected density $d = \frac{2}{w+1}$ of winnowing with window size $w$ ), the algorithm provides no guarantee of detecting matches.

For a specific shared substring of guarantee length $t = w + k - 1$ containing $w$ consecutive $k$ -gram hashes, assuming independent uniformly distributed hash values and large $w$ , the probability that $0 \bmod p$ sampling fails to select any fingerprint within the sequence is: $(1 - d)^w = \left(1 - \frac{2}{w + 1}\right)^w \approx e^{-\frac{2w}{w+1}} \approx e^{-2} \approx 13.5\%$

Thus, at identical expected density, $0 \bmod p$ sampling misses approximately $13.5\%$ of threshold-length matches that winnowing is guaranteed to detect.

Knowl 9 — Empirical Density and Gap Comparison on Web Data

data/table

An evaluation on 500,000 HTML pages (Stanford WebBase) compared winnowing against $0 \bmod 50$ sampling using noise threshold $k = 50$ and window size $w = 100$ :

Metric	Winnowing	$0 \bmod 50$
Total bytes	7,182,692,852	7,182,692,852
Text bytes	1,940,576,448	1,940,576,448
Hashes computed	1,940,576,399	1,940,576,399
Fingerprints selected	38,530,846	38,761,128
Measured density	0.019855	0.019974
Expected density	0.019802	0.020000
Longest run with no fingerprint	-	29,983

While both methods matched their expected average densities across the entire corpus ( $\,\approx 0.0198$ for winnowing and $\,\approx 0.0200$ for $0 \bmod 50$ ), $0 \bmod 50$ exhibited a maximum gap of 29,983 non-whitespace, non-tag characters without a single fingerprint due to low-entropy repetitive strings. Winnowing strictly bounded the gap to at most one fingerprint per window of 100 hashes.

Knowl 10 — Power-Law Distribution of k-Gram Hash Frequencies in Web Documents
empirical result
In an analysis of $k$ -gram hashes ( $k=50$ ) across 20,000 Web pages, the relationship between the rank $r$ of a hash (sorted in descending order of occurrence frequency) and its frequency $f$ follows a power law: $f \propto r^{-0.7}$

Log-log linear regression on the plateau endpoints of the frequency-rank data yields a power-law slope of approximately $-0.70$ for all computed $k$ -gram hashes and $-0.68$ for fingerprints selected by winnowing. In both distributions, $82\%$ of distinct hashes occur exactly once, $14\%$ occur twice, and $2\%$ occur three times, while repetitive boilerplate text (such as menus, legal disclaimers, and repeated script strings) constitutes the high-frequency tail.

Coverage note — Omitted general background discussions of Karp-Rabin hashing, related copy-detection systems (SCAM, p-matches, DRM), and MOSS operational anecdotes (e.g., UI merging heuristics and front-end tokenization) as they do not form the paper's core technical contributions.

References

1.Arvind Arasu, Junghoo Cho, Hector Garcia-Molina, Andreas Paepcke, and Sriram Raghavan. Searching the web. ACM Transactions on Internet Technology (TOIT), 1(1):2–43, 2001.
2.Brenda S. Baker. On finding duplication and near-duplication in large software systems. In L. Wills, P. Newcomb, and E. Chikofsky, editors, Second Working Conference on Reverse Engineering, pages 86–95, Los Alamitos, California, 1995. IEEE Computer Society Press.
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, and Héctor García-Molina. Copy detection mechanisms for digital documents. In Proceedings of the ACM SIGMOD Conference, pages 398–409, 1995.
5.Andrei Broder. On the resemblance and containment of documents. In SEQS: Sequences ’91, 1998.
6.Andrei Broder, Steve Glassman, Mark Manasse, and Geoffrey Zweig. Syntactic clustering of the web. In Proceedings of the Sixth International World Wide Web Conference, pages 391–404, April 1997.
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 and Michael O. Rabin. Pattern-matching algorithms. IBM Journal of Research and Development, 31(2):249–260, 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.

Citation

MLA

Schleimer, S., et al. “Winnowing”. Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, 2003, pp. 76–85, https://doi.org/10.1145/872757.872770.

APA

Schleimer, S., Wilkerson, D. S., & Aiken, A. (2003). Winnowing. Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, 76–85. https://doi.org/10.1145/872757.872770

Chicago

Schleimer, S., D. S. Wilkerson, and A. Aiken. 2003. “Winnowing”. Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, 76–85. https://doi.org/10.1145/872757.872770.

Harvard

Schleimer, S., Wilkerson, D.S. and Aiken, A. (2003) “Winnowing”, Proceedings of the 2003 ACM SIGMOD international conference on Management of data. ACM, pp. 76–85. Available at: https://doi.org/10.1145/872757.872770.

Vancouver

1. Schleimer S, Wilkerson DS, Aiken A (2003) Winnowing. In: Proceedings of the 2003 ACM SIGMOD international conference on Management of data. ACM, pp 76–85

BibTeX

@inproceedings{Schleimer_2003, series={SIGMOD/PODS03}, title={Winnowing: local algorithms for document fingerprinting}, url={http://dx.doi.org/10.1145/872757.872770}, DOI={10.1145/872757.872770}, booktitle={Proceedings of the 2003 ACM SIGMOD international conference on Management of data}, publisher={ACM}, author={Schleimer, Saul and Wilkerson, Daniel S. and Aiken, Alex}, year={2003}, month=June, pages={76–85}, collection={SIGMOD/PODS03} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Winnowing: local algorithms for document fingerprinting

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — The Winnowing Algorithm for Document Fingerprinting

Knowl 2 — Expected Fingerprint Density of Winnowing

Knowl 3 — Local Document Fingerprinting Algorithms and Substring Match Guarantee

Knowl 4 — Theoretical Lower Bound on the Density of Local Fingerprinting Algorithms

Knowl 5 — Robust Winnowing for Low-Entropy Sequences

Knowl 6 — Circular Buffer Implementation of the Winnowing Algorithm

Knowl 7 — Density Analysis of Safe 0 mod p Fingerprinting

Knowl 8 — Match Detection Failure Rate of 0 mod p Sampling at Equivalent Density

Knowl 9 — Empirical Density and Gap Comparison on Web Data

Knowl 10 — Power-Law Distribution of k-Gram Hash Frequencies in Web Documents

References

Citation

BibTeX

Access the Paper