Entity resolution

Deep dive

How it works

Parts:

• normalizer — lowercases, strips punctuation and accents, parses fields
• blocker — computes cheap keys; records sharing a key become candidate pairs
• comparator — maps each field pair to a level (agree, similar, disagree)
• scorer — sums log-likelihood ratios ln(m/u) over fields (Fellegi-Sunter)
• decider — two thresholds: match, clerical review, non-match
• clusterer — union-find over matched pairs; one component is one entity

1. Normalize: lowercase, strip punctuation and accents, collapse whitespace, parse into fields (name, date, address). Most of the accuracy comes from this step.
2. Block: compute one or more keys per record (surname prefix + birth year, first-name prefix + full date, phonetic code). Records sharing any key form a candidate pair (multi-pass blocking). Oversized blocks (a key like "smith") are capped or refined, not exploded.
3. Compare: per field, map the pair to a discrete level: exact agree, similar (Jaro-Winkler ≥ 0.80), disagree. Missing values contribute weight 0.
4. Score: sum the weights ln(m/u) of the observed levels. Rare agreements (a birth date, u = 3×10⁻⁴ in the code) add a lot; common ones (a city) add little. Disagreement adds ln((1-m)/(1-u)), negative.
5. Decide: score ≥ upper: match; ≤ lower: non-match; in between: clerical review.
6. Cluster: union the matched pairs; each component is one entity. Give it a stable id and keep the evidence (pairs, scores).

records ─normalize─► block keys ─► candidate pairs ─► field levels ─► Σ ln(m/u)
                                                                          │
                          entity ids ◄─ union-find ◄─ score ≥ upper ◄─────┘

Code

Blocking, Jaro-Winkler, Fellegi-Sunter scoring and union-find clustering from std only. The m/u values are illustrative; estimate them with EM or labelled pairs. Compiled and run with asserts: the three Smith variants cluster together, "John Smith" (other birth date, city) stays apart.

use std::collections::{HashMap, HashSet};

pub struct Rec { pub name: String, pub dob: String, pub city: String }

/// Lowercase, keep letters/digits, single spaces.
pub fn norm(s: &str) -> String {
    let t: String = s.chars().map(|c| if c.is_alphanumeric() { c.to_ascii_lowercase() } else { ' ' }).collect();
    t.split_whitespace().collect::<Vec<_>>().join(" ")
}

pub fn jaro(a: &[u8], b: &[u8]) -> f64 {
    if a.is_empty() || b.is_empty() { return if a.len() == b.len() { 1.0 } else { 0.0 }; }
    let w = (a.len().max(b.len()) / 2).saturating_sub(1);
    let (mut ma, mut mb) = (vec![false; a.len()], vec![false; b.len()]);
    let mut m = 0.0;
    for i in 0..a.len() {
        for j in i.saturating_sub(w)..(i + w + 1).min(b.len()) {
            if !mb[j] && a[i] == b[j] { ma[i] = true; mb[j] = true; m += 1.0; break; }
        }
    }
    if m == 0.0 { return 0.0; }
    let bm: Vec<u8> = (0..b.len()).filter(|&j| mb[j]).map(|j| b[j]).collect();
    let (mut k, mut t) = (0, 0.0);
    for i in (0..a.len()).filter(|&i| ma[i]) { if a[i] != bm[k] { t += 0.5; } k += 1; }
    (m / a.len() as f64 + m / b.len() as f64 + (m - t) / m) / 3.0
}

pub fn jaro_winkler(a: &str, b: &str) -> f64 {
    let (x, y) = (a.as_bytes(), b.as_bytes());
    let j = jaro(x, y);
    let l = x.iter().zip(y).take(4).take_while(|(p, q)| p == q).count() as f64;
    j + l * 0.1 * (1.0 - j) // prefix bonus, only meaningful when j is already high
}

/// Blocking keys: a pair becomes a candidate if it shares ANY key (multi-pass).
fn keys(r: &Rec) -> Vec<String> {
    let last = r.name.split(' ').last().unwrap_or("");
    let first = r.name.split(' ').next().unwrap_or("");
    let p = |s: &str, n: usize| s.chars().take(n).collect::<String>();
    vec![format!("a|{}|{}", p(last, 4), p(&r.dob, 4)), format!("b|{}|{}", p(first, 3), r.dob)]
}

pub fn candidates(recs: &[Rec], max_block: usize) -> HashSet<(usize, usize)> {
    let mut blocks: HashMap<String, Vec<usize>> = HashMap::new();
    for (i, r) in recs.iter().enumerate() { for k in keys(r) { blocks.entry(k).or_default().push(i); } }
    let mut out = HashSet::new();
    for ids in blocks.values().filter(|v| v.len() <= max_block) { // oversized blocks are skipped, not exploded
        for (x, &i) in ids.iter().enumerate() { for &j in &ids[x + 1..] { out.insert((i, j)); } }
    }
    out
}

/// Fellegi-Sunter: sum of ln(m/u) per field level. m = P(level | match), u = P(level | non-match).
/// Levels: 0 = agree, 1 = partial, 2 = disagree. Probabilities here are illustrative; estimate them with EM.
const NAME: [(f64, f64); 3] = [(0.85, 0.002), (0.10, 0.02), (0.05, 0.978)];
const DOB: [(f64, f64); 3] = [(0.95, 0.0003), (0.0, 0.0), (0.05, 0.9997)];
const CITY: [(f64, f64); 3] = [(0.85, 0.05), (0.0, 0.0), (0.15, 0.95)];

fn w(t: &[(f64, f64); 3], lvl: usize) -> f64 { let (m, u) = t[lvl]; if m == 0.0 { 0.0 } else { (m / u).ln() } }

pub fn score(a: &Rec, b: &Rec) -> f64 {
    let s = jaro_winkler(&a.name, &b.name);
    let nl = if s >= 0.92 { 0 } else if s >= 0.80 { 1 } else { 2 };
    let dl = if a.dob == b.dob { 0 } else { 2 };
    let cl = if a.city == b.city { 0 } else { 2 };
    w(&NAME, nl) + w(&DOB, dl) + w(&CITY, cl)
}

pub struct Dsu(Vec<usize>);
impl Dsu {
    pub fn new(n: usize) -> Self { Dsu((0..n).collect()) }
    pub fn find(&mut self, mut x: usize) -> usize {
        while self.0[x] != x { self.0[x] = self.0[self.0[x]]; x = self.0[x]; } // path halving
        x
    }
    pub fn union(&mut self, a: usize, b: usize) { let (a, b) = (self.find(a), self.find(b)); if a != b { self.0[a] = b; } }
}

/// Returns (cluster id per record, pairs needing manual review).
pub fn resolve(recs: &[Rec], lo: f64, hi: f64) -> (Vec<usize>, Vec<(usize, usize)>) {
    let mut dsu = Dsu::new(recs.len());
    let mut review = Vec::new();
    for (i, j) in candidates(recs, 1000) {
        let s = score(&recs[i], &recs[j]);
        if s >= hi { dsu.union(i, j); } else if s >= lo { review.push((i, j)); }
    }
    ((0..recs.len()).map(|i| dsu.find(i)).collect(), review)
}

Complexity and constants

• Pairs: n(n-1)/2 without blocking; with blocks, Σ bᵢ(bᵢ-1)/2. One block of 10⁵ records alone costs 5×10⁹ pairs, so block-size distribution matters more than average size.
• Jaro-Winkler is O(len²) worst case with a match window of max(len)/2-1; the code above measured about 115 ns per call on 14-byte names (release build, includes its small allocations). Exact-field checks are a few ns.
• Memory: block index is one u32 id per record per key, plus the key; union-find is 4-8 B per record.
• Cost drivers: candidate-pair count (dominant), string comparator calls, and the memory for block tables. Cost grows with pairs, not with records.

Efficiency

• Cost: compute, set by the number of candidate pairs: n(n-1)/2 without blocking, Σ bᵢ(bᵢ-1)/2 with blocks. A Jaro-Winkler call measured about 115 ns on 14-byte names (release build, includes small allocations); exact-field checks are a few ns. Memory: one u32 id per record per block key, union-find 4-8 B per record. Normalization and clustering are linear.
• Levers:
  • better blocking — n² down to about Σ bᵢ² (computed above) — always; use multi-pass blocking and measure recall on labelled pairs
  • exact fields before string distance, drop a pair once the best reachable score is under the lower threshold — fewer comparator calls — pair loop
  • normalize once, hash block keys to u64, reuse buffers — no allocation in the pair loop (order of) — large runs
  • incremental matching — compare new records only against their blocks — streams
  • shard by block key — blocks are independent, union-find per shard then merge — multi-core
• Naive → standard → state of the art:
  • compare all pairs · 5×10¹¹ pairs for 1M records
  • multi-pass blocking plus Fellegi-Sunter scoring · pairs scale with Σ bᵢ²
  • incremental, sharded blocking with cheap-first comparisons · cost follows new records only

Implementation notes

• Sort-based blocking (sort records by key, scan runs) avoids a hash table of vectors and streams from disk; a block-size cap protects against hot keys.
• Fit m and u by EM on the comparison vectors of candidate pairs (Fellegi and Sunter's model assumes fields are conditionally independent given match status; Splink uses this). Keep a labelled sample for threshold choice and for measuring precision and recall.
• Use term-frequency adjustment: agreeing on a rare surname is stronger evidence than agreeing on "smith". Scale u by the value frequency.
• Persist cluster ids and pair evidence so merges can be explained and undone; a changed threshold re-labels entities, so version the ids.

Pitfalls

• Chaining: A~B and B~C merge A and C even if A and C clearly differ. Use a higher merge threshold than the review threshold, cap cluster size, or re-cluster big components (hierarchical or correlation clustering).
• Blocking on a dirty field (typo in the surname prefix) silently loses true matches; recall cannot be seen from the output, only from labelled data.
• Jaro-Winkler's prefix bonus favours shared starts; Winkler's version applies it only above a Jaro score of about 0.7, which the code above omits for brevity.
• Treating missing as disagreement penalizes sparse records; give missing its own level with weight 0.
• Independence of fields is false for correlated fields (city and postcode); the score overcounts. Prefer one combined field or calibrate thresholds on labels.
• Twins, same-address households and junk values ("N/A", "000000") create confident false matches: blocklist junk values.

Variants and alternatives

In production

Census and statistical agencies, health and population data linkage, customer data platforms, KYC and sanctions screening, bibliography and knowledge-graph construction.

Implementations

Sources

• Fellegi, Sunter, A Theory for Record Linkage, JASA 1969. paper
• Hernández, Stolfo, The merge/purge problem for large databases, SIGMOD 1995. paper
• Elmagarmid, Ipeirotis, Verykios, Duplicate Record Detection: A Survey, IEEE TKDE 2007. paper
• Christen, Data Matching, Springer 2012. book
• Papadakis, Skoutas, Thanos, Palpanas, Blocking and Filtering Techniques for Entity Resolution: A Survey, ACM Computing Surveys 2020. paper
• Linacre et al., Splink: Free software for probabilistic record linkage at scale, IJPDS 2022. paper · code