MinHash and LSH
- Lesson 10
- 40 min
- Module 3: Blocking: do not compare everything
Where we are
Blocking keys need one field that agrees exactly. Product titles rarely agree exactly. In this lesson, we use MinHash and LSH to find similar titles without comparing all of them, with five product titles as the example.
Lesson 10 of 29 · Entity Resolution and Record Matching: Is This the Same Thing?MinHash and LSH
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
Find pairs of similar texts, such as two product titles for one hose, without comparing every pair. Learn the three steps of MinHash LSH: shingles, signatures and bands. Then measure it 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 two supplier feeds.
NotebookShingles, signatures and bands in a notebook
The notebook computes the shingles and the Jaccard similarity of the five titles. You write a small MinHash yourself, and see that its agreement is close to the Jaccard similarity. Then you block the two supplier feeds with the datasketch library and measure the result. 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
- Blocking keys, several keys together, and pair completeness, from Blocking keys and sorted neighbourhood.
- Larkfield’s two supplier feeds, from Meet the records.
- A set is a collection of different items, in no order. Python has
set().
What you need on your computer
- The project
larkfield-matchwith the blocking files of the last lesson. Or use the notebook only.
Two titles for one hose
Section titled “Two titles for one hose”Think of a librarian who receives two lists of new books from two shops. One list says “The Garden Year, by A. Morel, paperback”. The other says “Morel – garden year (the), pbk”. It is the same book. No field matches exactly: not the title, not the author, not the format. But the two lines share most of their pieces: “garden”, “year”, “morel”.
Larkfield’s merchandising lead, Hana, has the same problem with the two supplier feeds. Northfield Supply sends 4,460 products, and Copperleaf Wholesale sends 3,501. Here are five of their titles:
| Title | Feed | Product ID | |
|---|---|---|---|
| A | Mossway Vinyl Garden Hose 30 ft Brown | Northfield | NF-03673 |
| B | gdn hose 9.1 m vinyl brown MOSSWAY | Copperleaf | CL-03459 |
| C | Mossway Vinyl Garden Hose 30 ft Brown Pack of 2 | Northfield | NF-02877 |
| D | Copperwren Ceramic Planter 12 in Black | Northfield | NF-01651 |
| E | planter 30.5 cm ceramic black Copperwren | Copperleaf | CL-00741 |
We removed only the punctuation. The words are as the feeds write them. A and B are one hose: 30 feet is 9.1 metres. D and E are one planter: 12 inches is 30.5 centimetres. C is a pack of two hoses: another product, a practice problem that we made on purpose. All feeds are synthetic.
The problem: no key works for titles
Section titled “The problem: no key works for titles”Try the keys of the last lesson. The title as a key fails: no two of these titles are equal. The first word fails: “Mossway” against “gdn”, and “Copperwren” against “planter”. The brand works here, after lower case, but it makes huge blocks: every Mossway product of one feed meets every Mossway product of the other.
On the full feeds, the brand key makes 783,869 candidate pairs. It keeps all 2,750 true pairs, but it removes only 95% of the 15,614,460 possible pairs.
What we want: a pair becomes a candidate when the two titles are similar, not equal. And we must find those pairs without comparing every pair, or we are back at the start.
Step 1: shingles and Jaccard
Section titled “Step 1: shingles and Jaccard”First, decide what “similar” means. Cut each title into shingles: every run of 3 characters, after lower case. “garden hose” gives “gar”, “ard”, “rde”, “den”, “en “, “n h”, “ ho”, “hos”, “ose”. A title becomes a set of shingles. Word order does not matter much: “hose rubber” and “rubber hose” share most of their shingles.
Two sets are similar when they share many items. The Jaccard similarity measures this:
Jaccard = the shingles in both titles ÷ the shingles in either title
For A and B: A has 35 shingles and B has 32. They share 19, and together they have 48 different shingles. Jaccard = 19 ÷ 48 = 0.396.
Here are all ten pairs of the five titles:
| Pair | What it is | Jaccard | MinHash agreement (100 values) |
|---|---|---|---|
| A–B | one hose, two feeds | 0.396 | 0.4 |
| A–C | hose and its pack of 2 | 0.778 | 0.79 |
| B–C | hose and pack of 2 | 0.351 | 0.37 |
| D–E | one planter, two feeds | 0.51 | 0.52 |
| A–D, A–E, B–D, B–E, C–D, C–E | a hose and a planter | 0.000 to 0.037 | 0.00 to 0.03 |
The true pairs, A–B and D–E, have a Jaccard of only 0.396 and 0.510. Feed B writes “gdn” for “garden”, metres for feet, and the brand at the end. The hose–planter pairs have almost nothing in common. The pack of two, C, is very close to A (0.778): the title only adds “Pack of 2”. So the wrong pair A–C is much more similar than the true pair A–B. Blocking must keep A–C as a candidate. The comparison step of Module 4 must then see that it is another product.
But computing the Jaccard of every pair is again all pairs. We need a short cut.
Step 2: MinHash signatures
Section titled “Step 2: MinHash signatures”Here is the trick, first as a game. Put every possible shingle in one long list, in a random order. For each title, walk down the list and stop at the first shingle that the title has. Write it down. Do this for titles A and B.
What is the chance that A and B write down the same shingle? The first shingle that either title has is equally likely to be any of the 48 shingles in A or B. A and B write the same one only when it is one of the 19 shared shingles. So the chance is 19 ÷ 48: exactly the Jaccard similarity.
One game gives only “same” or “not same”. So play it 100 times, each time with a new random order. The 100 results are the title’s MinHash signature. The share of games where A and B agree estimates their Jaccard.
In code, “a random order” is a hash function: a function that turns each shingle into a number that looks random. “The first shingle in the order” is the one with the smallest hash. That is where the name comes from: the minimum hash.
Here are the first 10 of the 100 values of A and B, from the course’s code:
| Hash function | A | B | Same? |
|---|---|---|---|
| 1 | 51,792,715 | 33,869,745 | no |
| 2 | 53,569,090 | 53,569,090 | yes |
| 3 | 56,648,782 | 56,648,782 | yes |
| 4 | 174,247,870 | 24,318,687 | no |
| 5 | 794,414 | 794,414 | yes |
| 6 | 106,014,239 | 106,014,239 | yes |
| 7 | 41,340,559 | 110,631,880 | no |
| 8 | 86,062,820 | 56,026,171 | no |
| 9 | 64,155,423 | 63,732,843 | no |
| 10 | 124,509,585 | 159,614,191 | no |
A and B agree on 4 of these 10 values, and on 40 of all 100. The Jaccard is 0.396. The table of the ten pairs shows the same for every pair: the agreement of 100 values is within 0.03 of the Jaccard.
The important part: each signature is computed from one title alone. No pair is compared to make it. And a signature has always 100 numbers, however long the title is.
Step 3: bands and buckets (LSH)
Section titled “Step 3: bands and buckets (LSH)”Signatures are short, but comparing every pair of signatures is still all pairs. The last step, locality-sensitive hashing (LSH), finds the similar pairs without a pair loop.
Cut each signature into bands. The project uses signatures of 128 values and 25 bands of 5 values each. For each band, put the title in a bucket named by its 5 values. Two titles in the same bucket for any band become a candidate pair.
This is blocking again: each band is one key, and the 25 bands are 25 keys together. Like the five keys of the last lesson, a pair needs only one band in common.
Text description of the diagram
Titles A and B go through three steps. Step 1 cuts each title into shingles of 3 characters: 35 for A and 32 for B, 19 shared, 48 in all, so the Jaccard similarity is 0.396. Step 2 makes a signature of 100 MinHash values for each title; A and B agree on 40 of them, close to the Jaccard. Step 3 cuts the signature into bands of 5 values. Titles with the same 5 values in any band land in the same bucket and become a candidate pair. In steps 1 to 3, each title is handled alone. Only pairs in a bucket are compared later.
Why bands make an S-curve
Section titled “Why bands make an S-curve”Why 5 values in a band? Because it makes a sharp line between similar and not similar.
Take a pair with Jaccard s. One MinHash value agrees with chance s. All 5 values of one band agree with chance s⁵. The pair fails to share a band only when all 25 bands fail. So:
chance to be a candidate = 1 − (1 − s⁵)²⁵
- 25 bands of 5 values
- One band of 5 values (dashed)
Text description of the chart
A line chart. The horizontal axis is the Jaccard similarity of two titles, from 0 to 1. The vertical axis is the chance that they become a candidate pair. The solid line, 25 bands of 5 values, is an S-curve: near 0 up to a similarity of 0.2 (0.008), 0.059 at 0.3, 0.227 at 0.4, 0.548 at 0.5, 0.868 at 0.6, 0.99 at 0.7, and 1.0 from 0.8. The dashed line, one band of 5 values, stays low: 0.03 at 0.5 and 0.17 at 0.7.
Read the curve:
- A pair with Jaccard 0.7 becomes a candidate 99 times in 100.
- A pair with Jaccard 0.3 becomes a candidate about 6 times in 100.
- A pair with Jaccard near 0, such as the hose and the planter, almost never.
The middle of the S is the threshold. The project asks datasketch for threshold 0.5, and the library chooses 25 bands of 5 rows for 128 values. More rows in a band make the S steeper and move it right. More bands move it left.
D–E, the planter, has a Jaccard of 0.510, near the threshold. With these bands, it becomes a candidate with a chance of about 0.58. A pair near the threshold is a coin toss. A–B, the hose, is worse: with a Jaccard of 0.396, its chance is only about 0.22. That is one reason why the project’s MinHash reads clean text. It reads the brand and the title words, without the size and the pack, and “gdn” becomes “garden”. Units such as “30 ft” and “9.1 m” then do not lower the similarity.
MinHash on Larkfield’s feeds
Section titled “MinHash on Larkfield’s feeds”The project has three blockings for products:
match block --blocking p-brandmatch block --blocking p-minhashmatch block --blocking p-minhash-0.3p-brand: 783,869 candidate pairs out of 15,614,460 possible pairs (7.27 s) pair completeness 1.000 (2,750 of 2,750 true pairs kept); reduction ratio 0.949799p-minhash: 118,700 candidate pairs out of 15,614,460 possible pairs (41.06 s) pair completeness 0.999 (2,748 of 2,750 true pairs kept); reduction ratio 0.992398p-minhash-0.3: 700,712 candidate pairs out of 15,614,460 possible pairs (24.96 s) pair completeness 1.000 (2,750 of 2,750 true pairs kept); reduction ratio 0.955124The possible pairs are 4,460 × 3,501 = 15,614,460: the project pairs products only across the two feeds. A feed does not list one product twice.
MinHash with threshold 0.5 makes 6.6 times fewer candidate pairs than the brand, and loses only 2 of the 2,750 true pairs. The lower threshold 0.3 keeps all of them, but makes almost as many pairs as the brand.
The times are long because our laptop was busy, and the first product blocking also prepares the products. On a quiet laptop, p-minhash took 2.29 seconds.
Add a key for the last two pairs
Section titled “Add a key for the last two pairs”Two true pairs are lost. Can a key catch them? Some products have a barcode (GTIN) in both feeds. p-minhash+gtin adds the barcode as a key:
match block --blocking p-minhash+gtinp-minhash+gtin: 118,701 candidate pairs out of 15,614,460 possible pairs (10.64 s) pair completeness 1.000 (2,749 of 2,750 true pairs kept); reduction ratio 0.992398One more candidate pair, and one more true pair. MinHash and keys combine in the same way as keys: a union. This is the project’s default blocking for products. The pair completeness prints as 1.000, but 1 true pair is still lost.
The same idea elsewhere
Section titled “The same idea elsewhere”MinHash LSH finds near neighbours in a large collection without comparing every pair. Search engines find similar documents in the same way. Embeddings, lists of numbers that describe the meaning of a text, use the same family of ideas. An index for nearest neighbours puts similar vectors near each other, so a query looks at only a few of them. Search and Ranking: Find the Best Match uses embeddings in Search by meaning. RAG: Building AI That Uses Your Data uses them to find passages. Module 6 tries embeddings as a blocking for customers.
When to use MinHash LSH
Section titled “When to use MinHash LSH”Use it for text where no field is equal but the words overlap: product titles, company names, addresses written in one line, short descriptions.
Do not use it when a good exact key exists. For customers, the five keys keep 0.9937 of the true pairs. They are faster, and easier to explain.
What it costs:
- Pairs near the threshold are a coin toss. Choose the threshold from the Jaccard of your true pairs, and measure pair completeness.
- Short texts are noisy. A name of 10 characters has only 8 shingles. One typing error changes up to 3 of them.
- It sees letters, not meaning. “30 ft” and “9.1 m” share no shingles. “Pack of 2” adds only a few. MinHash keeps the hose and its pack of two together, which is right for blocking. The decision belongs to the comparison step.
- The text must be clean. The notebook runs the same threshold on the raw titles, in lower case, with their sizes and units. It keeps only 0.73 of the true pairs. The project’s clean text, without size and pack, keeps 0.9993.
- Common words make big buckets. Words such as “garden” or “green” appear in thousands of titles. Removing the brand from the text, as the project does, or very common words, keeps the buckets small.
Common mistake
A threshold that is too high
Symptom: TermTomásLarkfield’s AI engineer. He often suggests a quick shortcut, and the lesson shows why it fails. wants fewer candidate pairs. He sets the MinHash threshold to 0.8. The candidate pairs fall, and so does the number of matched products. The pair of planters D and E is never compared.
Cause: the threshold is the middle of the S-curve. With threshold 0.8, a pair needs a Jaccard of about 0.8 to become a candidate with a chance of 50%. The planters have a Jaccard of 0.510, and the hose in two units 0.396. Both fall far below the S. Many true pairs of the feeds look like them: the same words in another order, another unit, another case.
Fix: choose the threshold from your true pairs, not from the number of candidates. Look at the Jaccard similarity of a sample of labelled true pairs. Put the threshold well below most of them. Then measure the pair completeness, as the project does with match block. The project uses 0.5.
Consequence in AI work: a blocking threshold is a recall setting for the whole matcher. Every true pair that it removes is a missed match, and no later model, however good, can bring it back.
Knowledge check
Section titled “Knowledge check”Check your understanding
Two titles have a Jaccard similarity of 0.6. With the project's 25 bands of 5 values, what is the chance that they become a candidate pair? Show the calculation.
Show the answer
One value agrees with chance 0.6. All 5 values of a band agree with chance 0.6⁵ = 0.078. A band fails with chance 1 − 0.078 = 0.922. All 25 bands fail with chance 0.922²⁵ = 0.132. So the pair becomes a candidate with chance 1 − 0.132 = 0.868. The S-curve shows the same value at 0.6.
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
Why does MinHash LSH not compare every pair, even though it estimates the Jaccard similarity of pairs?
Show the answer
The signature of each title is computed from that title alone: its shingles and 128 hash functions. Then each title goes into one bucket for each band, by the values of that band. A bucket is found with a dictionary lookup, not by comparing titles. Only the titles that land in the same bucket become candidate pairs. The work grows with the number of titles and of bands, not with the number of pairs.
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
MinHash makes the hose A and its pack of two, C, a candidate pair (Jaccard 0.778). Hana says: “Then MinHash is wrong: they are different products.” What do you answer?
Show the answer
Blocking does not decide “same”. It only chooses which pairs to compare. A and C are very similar texts, so they must be compared. A blocking that removed them would also remove many true pairs that differ by a few words. The comparison step must see the “Pack of 2” and say “different”. Module 4 compares sizes and packs, and Module 6 shows that embeddings also find these two titles very close. A blocking that makes a wrong pair a candidate costs only one comparison. A blocking that removes a true pair loses it for good.
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
- Shingles cut a text into runs of 3 characters. The Jaccard similarity of two sets of shingles is shared ÷ all. Titles A and B: 19 ÷ 48 = 0.396.
- A MinHash signature keeps the smallest hash of the shingles for each of many hash functions. The share of equal values estimates the Jaccard: A and B agree on 40 of 100.
- LSH cuts the signature into bands and puts each title in one bucket per band. Titles that share any bucket become candidates. With 25 bands of 5, the chance is 0.548 at Jaccard 0.5 and 0.99 at 0.7.
- On Larkfield’s feeds, MinHash (0.5) makes 118,700 candidates out of 15,614,460 and keeps 2,748 of 2,750 true pairs. The barcode as an extra key catches one more.
- MinHash sees letters, not meaning or units. Its threshold is a recall setting.
You now have three kinds of blocking: keys, sorted neighbourhood and MinHash LSH. Next, you measure what each one loses, and choose keys that catch the customers who moved.
Next: What blocking loses