Blocking Strategies for Large-Scale Address Matching

TL;DR: Pairwise comparison is quadratic and therefore impossible at scale; blocking makes it linear-ish by only comparing records that share a cheap exact key. Pick the key from what you can trust, cap the largest blocks, run a second pass on a different key to recover the pairs the first one missed, and measure recall against a labelled sample. The matching itself is covered in deduplicating addresses by fuzzy canonical key.

The Quadratic Wall

Comparing every record against every other is fine at a thousand rows and impossible at a million. The arithmetic is unforgiving and worth internalising before choosing a strategy.

Pairs to compare, with and without blocking A table of dataset sizes against the number of pairs. Ten thousand records produce fifty million unblocked pairs. One hundred thousand produce five billion. One million produce five hundred billion. With blocking on postcode and street initial, the same datasets produce forty thousand, four hundred thousand and four million pairs. Records Unblocked pairs Blocked pairs 10 000 50 000 000 ~40 000 100 000 5 000 000 000 ~400 000 1 000 000 500 000 000 000 ~4 000 000 Blocking turns an impossible problem into a routine one — at the cost of never comparing pairs in different blocks.

That cost is the whole design tension. Every pair in different blocks is a pair you have decided not to look at, so the blocking key must be an attribute that true duplicates almost always agree on — which rules out the fields most likely to contain the typo you are trying to detect.

Choosing the Key

Key Blocks Misses Best for
postcode + street initial small and even postcode typos, boundary reassignments the general default
geohash 6–7 small, density-dependent records without coordinates post-geocoding dedup
postcode alone huge in dense cities postcode typos small datasets only
street name soundex moderate different street spellings entirely name-heavy corpora
first N of the canonical key tunable any difference in the leading tokens quick prototypes

The second row is the strongest option once coordinates exist, because location survives the errors that text does not: a record whose postcode was mistyped still geocodes close to its twin, and a geohash block will bring them together where a postcode block never would.

Capping the Pathological Block

Real data always contains one or two enormous blocks — a default postcode used by a misconfigured form, a warehouse address entered on tens of thousands of orders — and they dominate the run.

from __future__ import annotations

from collections import defaultdict


def build_blocks(
    keys: list[tuple[str, str]],          # (record_id, blocking_key)
    max_block: int = 400,
) -> tuple[dict[str, list[str]], list[str]]:
    """Group records by key, returning blocks plus the overflow to review."""
    grouped: dict[str, list[str]] = defaultdict(list)
    for record_id, key in keys:
        grouped[key].append(record_id)

    blocks: dict[str, list[str]] = {}
    overflow: list[str] = []
    for key, members in grouped.items():
        if len(members) > max_block:
            overflow.extend(members)      # do not compare; flag for review
        else:
            blocks[key] = members
    return blocks, overflow

Routing the overflow to review rather than comparing it is the pragmatic choice. A block of twenty thousand records is eighty million pairs on its own — more than the rest of the file combined — and the records in it are almost always a data-quality problem rather than a genuine cluster of duplicates.

Multi-Pass Blocking Recovers the Misses

Two passes, two keys, one recovered pair Two records are true duplicates but their postcodes differ by a typo, so the first pass on postcode places them in separate blocks and never compares them. A second pass blocking on geohash places them in the same block, and the pair is compared and matched. The union of both passes is what the scorer receives. pass 1 · postcode + street initial 78701-M record A 78710-M record B — typo never compared pass 2 · geohash 7 9v6m2yq record A and record B — same block compared, matched, recovered

Two passes on independent keys recover most of what either misses alone, and the cost is additive rather than multiplicative — two linear passes, not a quadratic one. Deduplicate the candidate pairs before scoring, since a pair found by both passes should only be scored once.

Measuring Recall

Blocking recall — the share of true duplicate pairs that end up in at least one shared block — is the number that says whether a scheme is working, and it cannot be inferred from the match rate. A scheme with poor recall produces confident, correct matches on the pairs it does compare, and quietly never sees the rest.

Measure it against a labelled sample: take a few hundred known duplicate pairs, apply the blocking scheme, and count how many pairs share a block. Anything above ninety-five percent is usually acceptable; below eighty means the key is wrong for this corpus rather than merely imperfect.

The measurement also tells you whether a second pass is worth its cost. If pass one already achieves ninety-eight percent recall, adding a geohash pass doubles the comparison work to recover two percent of pairs — which may still be right for a high-stakes merge and is clearly wrong for a routine nightly job.

Block-Size Distribution Is the Diagnostic

What a healthy block-size distribution looks like A distribution of block sizes. Most blocks contain fewer than fifty records. A small number contain several hundred. Two blocks contain tens of thousands and are marked as pathological, accounting for more comparisons than the rest of the file combined. cap here — overflow to review small blocks pathological blocks Plot this once before tuning anything — the two bars on the right usually explain the entire runtime.

Edge Cases and Failure Modes

Blocking on a field the fuzzy matcher is meant to fix. Blocking on street name and then fuzzy-matching street names compares only records that already agree, which defeats the purpose entirely.

Blocks of size one. A record alone in its block is never compared to anything and is silently unique. That is usually correct and worth counting — a rising share of singleton blocks means the key is becoming too specific.

Nulls in the blocking key. Records missing a postcode all share the empty key and form one enormous block. Route them to a separate pass keyed on something they do have, rather than letting them collapse together.

Non-transitive matches across passes. Pass one links A to B, pass two links B to C, and A and C were never compared. Resolve clusters with a union-find over all matched pairs rather than treating each pair independently.

Blocking on Dirty Data

Every blocking key assumes the attribute it uses is populated and roughly correct, and real files test that assumption immediately.

Missing values are the first problem. Records without a postcode all share the empty key, which is both an enormous block and a meaningless one. Route them to a separate pass keyed on something they do have — a street-name soundex, or a geohash if coordinates exist — rather than allowing them to collapse together or dropping them silently.

Systematic errors are the second. A partner feed that pads every postcode to six characters, or one that submits a warehouse postcode as a default, produces blocks that are internally consistent and unrelated to reality. Those are visible in the block-size distribution before they are visible anywhere else, which is another argument for plotting it.

The third is the interaction with normalisation. If the blocking key is derived from the canonical form, a change to normalisation changes the blocking too, and a deduplication run before and after the change is not comparable. Version the blocking key alongside the canonical key and record which version a run used, exactly as the cache does.

Taken together these argue for treating the blocking key as a first-class derived column that is written at ingestion, indexed, and versioned — rather than as an expression computed inline at the start of each deduplication run.

Integration Note

Blocking sits directly in front of the scoring step described in fuzzy address matching with rapidfuzz in Python, and the two are tuned together: a looser block produces more candidate pairs and lets the threshold be stricter, while a tighter block relies on the scorer catching less. The geohash key comes from geohash encoding for address proximity search, which is the same encoder the reverse-geocoding cache uses — one implementation, three consumers.

Treating it that way also means the blocking key can be indexed, which turns the grouping step from a full scan into an index scan and removes what is otherwise the second-largest cost in a deduplication run after the scoring itself.

Blocking Is Not Free at Write Time

One consequence of treating the blocking key as a stored column deserves stating: it has to be written, indexed and maintained, and that cost lands on the ingestion path rather than on the deduplication run.

In practice the cost is small — one derived string per record and one index — and it is almost always worth paying, because the alternative is recomputing the key for every record on every run. On a table of tens of millions of rows that recomputation is minutes of CPU that buys nothing, repeated nightly.

The exception is a pipeline that deduplicates rarely, perhaps quarterly, against a table that is written constantly. There the index maintenance runs continuously and the benefit is collected four times a year, and computing the key on demand into a temporary table is the better trade. As with most of these decisions, the deciding factor is the ratio between how often the data is written and how often it is matched.