Skip to main content

Blocking

By

Record Linkage Field Guide

Goal: Find records in two datasets that refer to the same real-world person/entity.
Process: Clean -> Block -> Compare -> Classify -> Evaluate

Step 1: Clean Data

Step 2: Blocking

Blocking = split records into groups (blocks) by a blocking key,
then compare records ""only within the same block**.
It's grouping, not filtering: no record is removed, only pointless paris are skipped.

5H1W

5W1H Blocking
Who records from both datasets
What separate records into smaller groups
When after cleaning, before detailed comparison
Where comparisons happen only inside each block
Why full comparison is too big and slow → smaller blocks are much faster
How a rule (blocking key) decides the grouping

Why Blocking?

Problem: Comparing every pairs of records is too slow, and real data has millions of records.

  • Without blocking: 100 x 100 = 10,000 comparisons
  • With blocking: e.g. 1,000 comparisons

Benefit: Far fewer comparison -> much faster
Cost: A true match placed in different blocks is never compared -> lost forever

Blocking Keys

A blocking key is a rule that turns ONE record into a value.
Records with the same key go into the same block.

  • Exact match only: "lew" ≠ "lwe" -> different blocks
  • A key can be a whole column, part of one, a combination, or an encoding:
    • postcode -> 3350
    • first 3 letters of last_name -> lew
    • first letter of first_name + birth year -> j1986
    • soundex(last_name) -> L200
  • Common keys: surname, DOB, postcode

Multiple keys: run each key separately, then take union (∪) of all candidate pairs.
A true match only needs to survive one key to be caught.

Good vs Bad Keys

Check two things for each candidate key:

  1. Number of distinct values: few values -> huge blocks -> barely faster
    • Watch for uneven values too: one common = one giant block
  2. Reliability: is the value usually correct?
    • Errors: typos, OCR(smith -> 5mith)
    • Missing: blank values
    • Changes over time: moved house, changed surname
Key Distinct values Reliability Verdict
gender 2 (only saves ~50%) good ❌ too few values
state 8, uneven (NSW ~30%) good ❌ too few values
blood type 8, uneven (O+ ~40%) often missing ❌
phone/email many often missing ❌
postcode many changes when moving ✅ candidate
surname many typos, marriage, name order ✅ with soundex
DOB many typos only ✅ candidate

Goal: the middle ground. Enough values for small blocks, reliable enough not to split true matches.
There's no perfect way, always a trade-off -> use multiple keys.

Blocking methods

Standard Blocking

Records with exactly the same key -> same block.

  • ✅ Simple, fast
  • ❌ Any type in the key -> split apart

Phonetic Blocking (Soundex)

Key = how a name sounds. Keep the first letter, turn consonants into digits, drop vowels.

  • smith / smyth -> S530 ✅ same block
  • ✅ Fixes vowel typos and similar-sounding letters
  • ❌ First letter must be correct (5mith fails)
  • ❌ Built for English names (Zhang / Chang -> Z520 / C520)

Sorted Neighbourhood

Sort all records by key, slide a window down the list, compare records inside the window.

  • lewis / lewiss -> sorted next to each other ✅
  • ✅ Keys only need to be close, not equal
  • ❌ Type at the start of the key -> sorted far apart
  • Window size trad-off: small = fast but misses more, large = catches more but slower
Standard Phonetic (Soundex) Sorted Neighbourhood
Blocking key value from record (e.g. DOB + first letter) encoded value (e.g. soundex(last_name)) any key (plain or encoded)
How key is used group by key group by key sort by key
Pairs come from same block same block same window
Match type exact exact (on the code) not exact (close in sorted order)
Pairs generated records from different datasets only records from different datasets only records from different datasets only
Handles nothing: any typo splits spelling variants that sound alike (smith / smyth) typos near the end (lewis / lewiss)
Fails on any typo first-letter errors, non-English names typos near the start (smith / 5mith)
Size control depends on key's distinct values depends on key's distinct values window size

Q-gram Blocking

Q-gram:

  • split the value into overlapping pieces of q letters (smith → sm, mi, it, th) →
  • make keys from the full list + lists with some pieces dropped (any combination) →
  • a record goes into one block per key (exact match on the key) →
  • records sharing any key become candidate pairs.
Standard Phonetic (Soundex) Sorted Neighbourhood Q-gram
Blocking key value from record (e.g. DOB + first letter) encoded value (e.g. soundex(last_name)) any key (plain or encoded) q-gram lists of a value (e.g. bigrams of last_name)
How key is used group by key group by key sort by key group by each sub-list key
Keys per record 1 1 1 many
Pairs come from same block same block same window same block (any shared sub-list)
Match type exact exact (on the code) not exact (close in sorted order) not exact (most pieces shared)
Pairs generate different datasets only different datasets only different datasets only different datasets only
Handles nothing: any typo splits spelling variants that sound alike (smith / smyth) typos near the end (lewis / lewiss) typos anywhere, incl. first letter (smith / 5mith)
Fails on any typo first-letter errors, non-English names typos near the start (smith / 5mith) too many typos, very short values
Size control key's distinct values key's distinct values window size threshold (how many pieces can be dropped)
Speed fast fast fast slow (many blocks per record)

SLK-581

SLK-581: standard blocking with one long combined key (exact match).

  • 2nd, 3rd, 5th letters of family name
  • 2nd, 3rd letters of given name
  • DOB as ddmmyyyy
  • sex code: m → 1, f → 2, unknown → 9
  • e.g. jeffrey lewis, 10/12/1987, m: lewis → ews, jeffrey → ef, 10121987, 1 → key = ewsef101219871
  • Missing name → 999 / 99; short name padded with 2
  • ✅ tiny blocks, very fast ❌ any single error in name / DOB / sex → match lost

Measuring Blocking Quality

  • RR (Reduction Ratio): how much work was saved?
    Close to 1 = saved more comparisons. -> fast

RR=1−candidate pairsall possible pairsRR = 1 - \frac{\text{candidate pairs}}{\text{all possible pairs}}

  • PC (Pairs Completeness): how many true matches survived?
    Close to 1 = few matches lost.

PC=true matches in candidatesall true matchesPC = \frac{\text{true matches in candidates}}{\text{all true matches}}

  • PQ (Pairs Quality): how clean is the candidate list?
    Close to 1 = almost every candidate is a real match.

PQ=true matches in candidatescandidate pairsPQ = \frac{\text{true matches in candidates}}{\text{candidate pairs}}

Step 3: Compare Pairs

Step 4: Decide Match (Classification)

Step 5: Evaluate

Comments

Post a Comment