Blocking keys and sorted neighbourhood
- Lesson 9
- 40 min
- Module 3: Blocking: do not compare everything
Where we are
We cannot compare every pair, so we must choose candidate pairs. The simplest way is a shared key. In this lesson, we block on keys such as the postcode or the start of the surname, combine keys, and slide a window over sorted records.
Lesson 9 of 29 · Entity Resolution and Record Matching: Is This the Same Thing?Blocking keys and sorted neighbourhood
1. The matching problem
2. Clean first, then match exactly
3. Blocking: do not compare everything
4. Compare records: similarity measures
5. Probabilistic linkage
6. Learned matching: classifiers, embeddings and language models
7. From pairs to entities
8. Run matching in production
What you will be able to do
Make candidate pairs with blocking keys. Build keys from several fields, measure each one, and combine them so that one key catches what another misses. Then try a second method that needs no exact key: a sliding window over sorted names.
NotebookBuild and measure keys in a notebook
The notebook builds the five keys of the project with pandas. You measure each key, combine them, and write a sorted-neighbourhood blocking yourself. Its setup cells download the data, so it needs no local setup.
Colab and Kaggle open your own copy. They need a free Google or Kaggle account. Stuck? See the solution notebook.
Before you startWhat to know and to have ready
What you need to know
- Candidate pairs, blocking keys, pair completeness and reduction ratio, from Why all pairs is impossible.
- The clean name, email, phone, postcode and date of birth of each record, from Normalise and Parse into parts.
What you need on your computer
- The project
larkfield-matchwith the command of the last lesson. Or use the notebook only.
Tested on macOS with Python 3.12.13. The Windows (PowerShell) commands are not tested.
Two ways to find a book
Section titled “Two ways to find a book”A library has a card catalogue. Each book has a card in the author drawers, sorted by the author’s surname. It has a second card in the title drawers.
Why two? A reader may remember the author but not the title. Another reader remembers the title but writes the author’s name wrong. With one set of drawers, the second reader finds nothing. With two, either memory is enough.
Blocking keys work in the same way. One key is one set of drawers. Two records of one customer must share one key to meet. They do not need to share all of them.
The problem: one key always misses someone
Section titled “The problem: one key always misses someone”The last lesson blocked on the postcode. It lost 4,289 true pairs: 15.5% of all true pairs. Who are they? Every one of them is a pair whose two records have different postcodes. Most are customers who moved: one record has the old postcode and one has the new one. In our synthetic data, about 28% of people moved.
Try another single key instead. Each key loses a different group of customers:
- One key
- Several keys together
Text description of the chart
A dot chart with seven rows, one dot per blocking, on an axis from 0 to 1. One key: postcode 0.845, surname 0.849, phone 0.494, email 0.451, date of birth (with the first letter of the first name) 0.235. Several keys: postcode or surname 0.976; the five keys together 0.994.
- The email keeps only 0.451. The garden centres leave the email empty in most records, and some customers use a family email in one list and their own in another.
- The phone keeps 0.494. The shop leaves the phone empty in 30% of records.
- The date of birth keeps 0.235. Most garden-centre and shop records have no date of birth.
- The surname key keeps 0.849. It loses customers with a typing error in the first letters of a name, or a nickname in place of the first name.
No single key is good enough. But look at the last two rows: keys together keep far more.
Build a key
Section titled “Build a key”A key is a short text made from the clean values of a record. It must be the same for two records of one customer, and different for most other records.
The postcode is a key as it is. The surname key needs more work. The project makes it from two parts:
surname key = the first 4 letters of the surname + “|” + the first 2 letters of the first name
For Samuel Green, that is gree|sa. For Jacques Beaulieu, beau|ja. The | only separates the parts.
Narrow keys and wide keys
Section titled “Narrow keys and wide keys”Why 4 letters, and why add the first name? Because of the size of the blocks. A block of k records makes k × (k − 1) / 2 pairs. One big block can make more pairs than all the small blocks together.
We counted the pairs that each key would make on TermLarkfieldA made-up Canadian online shop for home and garden products. It is not a real company. All Nextia courses use its help desk and data as the example.Learn more Meet Larkfield’s records. We counted them from the block sizes; we did not build them:
| Key | Different values | Largest block | Pairs |
|---|---|---|---|
| The source list (shop, loyalty, garden) | 3 | 31,128 | 700,893,447 |
| The first letter of the surname | 23 | 5,780 | 120,104,444 |
| The first 4 letters of the surname | 1,027 | 2,381 | 24,624,225 |
| 4 letters of the surname + 2 of the first name | 7,499 | 316 | 1,035,498 |
| The postcode | 22,727 | 16 | 89,630 |
A wide key has few values and big blocks. It keeps many true pairs, but it makes too many candidate pairs. A narrow key has many values and small blocks. It makes few pairs, but one small difference puts two records in different blocks. The two letters of the first name make about 24 times fewer pairs. The largest block is now trem|ma: 316 records whose surname starts with “trem” and whose first name starts with “ma”.
Keys need clean values
Section titled “Keys need clean values”A key compares exact values. So build it from the clean values of Module 2, not from the values as typed. TREMBLAY, VAL and Valérie Tremblay give the same key only after normalising: no capitals, no accents, and the surname split from the first name. Here, a short first name still helps: “val” and “valérie” both start with va.
Several keys together
Section titled “Several keys together”Now combine keys, as the library combines its drawers. A pair is a candidate when the two records share any of the keys. In set language, the candidate pairs are the union of the pairs of each key.
The diagram shows it on the six records of the last lesson.
Text description of the diagram
The six records again: Samuel Green’s four records (1 to 4), his brother Nathan (5) and Jacques Beaulieu (6). The postcode puts records 1, 2, 3 and 5 in one block: 6 pairs, 3 of them true. Record 4, Samuel’s old record, is alone. The surname key puts Samuel’s four records in the block gree|sa: 6 pairs, all true. Nathan is alone in gree|na, because his first name starts with “na”. Together, the two keys make 9 candidate pairs: the 6 pairs among Samuel’s records, and 3 pairs of Nathan with Samuel. All 6 true pairs are kept.
In this example, the surname key alone already keeps every true pair. On the full data, it does not: each key catches true pairs that the other loses. The postcode alone keeps 0.845 of the true pairs. The surname key alone keeps 0.849. Together they keep 0.976.
The cost is small, because most pairs that the two keys make are different. Together they make 1,103,620 candidate pairs: only 68,122 more than the surname key alone.
The project’s five keys
Section titled “The project’s five keys”The project’s default blocking, keys, uses five keys together:
- the postcode
- the email
- the phone
- the surname key (4 letters of the surname, 2 of the first name)
- the date of birth with the first letter of the first name
Each key alone keeps between 0.235 and 0.849 of the true pairs. Together they keep 0.9937, with 1,108,591 candidate pairs. The date of birth gets the first letter of the first name because many people share a birthday: the letter keeps the blocks small.
This is the same idea as an inverted index in search: for each key value, a list of the records that have it. Search and Ranking: Find the Best Match builds one in The inverted index.
Run it in the project
Section titled “Run it in the project”Add the blocking code of this module to your project.
-
In your project folder, with the TermVirtual environmentA folder with its own Python and its own packages, for one project. Packages that you install there do not change other projects.Learn more Isolate dependenciesPython for Practical AI Engineering active, copy the blocking files from the snapshot
end-of-m03. Copy itsrequirements.txtandREADME.mdtoo:Terminal window S=../nextia-learning-labs/C39/snapshots/end-of-m03cp $S/larkfield_match/blocking.py larkfield_match/cp $S/larkfield_match/commands/block.py larkfield_match/commands/cp $S/tests/test_blocking.py tests/cp $S/requirements.txt $S/README.md .Terminal window $S = "..\nextia-learning-labs\C39\snapshots\end-of-m03"Copy-Item $S\larkfield_match\blocking.py larkfield_match\Copy-Item $S\larkfield_match\commands\block.py larkfield_match\commands\Copy-Item $S\tests\test_blocking.py tests\Copy-Item $S\requirements.txt, $S\README.md .blocking.pyalso has the MinHash code of the next lesson. The newrequirements.txtadds one package for it:datasketch. -
Install the new package:
Terminal window python -m pip install -r requirements.txtThe last line names the new packages:
Successfully installed datasketch-2.0.0 scipy-1.18.1 -
Run the tests. There are 21 now:
Terminal window python -m pytest -q..................... [100%]21 passed in 5.05s -
List the blockings that the project knows:
Terminal window match block --listpostcode customers same postcodesurname customers same first 4 letters of the surname and first 2 of the first namesurname-wide customers same first 4 letters of the surname and first letter of the first nameemail customers same emailphone customers same phonedob customers same date of birth and first letter of the first namepostcode+surname customers postcode, or surname startkeys customers postcode, email, phone, surname start or date of birth (the default)keys+street customers the default keys and the street number with the start of the streetsorted-name customers sorted neighbourhood on the full name, window 10sorted-name-50 customers sorted neighbourhood on the full name, window 50keys-wide customers the default keys with the wider surname keyp-brand products same brandp-minhash products MinHash LSH on title shingles (threshold 0.5)p-minhash-0.3 products MinHash LSH on title shingles (threshold 0.3)p-minhash+gtin products MinHash LSH (0.5) or the same barcode
Now make the candidate pairs of one key, then of two keys, then of five:
match block --blocking surnamematch block --blocking postcode+surnamematch block --blocking keyssurname: 1,035,498 candidate pairs out of 1,806,455,778 possible pairs (4.91 s) pair completeness 0.849 (23,489 of 27,677 true pairs kept); reduction ratio 0.999427postcode+surname: 1,103,620 candidate pairs out of 1,806,455,778 possible pairs (4.29 s) pair completeness 0.976 (27,019 of 27,677 true pairs kept); reduction ratio 0.999389keys: 1,108,591 candidate pairs out of 1,806,455,778 possible pairs (6.0 s) pair completeness 0.994 (27,503 of 27,677 true pairs kept); reduction ratio 0.999386Our laptop was busy during this run, so the times are long. On a quiet laptop, keys took 0.24 seconds. Your times will differ; the counts will not. Each run saves its pairs in outputs/candidates/, for the later modules.
How the code makes the pairs
Section titled “How the code makes the pairs”Open larkfield_match/blocking.py. The function key_pairs makes the pairs of each key column, and joins the lists:
def key_pairs(keys, cols): parts = [same_value_pairs(keys, c) for c in cols] return pd.concat(parts).drop_duplicates(["record_id_l", "record_id_r"]).reset_index(drop=True)same_value_pairs joins the key table to itself on one column, and keeps each pair once, with the smaller record ID first. A pair that two keys find is kept only once: that is what drop_duplicates does.
Sorted neighbourhood: no exact key needed
Section titled “Sorted neighbourhood: no exact key needed”A key needs an exact match. “gagnon” and “gagnoj” give different blocks. Is there a way to pair records that are only close?
Think of the library’s author drawers again. A reader looks for “Gagnon”. The card says “Gagnoj” by mistake. It is not under “Gagnon”, but it is right next to it. A reader who looks at the few cards around the place still finds it.
Sorted neighbourhood does this. Sort all records by one value, such as the full name. Then slide a window of w records down the sorted list. Pair each record with the w − 1 records after it.
Text description of the diagram
The six records sorted by name: Jacques Beaulieu first, then Nathan Green, then Samuel Green’s four records, in the order of their record IDs. A window of 3 records slides down the list. Each record is paired with the next two. That makes 9 candidate pairs: 1–2, 1–3, 2–3, 2–4, 3–4, 3–5, 4–5, 4–6 and 5–6. Five of them are Samuel with himself. One true pair is lost: positions 3 and 6, Samuel’s records G-001688 and S-007770, are three places apart.
A window of w makes about n × (w − 1) pairs. It grows with the number of records, not with its square. With a window of 10, Larkfield’s 60,108 records give 540,927 pairs.
Sorted neighbourhood on Larkfield’s names
Section titled “Sorted neighbourhood on Larkfield’s names”match block --blocking sorted-namematch block --blocking sorted-name-50sorted-name: 540,927 candidate pairs out of 1,806,455,778 possible pairs (1.4 s) pair completeness 0.543 (15,023 of 27,677 true pairs kept); reduction ratio 0.999701sorted-name-50: 2,944,067 candidate pairs out of 1,806,455,778 possible pairs (7.85 s) pair completeness 0.800 (22,144 of 27,677 true pairs kept); reduction ratio 0.998370The result is poor. A window of 10 keeps only 0.543 of the true pairs. A window of 50 keeps 0.800, with 2.9 million pairs: more pairs than the five keys, and far fewer true pairs.
Why? Look at the sort order. The full name starts with the first name: samuel green. So the list is sorted by first name first. “Samuel Green” and “Sam Green” are far apart: every “Samuel” with another surname lies between them. Common names make long runs of equal values, and a true pair inside a long run is often more than w places apart.
Sorted neighbourhood works best when:
- the sort value has its errors near the end, not at the start (a typing error in “Gagnon” at the last letter, not the first);
- the values are rare, so equal values make short runs;
- you cannot make a good exact key.
A common fix is several passes, each sorted by another value: the surname, then the postcode, then the phone. The union of the passes is the blocking, as with keys.
When to use which
Section titled “When to use which”| Method | Use it when | What it costs |
|---|---|---|
| One key | one field is reliable, and you need a fast first try | it loses every true pair where that field differs or is empty |
| Several keys together | the default for customer records | more candidate pairs; each key must be measured |
| Sorted neighbourhood | no exact key works, and errors are at the end of a value | true pairs in long runs of common values are lost |
The window size and the key width do the same job: they trade candidate pairs against true pairs. Choose them by measurement, not by feel.
Common mistake
A key on a field that is often empty
Symptom: TermTomásLarkfield’s AI engineer. He often suggests a quick shortcut, and the lesson shows why it fails. blocks on the date of birth: “One person has one birthday, so this key cannot be wrong.” He gets only 8,757 candidate pairs, and the matcher finds very few customers.
dob: 8,757 candidate pairs out of 1,806,455,778 possible pairs (1.77 s) pair completeness 0.235 (6,495 of 27,677 true pairs kept); reduction ratio 0.999995Cause: the key is right where it exists, but it is often empty. The garden centres have no date of birth in 84.7% of their records, and the shop in 54.6%. A record with an empty key is in no block, so it is never compared. The pair completeness is 0.235: 77% of the true pairs are lost before any comparison.
Fix: never block on one field. Use the date of birth as one key among several, as the project’s keys does. And before you choose a key, check how often its field is empty in each source, as in Meet the records.
Consequence in AI work: an empty value is not a disagreement, and it is not an agreement either. A key that skips empty values silently removes whole groups of records. Here, it removes most garden-centre customers.
Knowledge check
Section titled “Knowledge check”Check your understanding
The postcode keeps 0.845 of the true pairs and the surname key keeps 0.849. Together they keep 0.976. Why is the result much higher than either key alone, and why does it cost only 68,122 more candidate pairs than the surname key?
Show the answer
The two keys lose different true pairs. The postcode loses the customers who moved; most of them keep their surname and first name, so the surname key catches them. The surname key loses names with an error in the first letters; most of those customers keep their postcode. A pair is a candidate when it shares either key, so it is lost only when both keys fail. The cost is small because the keys find many of the same pairs. Two records of one household often share both the postcode and the surname. Each pair is counted once.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Check your understanding
The first letter of the surname makes 120,104,444 pairs. The first 4 letters plus 2 letters of the first name make 1,035,498. Why is the first key so much worse, even though it has a higher pair completeness?
Show the answer
The first letter has only 23 values, so the blocks are big: the largest has 5,780 records. A block of k records makes k × (k − 1) / 2 pairs, so big blocks make huge numbers of pairs. 120 million pairs is too many to compare and to hold in memory. The narrower key has 7,499 values and a largest block of 316 records. It loses a few more true pairs, but it makes 116 times fewer candidate pairs. The other keys catch most of the pairs that it loses.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Check your understanding
A colleague wants to use sorted neighbourhood on the email, with a window of 5, in place of the email key. Name one true pair that it would catch and the key would miss, and one that both would miss.
Show the answer
It catches an email with a typing error near the end, for example mariepaquette@… and mariepaqquette@…: sorted by email, the two land close together. The exact email key misses them. Both methods miss a customer who uses the family email thebouchards@example.org in one list and her own cbouchard@post.example in another. The two emails sort far apart, and they are not equal. Both also miss every record with an empty email.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Recap
- A blocking key is a short value made from clean fields. The surname key is the first 4 letters of the surname and the first 2 of the first name.
- Wide keys make huge blocks: a block of k records makes k × (k − 1) / 2 pairs. Narrow keys lose true pairs at small differences.
- Keys together catch what one key misses. The project’s five keys keep 0.9937 of the true pairs with 1,108,591 candidates. The postcode alone keeps 0.845; with the surname key, 0.976.
- Sorted neighbourhood pairs each record with the next w − 1 in a sorted list. On Larkfield’s names it keeps only 0.543 (window 10) and 0.800 (window 50).
- A key on a field that is often empty, such as the date of birth, loses most true pairs.
Keys work for names and postcodes. But two product titles that describe one hose seldom share an exact value. Next, MinHash and LSH find similar titles without comparing every pair.
Next: MinHash and LSH