Data deduplication

https://www.pinecone.io/learn/series/faiss/locality-sensitive-hashing/

• In FineWeb, they tried both global dedup (all 96 CC snapshots, going from new to old) or per snapshot dedup
  • per snapshot dedup was better because:
    • the data from oldest crawl taken that was kept (10% of the original data) was actually of worse quality than the 90% of data that was removed; kept data contains more ads, incoherent lists of keywords and generally badly formatted text than originally removed data.
    • The main improvement gained from deduplication lies in the removal of large clusters of duplicates with hundreds of thousands of documents present in all crawls, while further deduplication of clusters with a small number of duplicates (less than ~100, i.e., the number of crawls) can harm performance.

MinHash and LSH

MinHash and LSH are basically a two-stage hack for “find near-duplicates without doing all pairwise comparisons”. Think of them as:

• MinHash: “How similar are these two sets?” (fast approximate Jaccard)
• LSH: “Given a bunch of MinHash signatures, which pairs are worth checking more carefully?”

1. First: how we model “duplicates”

For text / records de-duplication, a common model is:

1. Turn each object into a set of features

   • Documents → set of shingles (e.g. all 5-grams of characters, or all word bigrams)

   • Web pages → set of URLs / tokens they link to

   • User profiles → set of normalized fields (email, phone, etc.)

2. Use Jaccard similarity to measure near-duplication:

$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$ Naively, to de-duplicate N items you’d need to compute Jaccard for O(N²) pairs → impossible at scale.

2. MinHash: fast approximate Jaccard

Core trick: turn big sets into short signatures such that

Probability that MinHash(A) = MinHash(B) equals Jaccard(A,B)

2.1 Intuition

Imagine you could:

1. Pick a random permutation π of the universe of all possible shingles.

2. For a set $S$, define

   ${\text{MinHash}}_{\pi }(S)=\underset{x\in S}{\min }\pi (x)$

Then you can prove:

$\mathrm{Pr}[{\text{MinHash}}_{\pi }(A)={\text{MinHash}}_{\pi }(B)]=J(A,B)$

Intuition: under a random order, the first element that appears in $A\cup B$ is equally likely to be any element of the union. It will be in the intersection $A\cap B$ exactly a fraction $J(A,B)$ of the time.

So one MinHash value is a Bernoulli trial with success prob = Jaccard.

2.2 From one MinHash to a signature

We can’t generate true permutations on huge universes, so we approximate them with independent hash functions $h_1,\dots ,h_k$

For each object/set $S$:

• For each hash function $h_i$​:
  compute $\text{sig}[i]={\min }_{x\in S}{h}_i(x)$

That gives you a k-dimensional MinHash signature (often k ≈ 64–256).

For two sets $A,B$:

• The fraction of positions where their signatures are equal is an unbiased estimator of their Jaccard similarity.

3. LSH: using signatures to find candidate pairs

Now we have MinHash signatures for all N documents. But we still don’t want to compare all N² pairs of signatures.

Locality-Sensitive Hashing (LSH) uses a neat trick (“banding”) to only propose pairs that are likely to be similar.

3.1 Banding idea

Take each signature (length k) and:

1. Split it into b bands of r rows each, so $k=b\cdot r$
   • Example: k = 100, r = 5 → b = 20 bands.
2. For each band:
   • Treat the r entries in that band as a little tuple
   • Hash that tuple into a bucket.
3. If two signatures fall in the same bucket in at least one band, they become a candidate pair.

Then:

• You only compute full Jaccard (or more expensive similarity) on candidate pairs.
• That makes the overall pipeline sub-quadratic in practice.

How FineWeb used MinHash and LSH

• In FineWeb, they used 5-grams and 112 hash functions for the MinHash deduplication. Each 5-gram is hashed with each of the 112 hash functions, and a document signature is obtained by taking the minimum hash value (minhash) across all 5-grams for each hash function.
• They further split the resulting 112 minhashes into 14 buckets of 8 hashes each. Documents are matched if they have the same 8 minhashes in at least one of the 14 buckets.
• They perform a transitive clustering step where documents A, B and C will be in the same duplicate cluster if A and C are duplicates and B and C are duplicates, even if A and B do not have 8 matching MinHashes in any bucket with each other

How do they choose their parameters?

• They target documents that are at least 75% similar

• By this, they mean that, with these parameters, the probability that two documents with a n-gram similarity / Jaccard similarity ($s$) of 0.7, 0.75, 0.8 and 0.85 would be identified as duplicates would be 56%, 77%, 92% and 98.8%, respectively.

• This split therefore will match documents that are at least 75% similar with a high probability, and almost guarantee that documents with similarities of 85% or above will be matched.

• How to get these numbers?

• These values can be computed by taking the following probabilities:

  • that the two documents would have the same value for a given hash function, s
  • that they do not have the same 8 minhashes in one bucket, $1-s^8$;
  • that they do not have the same 8 minhashes in any of the 14 buckets, $(1-s^8{)}^{14};$
  • finally that they have the same 8 minhashes on at least one of the 14 buckets, $1-(1-s^8{)}^{14}$

• We can plot these probabilities (here they compare with the setup from RefinedWeb, with 9000 hashes, divided into 450 buckets of 20 hashes)

  •