Shingling

Shingling extracts overlapping sequences of k consecutive tokens from a document. For the phrase 'the quick brown fox', 3-shingles are: ['the quick brown', 'quick brown fox']. This contiguity preserves local word order, making it more robust than bag-of-words models for detecting paraphrased or slightly reordered content. The window slides one token at a time, ensuring comprehensive coverage of all possible subsequences.

Each shingle is passed through a hash function (e.g., MD5, SHA-1) to produce a fixed-size integer fingerprint. This achieves two goals: dimensionality reduction—a document is represented as a compact set of integers rather than variable-length strings—and uniform distribution across the hash space. The set of hashed shingles becomes the document's sketch, enabling constant-time lookups and set-based comparisons.

Near-duplicate detection relies on the Jaccard Index: the size of the intersection of two shingle sets divided by the size of their union. A score of 0.85+ typically indicates near-duplicate content.

• Formula: J(A,B) = |A ∩ B| / |A ∪ B|
• Example: If doc A has 100 shingles and doc B shares 92, Jaccard = 0.92
• Threshold tuning: Lower thresholds catch more paraphrases; higher thresholds reduce false positives

Pairwise Jaccard computation across millions of documents is computationally prohibitive. MinHash compresses shingle sets into compact signatures of n hash values, where the probability of signature collision equals the Jaccard similarity. Documents are then bucketed using LSH bands, ensuring only candidate pairs within the same bucket are compared exhaustively. This reduces complexity from O(N²) to near-linear.

The choice of k (shingle width in tokens) critically impacts detection granularity:

• k=1 (unigrams): Degrades to bag-of-words; loses all word order. High recall, low precision.
• k=3–5: Standard for web documents. Captures short phrases while tolerating minor edits.
• k=8–10: Used for code clone detection or highly structured text. High precision, low recall.

Larger k values increase specificity but miss smaller reused fragments.

Raw text must be normalized before shingling to prevent superficial differences from breaking matches:

• Case folding: Convert all tokens to lowercase
• Punctuation stripping: Remove or normalize punctuation marks
• Stop word handling: Optionally remove high-frequency function words to focus on content-bearing terms
• Stemming/Lemmatization: Reduce words to root forms (e.g., 'running' → 'run')
• Unicode normalization: Apply NFC or NFD to standardize character encodings

The primary statistical measure used to compare two shingled documents. It calculates the similarity between two sets by dividing the size of their intersection by the size of their union. In the context of shingling, a high Jaccard Index indicates a significant overlap of contiguous token subsequences, flagging the documents as near-duplicates.

• Formula: J(A, B) = |A ∩ B| / |A ∪ B|
• Scale: 0 (no overlap) to 1 (identical sets)

A locality-sensitive hashing (LSH) technique that generates a compact, fixed-size fingerprint for a document. Unlike standard hashing, similar documents produce hashes with a small Hamming distance. This allows for efficient near-duplicate detection by comparing fingerprints rather than raw shingle sets, dramatically reducing computational complexity.

• Key Property: Inputs with small differences yield outputs with small differences.
• Use Case: Google's original crawler used Simhash for web-scale deduplication.

An optimization technique used when the set of shingles is too large to compare directly. MinHash compresses large sets into compact signatures while preserving the Jaccard similarity between them. Locality-Sensitive Hashing (LSH) then buckets these signatures so that only candidates within the same bucket are compared, avoiding an O(n²) pairwise comparison.

• Function: Reduces dimensionality while preserving similarity.
• Benefit: Enables sub-linear query time for nearest neighbor search.

A metric that measures the cosine of the angle between two non-zero vectors in a multi-dimensional space. When shingles are vectorized using techniques like TF-IDF, cosine similarity quantifies semantic closeness. A score of 1 indicates identical orientation (and thus high similarity), while 0 indicates orthogonality.

• Contrast: Unlike the Jaccard Index, which operates on discrete sets, cosine similarity operates on continuous vector representations.
• Range: -1 to 1 (typically 0 to 1 for text frequency vectors).

A numerical statistic that reflects the importance of a token to a document within a corpus. Before shingles are hashed or compared, Term Frequency-Inverse Document Frequency (TF-IDF) weighting can be applied to give higher weight to rare, discriminative shingles and lower weight to common ones.

• TF: How often a shingle appears in a document.
• IDF: How rare the shingle is across all documents.
• Effect: Prevents common stop-word shingles from dominating similarity scores.

A space-efficient probabilistic data structure used to test whether a shingle is a member of a set. It allows for rapid, memory-efficient duplicate detection with a controllable false positive rate, but guarantees no false negatives. This is useful for quickly discarding documents that definitely do not share shingles with a target set.

• Guarantee: 100% recall (no false negatives).
• Trade-off: Accepts a configurable rate of false positives to save memory.