Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Blocking for record linkage: reduce comparisons without hiding true matches

Last updated: 5 Oct 20265 min read
tutorial
IntermediateBy AITrove Editorial

Blocking limits candidate comparisons to plausible groups; a missed block can make a true link impossible to recover.

Calculate the comparison problem

Two files of 36,000 and 41,000 customer records would create roughly 1.48 billion cross-file pairs if every row were compared with every other row. Candidate generation narrows the search by keys such as verified postal district or a stable transaction token. The score stage can only judge candidates it receives. Exact linkage should remove proven matches first.

Use several defensible passes

One pass might block on postal district plus the first two letters of a normalized family name. Another can use a verified phone hash where policy allows it. A single misspelled surname or moved address will defeat the first pass, so union candidates from independent passes and deduplicate pair IDs. Do not use a sensitive attribute merely because it improves a benchmark; the data-use contract still governs.

Measure candidate recall on labeled pairs

Build a reviewed set of true matches that includes spelling changes, moves, missing fields and shared-household contacts. Candidate recall is the number of known true pairs generated divided by all known true pairs in that test set. This number does not prove recall for the whole population if the reviewed sample is unrepresentative. Audit sampling can deliberately cover rare error modes.

Inspect block sizes and skew

A block containing half the dataset saves little work and may exhaust memory, while thousands of singleton blocks may hide too many links. Report candidate pairs per pass, duplicate pairs across passes, maximum block size and reviewed-pair recall by subgroup. If a postcode is missing, define a fallback rather than placing all missing records in one enormous block.

Keep the candidate boundary explicit

A pair excluded by blocking is not a negative match decision. In the result ledger, distinguish never compared, compared and rejected, compared and accepted, and sent for review. This matters when a new blocking strategy changes measured customer counts: it changes the opportunity to match, not necessarily the underlying population.

Implementation

python
from collections import defaultdict

def postcode_candidates(left_customers, right_customers):
    right_blocks = defaultdict(list)
    for customer in right_customers:
        key = (customer["postal_district"], customer["surname_key"][:2])
        if all(key):
            right_blocks[key].append(customer["record_id"])
    candidates = set()
    for customer in left_customers:
        key = (customer["postal_district"], customer["surname_key"][:2])
        if all(key):
            candidates.update((customer["record_id"], right_id)
                              for right_id in right_blocks[key])
    return candidates

assert postcode_candidates(
    [{"record_id": "ret-47", "postal_district": "N4", "surname_key": "mehta"}],
    [{"record_id": "sup-83", "postal_district": "N4", "surname_key": "mehra"}],
) == {("ret-47", "sup-83")}

Performance and operating cost

Building blocks is O(L + R) expected time and space for L left and R right records. Emitting pairs costs O(P) for P candidates, where a large block still produces a quadratic number of pairs in that block. Monitor P and maximum block size, not only input row counts.

Common Mistakes

  • Do not call a pair a nonmatch merely because the blocker never generated it.
  • Do not report recall from a test set containing only easy exact matches.
  • Do not put every missing-key record into one unbounded comparison block.

Read next

ai-data
data-science
Storage details