Blocking for entity resolution before the pair count runs to billions

Take the registration archive for a portfolio: nine shows, five years, 420,000 rows after the obvious duplicates within each edition have gone. Somebody asks for a portfolio wide person count, and the naive way to get one is to compare every row with every other row.

That is 420,000 times 419,999 divided by 2, which is 88.2 billion pairs. At a hundred thousand comparisons a second, a rate a well written matcher on a single machine can hold, the run takes about 10 days. Blocking for entity resolution is the step that makes the same question answerable before lunch, and it is the step where you quietly decide which true pairs you are never going to find.

The idea is old. Winkler's 2006 overview for the US Census Bureau credits Newcombe with showing, in 1962, how to cut the number of pairs considered by only comparing records that agree on some characteristic such as surname or date of birth. The name for that reduction is blocking, and everything since has been variations on which characteristic to use.

What one blocking key does to that number

Take a key made of two parts: the first three characters of the normalised surname, plus the email domain. Two rows are compared only if both parts match.

Run it over the 420,000 rows and you get a block distribution that looks roughly like this, and the shape is what matters.

• 92,000 blocks holding about 3 rows each, which is 276,000 rows.
• 3,800 blocks holding about 20 rows each, which is 76,000 rows.
• 190 blocks holding about 200 rows each, which is 38,000 rows.
• 10 blocks holding about 3,000 rows each, which is 30,000 rows.

Comparisons inside a block of size b are b times b minus 1, over 2. So the small blocks contribute 3 comparisons each, or 276,000 in total. The 20 row blocks contribute 190 each, or 722,000. The 200 row blocks contribute 19,900 each, or 3.78 million. The 3,000 row blocks contribute 4,498,500 each, or 44.99 million.

Add them: about 49.8 million comparisons, down from 88.2 billion. The reduction ratio, one minus the pairs kept over the pairs possible, is 0.9994. The run that took 10 days now takes about 8 minutes.

Why do ten blocks produce ninety per cent of the work?

Look again at where the 49.8 million came from. The ten largest blocks contributed 44.99 million of it, which is 90.4 per cent. Ninety two thousand blocks contributed half of one per cent.

That is the quadratic term doing what quadratic terms do. Doubling a block's size roughly quadruples its comparisons, so a single 3,000 row block costs 4.5 million comparisons, sixteen times what the 276,000 rows sitting in blocks of 3 cost between them. In a registration file those big blocks are entirely predictable: common surname prefixes combined with consumer email domains, which is to say every Smith, Jones or Nguyen on a webmail address, all sitting in one bucket.

Two consequences follow. First, your run time is a property of your largest blocks and not of your file size, which is why capping block size is the most effective single optimisation available. Second, those oversized blocks are also the worst blocks for accuracy, because a bucket containing 3,000 unrelated people generates a huge number of high scoring coincidences. Cap them at a few hundred rows by adding a third component to the key, and both problems shrink together.

What to do about the ten big blocks

Splitting them is usually better than dropping them, and the arithmetic says by how much.

Add a third component to the key for oversized blocks only: the first character of the normalised forename. Each 3,000 row block becomes roughly ten sub blocks of 300. Comparisons inside one sub block fall to 300 times 299 over 2, which is 44,850, and ten of those is 448,500 per original block instead of 4,498,500. Across the ten big blocks the cost drops from 44.99 million to 4.49 million, and the run total falls from 49.8 million to about 9.3 million comparisons, roughly 93 seconds.

The cost is recall, and it is specific rather than general. You have just decided that two records whose forenames start with different letters are not worth comparing, inside those blocks only. That loses Bob against Robert, Kathryn against Cathryn, and anyone whose first initial was captured differently by two systems. Whether that trade is acceptable depends on how many of your true pairs live inside the big blocks, which you can measure directly.

The alternative that people reach for first is to drop the oversized blocks entirely, on the grounds that a bucket of 3,000 strangers cannot contain much signal. It does contain signal, and dropping the block discards it along with the noise. Splitting keeps the pairs that agree on more evidence and discards the ones that agree on less, which is the trade you actually want.

What blocking costs you in recall

Every pair you do not generate is a pair you have decided is a non match, silently, before any evidence was weighed. The measure for that loss is pairs completeness: the number of true matching pairs the blocking step generates, divided by the total number of true matching pairs in the file. Christen defines it exactly that way in his survey of indexing techniques in IEEE Transactions on Knowledge and Data Engineering in 2012, and notes that it corresponds to recall as the term is used in information retrieval.

Our key loses two populations by construction. Anyone whose surname changed loses the first component. Anyone who switched from a work address to webmail loses the second. Those are not rare cases in a five year archive, and they are correlated with exactly the people a portfolio count is about, since changing employer is the main reason a buyer appears under two identities.

So measure it rather than assuming it. Take 500 pairs you know to be true matches, run them through the blocking step alone, and count how many end up sharing at least one block. If 430 do, pairs completeness is 0.86, and the 14 per cent you lost is a ceiling on everything downstream. No scoring model recovers a pair it never sees, which is why key design gets its own treatment in blocking key design.

Which indexing method should you pick?

Christen's 2012 survey covers twelve variations of six indexing techniques, analyses their complexity, and evaluates them experimentally on synthetic and real data. The six are traditional blocking, sorted neighbourhood, q gram based indexing, suffix array based indexing, canopy clustering and a string map method, and the paper's honest conclusion is that the ranking depends on the data and the parameters as much as on the technique.

For registration and exhibitor data I would start with traditional blocking on several passes, and I would only reach for anything more elaborate when a measured pairs completeness says I need to. The reasons are practical. Traditional blocking runs as a group by in whatever database you already have. Its block sizes are inspectable, so when the run takes an hour you can see which key value caused it. And the failure mode is legible: a missed pair can be traced to a key that disagreed, which somebody can then fix with a normalisation rule.

The q gram and suffix array methods buy tolerance to typing errors inside the key itself, at the cost of much larger candidate sets and parameters that nobody on the team will be able to explain in six months. The sliding window alternative, which sorts records rather than bucketing them, has a different set of trade offs and is covered in the sorted neighbourhood method.

Where this stops

Blocking assumes there is some cheap function of a record that true pairs agree on. When there genuinely is not, blocking cannot help you, and two situations in event data produce that.

The first is the sparse row. A registration with a surname, a webmail address and nothing else has almost no key material, and whatever key you build for it will be either uselessly broad or unshared. Those rows will show a lower match rate than the rest of the file, and the difference is a property of your registration form rather than of the people.

The second is company matching. Exhibitor records key badly on any prefix, because the same firm appears as Acme, Acme Group, and The Acme Corporation, and the informative token is not always the first one. A prefix key on that field puts the three variants into two different blocks and calls the job done. Token based blocking, where a record joins one block per meaningful token in its name, handles that better than any prefix rule, at the cost of putting every record into several blocks at once.

The first step is a histogram, and it takes one query. Group your registration archive by whatever key your current matcher uses, count rows per key value, and sort descending. Look at the top twenty. If any of them holds more than a few hundred rows, that key is where your run time and your false merges are both coming from, and capping it is the cheapest improvement available to your unified data layer. The wider argument for why any of this is worth doing sits in cross event attendee matching.