LSH step by step

This page is a live teaching script. Move one step at a time: read two documents, turn them into shingles, compute exact Jaccard, approximate it with MinHash, then use banding to avoid checking every pair.

Step 1: Start with the raw objects

ADocument A

BDocument B

Step 2: Shingle the documents

Document A shingles

Document B shingles

Step 3: Compute exact Jaccard

J(A,B) = 0 / 0 = 0.00
0 shared shingles, the intersection
0 total distinct shingles, the union
0.00 exact Jaccard similarity

Mini-check

Before revealing the answer, ask students to compute the ratio from the two counts above.

Step 4: Compress with MinHash

signature agreement = 0 / 0 = 0.00
Row Signature A Signature B Same?

Step 5: Band the signature

candidate if at least one complete band matches

Step 6: Tune the system

0% recall: true near duplicates found
0% precision: candidates that are real
0% all pairs still checked
0 candidate pairs

Student challenge

Find settings with recall at least 90%, precision at least 50%, and no more than 40% of all pairs checked.

Pair Exact Jaccard Candidate? Status

Step 7: Compare with document embeddings

Important: this page uses a transparent toy embedding so students can see the idea offline. A production system would replace this with sentence or document embeddings from a trained model.
0.00 lexical Jaccard for selected pair
No selected pair is an LSH candidate
0.00 toy embedding cosine
No semantic neighbor at cosine >= 0.70

What changed?

LSH over shingles asks: "Do these documents share many exact word windows?" Embedding search asks: "Do these documents point in a similar semantic direction?"

When each one wins

Use shingle LSH for copied or lightly edited text. Use embeddings for paraphrases, topical similarity, and retrieval where the wording can change.

Selected pair embedding dimensions

Document A Document B
Pair Lexical Jaccard LSH candidate? Embedding cosine What it shows