Blocking key design that protects recall without exploding the comparison count

The obvious blocking key for a trade show archive is the employer name. Buyers register with their company, the field is nearly always populated, and it partitions the file into blocks small enough to compare. Somebody builds it, the run finishes in minutes, and the portfolio person count comes out lower than anybody expected.

The key lost every buyer who changed jobs, which is the entire population the exercise was about. Blocking key design is where that kind of loss happens, silently, before any model has a chance to weigh evidence, and the discipline is to measure the loss instead of discovering it in a meeting six months later.

Two measures that decide every key argument

Papadakis, Skoutas, Thanos and Palpanas, in their survey of blocking and filtering techniques in ACM Computing Surveys in 2020, define the pair of measures the field uses. Pair completeness estimates the portion of the detectable duplicates in the block collection relative to those in the whole data set, which is recall at the blocking stage. Reduction ratio measures the reduction in the number of pairwise comparisons relative to the brute force approach, computed as one minus the comparisons kept over the comparisons possible.

Read alone, either measure is useless. A key that puts every record in one block has perfect pair completeness and a reduction ratio of zero. A key that puts every record in its own block has a reduction ratio of essentially one and pair completeness of zero. Every real key sits between those two failures, and key design is the argument about where.

Christen makes the same point in his 2012 survey of indexing techniques in IEEE Transactions on Knowledge and Data Engineering, where pairs completeness is defined as the true matched candidate pairs an indexing technique generates divided by the total number of true matched pairs, and corresponds to recall as information retrieval uses the term.

What makes a field a good key?

Four properties, and most fields on a registration record fail at least one.

• Coverage. A key can only work on rows that have the field. Mobile number is discriminating and often 30 to 40 per cent empty, which caps any pass built on it at the same proportion.
• Stability. The value has to survive whatever changes between the two records. Surname survives most things and fails at marriage. Employer fails at a job change. Postcode fails at an office move. Email domain fails at both.
• Error tolerance. The key is compared for exact equality, so any typing error in the part you key on removes the pair. Taking the first three characters of a surname is a deliberate choice to expose only the part people get right, since typing errors cluster at the end of a string.
• Cardinality. The field has to split the file into many blocks without splitting it into blocks of one. Country is nearly useless as a key in a domestic show, because 80 per cent of the file lands in one block. A full email address is nearly useless in the other direction, since it produces blocks of size one and finds only the pairs an equality join would have found anyway.

Composite keys exist to fix cardinality. Surname prefix alone gives blocks that are too large, email domain alone gives blocks dominated by webmail providers, and the two together give a distribution you can work with. Each component you add multiplies the number of blocks and divides their size, and it also multiplies the number of ways a true pair can fall out of the block.

Measuring both on 500 labelled pairs

Here is the exercise, on one show with five editions and 260,000 registration rows. Comparing everything would mean 260,000 times 259,999 over 2, which is 33.8 billion pairs.

Build a labelled set first. Five hundred pairs that you know to be the same person, assembled from any source you trust: pairs that agree exactly on email and mobile, pairs a steward has already merged by hand, pairs recovered from a badge reprint log. The set does not have to be a random sample of true pairs to be useful, though you should know how it was built, because a set assembled from email agreement will flatter any key containing email.

Now run three candidate keys over the file and count.

• Pass A, first three characters of surname plus email domain. Generates 21.4 million comparisons. Recovers 310 of the 500 labelled pairs, so pair completeness is 0.62. Reduction ratio is 1 minus 21.4 million over 33.8 billion, which is 0.9994.
• Pass B, last six digits of the mobile number. Generates 2.9 million comparisons. Recovers 205 pairs, so pair completeness is 0.41 on its own, which sounds poor until you see which pairs they are.
• Pass C, outward postcode plus the first four characters of the longest employer token. Generates 12.7 million comparisons. Recovers 275 pairs, pair completeness 0.55.

Take the union of the three candidate sets, removing pairs generated more than once, and you get about 34.6 million comparisons and 445 of the 500 labelled pairs. Pair completeness rises to 0.89 and the reduction ratio for the whole scheme is 0.9990.

Why does the union of three weak keys beat one strong key?

Because the passes fail on different people, and that is the property you are designing for.

Pass A fails for anyone who changed employer, since the email domain moves with the job. Pass B fails for the 30 to 40 per cent of rows with no mobile number, and for anyone who changed phone. Pass C fails for anyone who moved house or whose employer name was written two ways. A buyer who changed jobs but kept her phone is invisible to A, found by B. A buyer with no mobile who stayed at the same firm in the same city is invisible to B, found by C.

The arithmetic makes the point. Passes A and C between them recover 380 of the 500, since they overlap heavily on the buyers who stayed put. Pass B, the weakest of the three on its own at 0.41, adds 65 pairs that neither of the others found, which is what takes the scheme to 445. Those 65 are the pairs a single key scheme was never going to see, however carefully you tuned it.

This is also the argument against spending a week making one key cleverer. Adding phonetic coding to pass A might lift its individual pair completeness from 0.62 to 0.66. Adding pass B lifts the scheme from 0.62 to 0.75 for a tenth of the effort, because it fails on a different population rather than fixing a rare case of the same failure.

What is the marginal pass worth?

Price it. This is the part of blocking key design that turns an aesthetic argument into a decision anybody can sign.

Suppose you propose a fourth pass on the surname prefix alone, no second component. It generates 780 million comparisons, which is 23 times the whole existing scheme, and on the labelled set it recovers 22 pairs the other three missed, taking pair completeness from 0.89 to 0.934.

That is 780 million divided by 22, or about 35 million comparisons per additional true pair. Whether to run it depends on what those 22 pairs are worth and what your compute costs, and both of those are answerable. If the recovered pairs are ordinary repeat attendees, the pass is poor value. If they are the buyers who changed both employer and phone, which is the profile of somebody who moved to a new firm entirely, they may be exactly the population your exhibitor sales team is asking about.

My own rule is that a pass earns its place if it recovers pairs at under a million comparisons each, and anything above ten million needs a specific reason. Those thresholds are mine rather than anybody's finding, and the number that matters is the one you can defend to whoever pays for the compute.

Where this stops

Pair completeness measured on a labelled set inherits the bias of that set. If your 500 pairs were assembled from records that agree on email, every key containing email will look better than it is, and pass B will look worse. Build the labelled set from at least two sources with different failure modes, and say in the report how it was built.

The second limit is that a candidate pair count is not a run time. Two schemes generating 30 million pairs can differ by an order of magnitude in wall clock, because one of them puts its pairs in a few enormous blocks and the other spreads them evenly. Look at the block size distribution as well as the total, which is the arithmetic in blocking for entity resolution.

The third is that keys age. A key built on email domain degrades as your file accumulates people who have changed employer, so a scheme measured at 0.89 pair completeness in 2024 may sit at 0.84 in 2026 with nothing changed. Re measure every edition and keep the numbers next to the match rate they support in your unified data layer.

The first step is to build the labelled set, because everything above depends on it and nothing else does. Pull 500 pairs of registration rows that agree exactly on both email and mobile, treat them as true matches, and run your current blocking over them. The share that share at least one block is your pair completeness today, and if that number is below 0.9 you have a ceiling on your match rate that no scoring work will lift. Then look at whether a sliding window over sorted records would suit your exhibitor files better, in the sorted neighbourhood method.