Skip to content
Français

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.

Plays from YouTube. Nothing loads from YouTube until you press play. Privacy

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 notebookColab · Kaggle · GitHub

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 readyAbout 40 minutes

What you need to know

What you need on your computer

  • The project larkfield-match with 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.

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
The share of true pairs that each key keeps, on all 60,108 synthetic records. Surname key = the first 4 letters of the surname and the first 2 of the first name. Five keys = the project's default keys.
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.

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.

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”.

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.

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.

The six records with their postcode and surname key. Key 1, postcode: block M7K4L8 has records 1, 2, 3 and 5 and makes 6 pairs; L0H6T9 has record 4 and J8Y1L3 has record 6, with no pairs. 6 candidate pairs, 3 of 6 true pairs kept. Key 2, surname start: block gree|sa has records 1, 2, 3 and 4 and makes 6 pairs; gree|na has record 5 and beau|ja record 6, with no pairs. 6 candidate pairs, 6 of 6 true pairs kept. Both keys together: a pair is a candidate when it shares key 1 or key 2: 9 candidate pairs, 6 of 6 true pairs kept.
The six records of the last lesson, blocked on two keys. Each key makes its own blocks. Together they make 9 candidate pairs and keep all 6 true pairs.
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 default blocking, keys, uses five keys together:

  1. the postcode
  2. the email
  3. the phone
  4. the surname key (4 letters of the surname, 2 of the first name)
  5. 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.

Add the blocking code of this module to your project.

  1. 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 its requirements.txt and README.md too:

    Terminal window
    S=../nextia-learning-labs/C39/snapshots/end-of-m03
    cp $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 .

    blocking.py also has the MinHash code of the next lesson. The new requirements.txt adds one package for it: datasketch.

  2. Install the new package:

    Terminal window
    python -m pip install -r requirements.txt

    The last line names the new packages:

    Successfully installed datasketch-2.0.0 scipy-1.18.1
  3. Run the tests. There are 21 now:

    Terminal window
    python -m pytest -q
    ..................... [100%]
    21 passed in 5.05s
  4. List the blockings that the project knows:

    Terminal window
    match block --list
    postcode customers same postcode
    surname customers same first 4 letters of the surname and first 2 of the first name
    surname-wide customers same first 4 letters of the surname and first letter of the first name
    email customers same email
    phone customers same phone
    dob customers same date of birth and first letter of the first name
    postcode+surname customers postcode, or surname start
    keys 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 street
    sorted-name customers sorted neighbourhood on the full name, window 10
    sorted-name-50 customers sorted neighbourhood on the full name, window 50
    keys-wide customers the default keys with the wider surname key
    p-brand products same brand
    p-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:

Terminal window
match block --blocking surname
match block --blocking postcode+surname
match block --blocking keys
surname: 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.999427
postcode+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.999389
keys: 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.999386

Our 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.

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.

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.

Step 1: the six records sorted by name: 1 jacques beaulieu (G-009906), 2 nathan green (G-002894), 3 samuel green (G-001688), 4 samuel green (G-008438), 5 samuel green (L-011126), 6 samuel green (S-007770). Dashed boxes show windows of 3, one per starting row. Step 2: the pairs inside each window: 1-2, 1-3, 2-3, 2-4, 3-4, 3-5, 4-5, 4-6, 5-6; the last five are the same person. Window 3: each record is paired with the next 2. 9 candidate pairs, 5 of 6 true pairs kept. Lost: 3-6, the same person, but too far apart in the list.
Sorted neighbourhood with a window of 3, on the same six records. The numbers here are the positions in the sorted list. No key must be equal, but a true pair that sorts far apart is lost.
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”
Terminal window
match block --blocking sorted-name
match block --blocking sorted-name-50
sorted-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.999701
sorted-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.998370

The 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.

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.999995

Cause: 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.

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.

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.

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.

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