Deduplication by containment

Detecting when one document is wholly contained inside another, which Jaccard similarity cannot do.

What it is

Containment measures the fraction of the smaller document's content that appears in the larger one.

Why it is needed

An exhibit contract inside a 200-page filing is a complete subset of it, but Jaccard scores it near zero because the filing is far larger. Containment scores it 1.0.

How it works

Documents are reduced to overlapping word shingles. Containment is the fraction of the smaller document's shingles present in the larger.

Formula

containment(A, B) = |shingles(A)  n  shingles(B)| / |shingles(A)|

with A the smaller document.

Jaccard, for contrast:
  J(A, B) = |A n B| / |A u B|

For a 20 KB contract inside a 400 KB filing, containment = 1.0 and Jaccard = 0.05.

shingle: a sliding window of 5 consecutive words
1 in 16 sampling: keep a shingle when its hash mod 16 is 0 — uniform, so unbiased
threshold 0.80: the containment above which a duplicate is declared

In this project

Five-word shingles, hash-sampled at one in sixteen to keep the index for 140 MB of filing text in the low millions of entries rather than tens of millions. The sampling is uniform, so the estimate is unbiased. Validated with controls before its result was trusted: a contract embedded in a filing scored 1.0000, the same contract reformatted scored 1.0000, an unrelated contract scored 0.0045.

Trade-offs

Advantages

Detects subset relationships Jaccard misses
Sampling makes it cheap at corpus scale
Survives reformatting

Limitations

Threshold is a judgement call
Sampling introduces variance on very short documents

Common mistakes

Using Jaccard for subset detection
Trusting a dedup result without a positive control — a detector that finds nothing may be one that cannot find anything

When to use it

Reach for it when

Corpora assembled from overlapping sources

How it interacts with the rest of the system

Provenance and reproducibilityCorpus acquisition and rate limiting

← All topics