The sorted neighbourhood method for matching exhibitor contact lists year to year

The exhibitor list for the 2026 edition holds 22,000 contacts and last year's holds 28,000. Sales want to know which of last year's named contacts are back, which have been replaced by somebody new at the same firm, and which firms have vanished. The company names do not match, because half of them carry a legal suffix in one file and not the other, and the contact names do not match either, because people move.

The sorted neighbourhood method suits this job better than key based blocking, and the reason is structural. Exhibitor records cluster around a company name that is written several ways rather than mistyped, so the variants sort next to each other even when no exact key value is shared. Acme Packaging, Acme Packaging Ltd and Acme Packaging Limited land in adjacent rows under any sensible sort, and a window that reaches ten rows will compare all three. A key requiring exact equality on the company field puts them in three separate blocks.

Hernandez and Stolfo set the method out at SIGMOD in 1995, in the paper that named the merge and purge problem, and the shape of it has not changed since.

The three phases, and the comparison count

The method has three phases and each is a single step.

Create a key. Concatenate the parts of the record you want to sort on, in order of how much you trust them: the first four consonants of the normalised company name, then the first three characters of the contact surname, then the outward postcode. Trust order matters more than field choice here, because the leftmost component decides the neighbourhood and everything after it only breaks ties. Consonants come first because vowels absorb most of the variation between Acme and Akme, and because dropping them shortens the field without losing its shape. Sort the file on that key. Then slide a window of fixed size down the sorted list and compare every record with the records still inside the window.

Now the arithmetic, on the combined file of 50,000 contacts. Comparing every pair means 50,000 times 49,999 over 2, which is 1,249,975,000 pairs. With a window of 10, each record is compared with the 9 records ahead of it, so the count is 50,000 minus 10, times 9, plus 10 times 9 over 2, which is 449,910 plus 45, or 449,955 comparisons.

That is a reduction ratio of 0.99964, and it runs in seconds on a laptop. The sort is the expensive part, at N log N, and it is still trivial at this size.

How big should the window be?

The window is the one parameter, and doubling it does two things you can measure.

At a window of 10 you get 449,955 comparisons. At 20 you get 50,000 minus 20, times 19, plus 190, which is 949,810, a little over twice as many. Comparisons scale roughly linearly with the window, which is the appeal of the method against the quadratic behaviour of an oversized block.

Recall does not scale linearly. Widening the window helps only for pairs that were already close in the sort order and just outside reach, and most pairs that miss are not near misses. They are records whose sort key differs at the front, which the window cannot fix at any size short of the whole file. In Christen's experimental survey of indexing techniques in IEEE Transactions on Knowledge and Data Engineering in 2012, the non adaptive sorted neighbourhood variants were run at window sizes of 2, 3, 5, 7 and 10, which is the range worth exploring before you conclude the method is failing.

My own starting point for exhibitor data is a window of 10, on the reasoning that a firm rarely appears under more than a handful of name variants and its contacts rarely number more than a few. For attendee data, where thousands of people share a surname prefix, a window is the wrong tool and a key based approach with capped block sizes is better, which is the arithmetic in blocking for entity resolution.

Why does one pass never work?

Because sorting is dominated by the leftmost characters of the key, and an error there is unrecoverable.

Two records for the same firm, one keyed from The Acme Packaging Company and one from Acme Packaging Ltd, sort under T and under A. They will be thousands of rows apart, and no window you can afford will bring them together. The same happens when a contact surname is captured in the company field, and again when a firm rebrands between editions.

Hernandez and Stolfo's answer was multiple passes. Run the method several times with different sort keys, each putting a different part of the record at the front, then take the transitive closure of all the links found, so a pair linked in any pass is linked overall, and a chain of links joins records that no single pass connected directly.

Three passes over the exhibitor file might sort on company consonants first, then on contact surname plus forename initial, then on email domain plus postcode. Three passes at a window of 10 cost 1,349,865 comparisons in total, which is still a thousandth of the brute force count, and each pass fails on a different population. The stripped accent that ruins pass one is irrelevant to pass two.

Transitive closure has a cost worth knowing before you switch it on. If pass one links A to B and pass two links B to C wrongly, the closure puts A, B and C in one cluster, and a single bad link contaminates everything it touches. Keep the closure a separate, reversible step, and record which pass produced each link so a bad pass can be removed without rebuilding.

Matching this year's list to last year's

The version most useful to a sales team is a link between two files rather than a deduplication of one, and the method handles it with one addition.

Concatenate both years into a single file of 50,000 rows, tagging each row with its edition. Sort and slide the window as normal, then discard any candidate pair whose two rows carry the same tag, since a 2026 row matching another 2026 row is a duplicate within an edition and a different question. What survives is a set of cross year candidate pairs, scored on company name similarity, contact surname, email domain and job title.

Work the counts through and the value of the exercise becomes obvious. Of the 22,000 contacts on the 2026 list, suppose 9,400 link to a 2025 row with the same person at the same firm and another 4,100 link to a 2025 row at the same firm under a different name. That leaves 8,500 contacts with no 2025 link at all, and on the other side 14,500 of last year's 28,000 rows with no 2026 link. Those two residuals are where the argument happens, because a single unmatched pair can appear in both.

The output has three groups, and each goes to a different person. Firms with the same named contact returning are a renewal conversation. Firms returning with a different contact are a handover conversation, and they are the group most often missed entirely, because the CRM shows the old contact as inactive and nobody joins the two rows. Firms present in 2025 and absent from 2026 are a lapsed account list, and its accuracy depends entirely on the matching, since a firm that merely changed its registered name will appear as both a lapse and a new logo.

That last failure is worth a number. If 6 per cent of your exhibitor base changes how its name is written between editions, and your matcher works on exact company names, you will report a churn figure roughly 6 points too high and a new business figure roughly 6 points too high at the same time, and the two errors will hide each other in the totals.

Where this stops

The method depends on a sort key that puts genuine pairs close together, which means it depends on the first few characters being right. For records where the informative token sits in the middle of the field, no ordering rescues you, and a token based key that puts a record into one block per meaningful word will do better. Choosing between the two, and pricing the choice, is the subject of blocking key design.

The second limit is that a window is a fixed budget applied to an uneven file. A stretch of the sorted list holding 400 rows for the same large firm exhausts a window of 10 immediately, so genuine pairs 40 rows apart inside that stretch are never compared, while a stretch of unrelated singletons wastes its comparisons entirely. Adaptive variants that vary the window by local similarity exist for exactly this, and they add a parameter you will have to explain.

The first step fits in an afternoon. Take your last two exhibitor directories, build one sort key from the first four consonants of the company name, sort the combined file, and read 200 consecutive rows in the middle. You will see the variant spellings sitting next to each other, and you will see how far apart the worst case is, which tells you the window size your data actually needs before you commit any of it to the unified data layer.