Candidate pair generation and the recall you give away before scoring starts

The match rate came back at 71 per cent, the room accepted it, and an hour later somebody asked the question that mattered. How many true pairs did the scorer never see?

Nobody knew. Candidate pair generation had run before the scoring stage, quietly, in about four minutes, and had handed the model roughly two million pairs out of a possible sixteen billion. Everything discarded at that step was outside the measurement entirely. The 71 per cent was a share of what survived, and the survivors had already been chosen by a rule nobody had audited.

This is the most consequential stage in a matching pipeline and the one that gets the least attention, because it looks like a performance optimisation and behaves like a policy decision.

The comparison count nobody wants to pay

Take one show with five editions and 180,000 registration rows across them. Comparing every row with every other row is 180,000 times 179,999 divided by two, which is 16,199,910,000 pairs. Call it 16.2 billion.

A comparison that computes four field similarities and a weighted sum runs at perhaps 50,000 pairs a second on a single core. At that rate, 16.2 billion pairs is 324,000 seconds, near enough 90 hours. Add a second show and the count grows with the square of the file, so doubling to 360,000 rows takes you to 64.8 billion pairs and about 15 days.

That is why every production pipeline compares a subset. The subset is the product of candidate pair generation, and it is usually built from a blocking key: the first three characters of the surname joined to the lowercased email domain, or the postcode district joined to the first initial. Suppose that key leaves 2.4 million candidate pairs. You have cut the work by a factor of about 6,750, and the scoring stage now runs in under a minute.

The saving is real. The question is what it cost, and the cost is not measured in seconds.

Why is candidate generation a recall ceiling and not a speed setting?

Because a pair that shares no key is never compared, so no score exists for it, so no threshold can reach it.

Work an example. Assemble 1,200 pairs you know to be true matches, from a period where you have a reliable answer: same person, confirmed by a badge collection record or by a steward who checked. Run your current candidate generation over the file and count how many of those 1,200 pairs appear in the candidate set. Say 1,152 do, and 48 do not, because the surname was mistyped in one record or the person registered once with a personal mailbox and once through a corporate domain.

Your ceiling is 1,152 divided by 1,200, which is 0.96. The scoring stage now gets to work on a set from which 4 per cent of the answer has already been removed. If the scorer then recovers 92 per cent of the true pairs it can see, your end to end recall is 0.96 times 0.92, which is 0.8832, so about 88 per cent.

Two of those numbers respond to tuning and one does not. Moving the merge threshold down lifts the 92 and costs you precision, which is the trade every team knows how to argue about. Nothing you do at the threshold moves the 96. The literature calls this quantity pair completeness, and Christen surveyed the indexing methods that produce it in IEEE Transactions on Knowledge and Data Engineering in 2012, with the recall each one gives up as the axis of comparison.

The practical consequence is an ordering rule. Measure the ceiling before you spend a fortnight on the scorer, because a scorer tuned against a candidate set that has already lost the interesting pairs is being optimised against the easy half of your file.

What does canopy clustering actually buy you?

An ordinary blocking key is a hard partition per pass. A record belongs to one group, the group is determined by exact agreement on the key, and a single mistyped character in the key sends the record somewhere else permanently.

McCallum, Nigam and Ungar proposed a different shape at the ACM SIGKDD conference in 2000, working on bibliographic reference matching. Use a cheap approximate distance measure, one you can compute in bulk, and two thresholds. Pick a record at random, put every record within the loose distance of it into a canopy, then remove from the pool only those records within the tight distance, and repeat until the pool is empty. Records can sit in several canopies at once, and the exact expensive comparison runs only between records sharing a canopy.

The loose threshold is the recall dial. Set it generously and borderline pairs stay alive at a cost you can count.

Continue the example. Use shared character trigrams on the surname as the cheap measure: one shared trigram puts a record in the canopy, four or more removes it from the pool. Suppose that produces 4,200 canopies averaging 120 records each. Within-canopy pairs are 120 times 119 divided by two, which is 7,140 per canopy, so 4,200 times 7,140 is 29,988,000 pairs. Round it to 30 million.

Now compare the three options honestly. Everything is 16.2 billion pairs and 90 hours. The tight blocking key is 2.4 million pairs and under a minute. The canopy set is 30 million pairs and about ten minutes at the same rate. Re-run the 1,200 labelled pairs and suppose 1,188 now survive, so the ceiling moves from 0.96 to 0.99.

Ten minutes of compute for three points of unreachable recall is a trade most organisers would take without discussion, and it is invisible unless somebody measures the ceiling separately from the score.

Deciding what the cheap measure should be

The cheap measure has one job, which is to be correlated with the expensive one and to run in bulk. It does not have to be good.

For attendee records, character trigrams on the surname work because typing errors and transliteration differences preserve most trigrams. For company names, an inverted index on the rarest token is stronger, since two records sharing the token Skanska are far more likely to be the same firm than two records sharing the token group. Rarity does the work, and you can compute token frequencies from your own exhibitor directory in a single pass.

The measure to avoid is the one built from a field your registration form does not enforce. Blocking on postcode looks precise until you discover that 22 per cent of your self-service registrations have a blank postcode, at which point those rows either form one enormous canopy or vanish from candidate generation altogether. Both outcomes are bad and only one of them is visible.

Whatever measure you pick, compute it on normalised values and never on raw ones. A canopy built from raw surnames puts MULLER, Muller and Müller in three different places, so the stage designed to protect recall has spent its budget separating three spellings of one person. Normalisation belongs upstream of candidate generation for the same reason blocking belongs upstream of scoring: each stage can only lose what the one before it handed over.

Choosing what to compare inside the canopy is a separate decision with its own reasoning, and one measure per field beats one measure everywhere, which is J16's argument. The measure most people reach for on names is the prefix weighted comparator covered in J12.

Where this stops

The ceiling estimate is biased upwards, and the bias comes from where the labelled pairs came from.

You found those 1,200 true pairs somehow. If they came out of your current system's review queue, they are pairs the current candidate generation already produced, and measuring that candidate generation against them will tell you it loses nothing. The measurement has been contaminated by the thing it is measuring. This is the single most common error in matching evaluation and it is easy to commit by accident.

The fix is uncomfortable and cheap. Draw a random sample of pairs from outside the candidate set, review them by hand, and count how many are true matches. If you draw 400 non-candidate pairs and find three true matches, you cannot use that as a rate directly, because the non-candidate population is enormous and the estimate is unstable at that sample size. What you can do is treat any hit at all as evidence that the ceiling sits below where you thought, and look at what those three pairs have in common. Usually it is one thing: a missing field, a transliterated surname, a company that books through an agency.

The second limit is that a loose canopy raises the ceiling and also raises the number of near misses arriving at the review queue, because the pairs it rescues are the marginal ones by construction. A queue that was 900 pairs a week becomes 2,300, and if nobody has the hours, the extra recall is theoretical. Size the loose threshold against review capacity, not against the ceiling you would like to report.

Start by computing two numbers on one show's file this week. Count the rows, work out n times n minus one over two, and count the candidate pairs your current process actually produces. The ratio is your reduction factor. Then take 100 pairs from outside the candidate set, read them, and count the true matches. If there are more than one or two, your ceiling is the thing to fix before anything else in the unified data pipeline, and the pairwise scoring model described in cross event attendee matching is not where your recall is going.