Blocking, before anything gets compared

A Fellegi-Sunter weight, or any of session 2's seven string measures, is cheap to compute once. It is not cheap to compute 1,953 times, and 1,953 is Meridian at 63 records. The moment a real customer table crosses somewhere between a hundred thousand and a million records per side, all-pairs comparison stops being slow and starts being infeasible on any budget - that is the arithmetic from session 1, and it does not go away just because your scoring got better.

Blocking is the answer to a specific question: can you decide, cheaply, that most pairs are obviously not worth the expensive comparison at all? The four schemes tonight are four different cheap questions to ask first.

Restating session 1's arithmetic in one place, because it is the entire reason this session exists: all-pairs comparison is O(N × M) for two tables of size N and M, or O(N²) when comparing a table against itself. That stops being comfortable well before most people expect.

Somewhere between the 100,000 and 1,000,000 row, all-pairs comparison becomes infeasible on any realistic compute budget, however cheap each individual comparison is. Meridian sits at the top of this table on purpose - it is small enough to compare exhaustively in class, which makes it a good teaching set and a slightly misleading one about what production actually requires.

Every scheme below reduces the same underlying question to one sentence: group records by something cheap to compute, and only compare records inside the same group. The cheap thing might be an exact field, a sorted position, an approximate distance, or a hashed shingle set. What they share is the trade they make: anything that groups two true-match records apart is a pair lost before Fellegi-Sunter, session 2's string measures, or anything else ever sees it.

This is why blocking is discussed as its own pipeline stage rather than folded into scoring. Scoring can be re-run with a different threshold at any time, cheaply, because the comparison already happened. Blocking cannot be re-run after the fact without redoing the expensive part it exists to avoid - which is the same irreversibility session 1 flagged for the pipeline as a whole, now landing on a specific stage.

Standard blocking picks a field, or a derived key, and only compares records that share it exactly - postcode, a truncated surname, a birth year. It is the oldest and simplest approach in production use, so widespread it is field practice rather than a single citable paper. Its failure mode is the flip side of its simplicity: any pair where the key genuinely differs is invisible to it, no matter how similar every other field is.

Sorted neighbourhood (Hernandez and Stolfo, SIGMOD 1995) sorts all records by a chosen key, slides a fixed-size window across the sorted list, and compares every pair that falls inside the same window together. It recovers some of standard blocking's blind spot, because two records with a slightly different key can still land near each other in sort order and end up in the same window. It trades that for more candidate pairs per true pair recovered, which shows up directly in the measured numbers below.

Canopy clustering (McCallum, Nigam and Ungar, KDD 2000, pages 169-178) runs a cheap approximate distance measure over the whole dataset first, forming loose, deliberately overlapping groups called canopies. The expensive, accurate distance measure - session 2's string measures, or Fellegi-Sunter's weight - then only runs on pairs that share a canopy. Because canopies overlap on purpose, a record can sit in more than one, which is exactly what protects it from being blocked out by a single bad key. The original paper reported more than a 10x speedup and about a 25 percent reduction in error on bibliographic matching, and this citation is primary-verified.

LSH and MinHash (Broder, "On the Resemblance and Containment of Documents", SEQUENCES 1997) take a different cheap distance entirely: break each string into overlapping character shingles, compute a small set of minimum hash values over those shingles, and use those minhash values to estimate Jaccard resemblance without ever comparing the full strings. Records whose hashes collide into the same bucket become a candidate pair. It scales to enormous text collections precisely because the expensive comparison never has to run on most of the data.

These come from Christen, "Quality and Complexity Measures for Data Linkage and Deduplication", and the citation is primary-verified.

• Pair completeness (PC) - the recall analogue for blocking. The share of true pairs that survive into the candidate set. If a blocker keeps 91 percent of true pairs, the other 9 percent are gone before scoring even starts.
• Reduction ratio (RR) - one minus the candidate pairs divided by all possible pairs. It measures how much work the blocker saved, independent of whether the work it saved was worth saving.
• Pairs quality (PQ) - the precision analogue for blocking. The share of surviving candidate pairs that are actually true matches. A low PQ means the expensive scoring stage still has to wade through a lot of pairs that were never going to match.

The trade-off is direct: push RR higher by shrinking the candidate set further, and PC usually falls, because a tighter key or a narrower window is more likely to split a true pair apart. The rule that follows is not a preference, it is a consequence of session 1's irreversibility argument applied to this exact stage: prioritise pair completeness. A pair discarded at blocking can never be recovered downstream, however good the scorer is. A false candidate that survives blocking is merely inefficient - the scorer filters it out later, at a cost in compute, not in truth.

These four schemes were run against Meridian's actual 1,953 possible pairs, and the numbers below are measured, not estimated.

The plain point first: every scheme costs 9 percent of the true pairs, permanently. None of the three real schemes reaches the 100 percent completeness that "no blocking at all" has by definition, because none of them is lossless - that was true before Meridian was measured and the measurement confirms it. Blocking is a genuine trade, not a free optimisation, and pretending otherwise is how a matcher quietly loses matches nobody notices until someone asks why a known customer pair never got compared.

Among the three real schemes, postcode is the best trade here: it reaches the same 91 percent completeness and 98 percent reduction as Soundex of surname, but at 78 percent pairs quality against Soundex's 73 percent, meaning fewer of its candidate pairs are wasted on non-matches. Sorted neighbourhood is the clearest illustration of reduction ratio without pairs quality: it does far more comparisons for the same 91 percent completeness - 242 candidate pairs against postcode's 41 - and its pairs quality collapses to 13 percent as a direct result. More candidates is not automatically safer if most of them were never going to match.