Cleaning data

Deduplication as a decision problem#

Exact duplicates are a GROUP BY. The real problem is entity resolution: deciding whether two records refer to the same real-world entity when no shared key exists.

The classical formulation is Fellegi and Sunter (1969), A Theory for Record Linkage, JASA. For a record pair $(a,b)$, compute a comparison vector $\gamma$ over fields, then the likelihood ratio:

$$ R(\gamma) \;=\; \frac{p(\gamma \mid (a,b) \in M)}{p(\gamma \mid (a,b) \in U)} $$

Where $M$ is the set of matched pairs and $U$ the set of unmatched pairs. Two thresholds $t_\mu > t_\lambda$ partition the decision into link, non-link and a clerical review region. Fellegi and Sunter prove this rule is optimal in the sense of minimising the review region for fixed error rates $\mu$ (false link) and $\lambda$ (false non-link).

The $m$- and $u$-probabilities per field are typically estimated by EM under a conditional independence assumption across fields, which is known to be violated in practice (surname and locality correlate) and is the main source of miscalibration.

Complexity and blocking#

Naive pairwise comparison is $O(n^2)$. At $n = 10^7$ that is $5 \times 10^{13}$ pairs, which is not feasible.

Blocking partitions records by a cheap key so that only within-block pairs are compared. Cost drops to $O!\left(\sum_b n_b^2\right)$, which for $B$ balanced blocks is $O(n^2/B)$. The trade-off is recall: any true pair split across blocks is lost permanently. Multi-pass blocking with several keys, unioned, mitigates this.

Sorted neighbourhood (Hernández and Stolfo, 1995) sorts on a key and compares within a sliding window of size $w$, giving $O(n \log n + nw)$.

MinHash with LSH (Broder, 1997) estimates Jaccard similarity in sublinear expected time. For a band of $r$ rows repeated $b$ times, the probability that a pair with Jaccard similarity $s$ becomes a candidate is:

$$ P(\text{candidate}) \;=\; 1 - \left(1 - s^{\,r}\right)^{b} $$

Choosing $r$ and $b$ sets the S-curve threshold at approximately $(1/b)^{1/r}$. This is the standard tool for near-duplicate text at scale, and the same machinery used to deduplicate LLM pretraining corpora.

Duplicate leakage in pretraining corpora#

Lee et al. (2022), Deduplicating Training Data Makes Language Models Better, ACL, found that C4 contains sequences repeated tens of thousands of times, and that over 1% of tokens emitted by models trained on undeduplicated data were memorised continuations. Deduplication with suffix arrays and MinHash reduced memorised output by roughly a factor of ten, cut training steps needed for equal perplexity, and — critically — removed train-test overlap that had inflated reported perplexity.

Carlini et al. (2023), Quantifying Memorization Across Neural Language Models, showed memorisation scales log-linearly with duplicate count. Deduplication is a privacy control, not only a quality control.

Constraint-based cleaning#

The database literature treats cleaning as repair under integrity constraints. Functional dependencies $X \to Y$ generalise to conditional functional dependencies (Bohannon et al., 2007), which hold on a subset of tuples selected by a pattern — for example, [country = "IN", pin] -> city.

Given violated constraints, the minimal repair problem is to find a database at minimum edit distance from the original satisfying all constraints. It is NP-hard for most useful constraint classes, so systems (HoloClean, Rekatsinas et al., 2017, VLDB) relax it to probabilistic inference over a factor graph combining constraints, quantitative statistics and external dictionaries.

Validation as an executable contract#

Rather than cleaning ad hoc, express expectations as assertions that run on every batch:

• Deequ (Schelter et al., 2018, Automating Large-Scale Data Quality Verification, VLDB) — declarative constraints over Spark, with incremental computation on growing datasets and anomaly detection over metric history.
• TensorFlow Data Validation (Breck et al., 2019, Data Validation for Machine Learning, SysML) — infers a schema from a baseline, then detects drift and skew against it in production.
• Great Expectations — the same idea, Python-native, with generated documentation.

Breck et al. (2017), The ML Test Score, IEEE Big Data, formalises this as a rubric. The data tests are the section most teams score zero on.

What to measure#

• Pairwise precision and recall on a hand-adjudicated sample of candidate pairs, not cluster-level accuracy, which is dominated by singletons.
• Reduction ratio for blocking: $1 - (\text{candidate pairs}) / \binom{n}{2}$, reported alongside pair completeness, the fraction of true matches surviving blocking. Optimising one alone is meaningless.
• Row counts at every stage, persisted. A cleaning step that changes its own removal rate week on week is an incident.

Reading#

• Fellegi and Sunter, A Theory for Record Linkage, JASA 1969.
• Christen, Data Matching, Springer 2012 — the standard book-length treatment.
• Lee et al., Deduplicating Training Data Makes Language Models Better, ACL 2022 — arxiv.org/abs/2107.06499
• Rekatsinas et al., HoloClean: Holistic Data Repairs with Probabilistic Inference, VLDB 2017 — arxiv.org/abs/1702.00820
• Schelter et al., Automating Large-Scale Data Quality Verification, VLDB 2018.

What to learn next#

• Handling missing data — the blanks left behind after cleaning.
• Train, test and validation splits — why the split has to come after the dedupe.
• Building a data pipeline — running these checks automatically, forever.