Design Blocking for 20 Million Customer Records
A retailer has 20 million customer records from a web shop, a loyalty programme and a call centre. Fields: first name, last name, date of birth (often missing), street address, zip code, phone and email (both often missing). Names and addresses are typed by hand, so typos, nicknames and abbreviations are common. You have about 5,000 labelled true duplicate pairs from past manual merges.
- Compute the number of pairs a naive comparison needs and explain why blocking is needed.
- Propose a multi-pass blocking plan: name the keys, say what each one is good and bad at, and say how you would add a fuzzy pass.
- State the metrics you would use to choose between plans and the numbers you would set as a budget.
- Name two ways a block can become dangerously large and what you do about them.
1. The arithmetic. All pairs is n(n-1)/2, which for n = 2 \times 10^7 is about 2 \times 10^{14} pairs. At 10^6 comparisons per second per core that is more than 6 core-years, so even a perfect classifier is unusable without blocking. Blocking replaces the quadratic count with a candidate set of roughly (pairs per record) \times\, n.
2. A multi-pass plan. Use several keys and take the union, because every single key fails on some typo:
- Exact email and exact normalized phone: very high pair quality but only fire when present (in the lesson's data 52 percent of phones and 57 percent of emails were missing, and phone alone had a pair completeness of only 0.12).
- Soundex of last name + first initial + birth year (or house number): tolerant of spelling variants in the name; loses a pair if the year or the initial is wrong or missing.
- Zip + first 3 letters of last name: survives a first-name variation; loses movers (zip differs) and surname changes.
- Date of birth (exact, and with day and month swapped): strong, but often missing.
- A fuzzy pass: MinHash with LSH on character 3-grams of "last first street zip" (for example b=20 bands of r=5 rows, threshold near (1/20)^{1/5} \approx 0.55 in Jaccard similarity), or a sorted-neighbourhood pass with a window of 10 on two different sort keys. These catch typo-ridden pairs that no exact key sees.
In the lesson's synthetic data the tight single keys reached pair completeness between 0.12 and 0.62 (a loose Soundex-plus-initial key reached 0.80 only by producing 56.6 candidate pairs per record); the union of eight keys reached 0.9028 at 10.3 candidate pairs per record, and adding an LSH pass reached 0.9104 at 12.2.
3. Metrics and budget. Compare plans on pair completeness (share of the labelled true pairs that become candidates; this is the recall ceiling), pairs per record (compute cost) and pair quality; the reduction ratio is almost always above 0.999 and does not discriminate. A sensible budget: pair completeness at least 0.92 on a labelled set that was not used to design the keys, and 10 to 20 pairs per record, i.e. 200 to 400 million candidate pairs for 20 million records. Check the labelled pairs are representative: manual merges are biased toward easy, visible duplicates, so also use a sampled set (see the recall question).
4. Oversized blocks. (a) A frequent value (the surname with the most holders had 7,225 records in the lesson's data, which is about 26 million pairs in one block); (b) a default or junk value such as a shared placeholder email or phone, which can make a block of millions. Fixes: cap the block size and refine large blocks with a second key; add stop-lists of junk values found by frequency profiling; or drop the key for records with a frequent value. Review the largest block per key after each data refresh.
Share this question