Finding Near Matches Without Comparing Everything
Suppose a library receives a new paragraph and wants to know whether it resembles any of ten million stored paragraphs. Comparing it with every item is exact, but expensive. Similarity search replaces that exhaustive scan with a cheaper question: can we assign compact signatures so that genuinely similar objects are likely to meet in the same bucket?
The first step is to decide what “similar” means. For sets of document shingles, Jaccard similarity measures shared elements relative to all distinct elements present. For numerical feature vectors, cosine similarity measures alignment and largely ignores magnitude. Angular distance turns that alignment into an angle, while an $\ell_p$ distance measures coordinate-wise displacement. These choices are not interchangeable: two documents may use the same vocabulary in very different proportions, and two images may point in the same feature direction while differing greatly in brightness or scale.
For a tiny example, let document $A$ have shingle set $\{a,b,c,d\}$ and document $B$ have $\{b,c,d,e\}$. Their intersection contains three shingles and their union contains five, so $J(A,B)=3/5=0.6$. A MinHash signature does not store those sets. Instead, each independent random ordering keeps only the first present shingle. Across many orderings, the fraction of matching minima estimates $0.6$ because a shared shingle is the minimum of the union with probability $3/5$.
This raises the chapter’s central questions. How can a collision be an unbiased similarity measurement? How many signature entries make the estimate reliable? How can bands amplify the difference between near and far pairs? When do preprocessing choices, dependent hashes, or adversarial inputs invalidate the mathematical model?
Locality-sensitive hashing is a probabilistic candidate generator: similar objects collide more often than dissimilar ones. A collision is evidence worth verifying, not proof that two objects are similar—and a missing collision does not prove they are dissimilar.
| Concept | Intuitive meaning | Exact example | Non-example or boundary | Main assumption | Question answered |
|---|---|---|---|---|---|
| Jaccard similarity | Shared set content divided by total distinct content | $J(\{a,b,c\},\{b,c,d\})=2/4$ | Repeated word counts are discarded | Objects are meaningfully represented as sets | How much set membership overlaps? |
| Cosine similarity | Alignment of two nonzero vectors | $(1,1)\cdot(2,2)/(\sqrt2\sqrt8)=1$ | Identical direction need not mean equal magnitude | Direction carries the relevant signal | Do feature profiles point the same way? |
| Angular distance | Normalized angle between vectors | Parallel nonzero vectors have distance $0$ | The zero vector has no defined angle | Vectors are nonzero | How far apart are directions metrically? |
| $\ell_p$ distance | Coordinate-wise displacement | $\lVert(1,2)-(4,6)\rVert_2=5$ | Large rescaling is not ignored | Coordinates and scale are comparable | How far apart are points in a normed space? |
| MinHash | Random minimum that preserves Jaccard collision probability | Matching in about $60$ of $100$ rows when $J=0.6$ | One matching row is not a reliable estimate | Each row behaves as an independent random permutation or suitable hash | Can set similarity be sketched? |
| LSH family | Hash family whose collision chance decreases with distance | Near pairs collide with probability at least $p_1$ | Ordinary uniform hashing deliberately destroys locality | The stated near and far thresholds match the data geometry | Can likely neighbors be shortlisted? |
Finding Near Matches Without Comparing Everything
Let $A=\{a,b,c,d\}$, $B=\{b,c,d,e\}$, and $C=\{w,x,y,z\}$.
- Compute intersections and unions. You should obtain $J(A,B)=3/5=0.6$ and $J(A,C)=0$.
- Use these three supplied orderings of the universe: $(a,e,b,c,d,w,x,y,z)$, $(c,b,z,d,e,a,w,x,y)$, and $(e,d,b,a,c,w,x,y,z)$. Record the first element from each set in every ordering.
- The signatures are $A=(a,c,d)$, $B=(e,c,e)$, and $C=(w,z,w)$. Thus $A$ and $B$ agree once in three trials; neither agrees with $C$.
- Explain the gap between the estimate $1/3$ and the true value $3/5$: three Bernoulli trials have high variance. With $k$ independent rows, the estimate has standard deviation $\sqrt{s(1-s)/k}$ when the true Jaccard similarity is $s$.
Reflection: would adding more hash rows repair a poor shingle definition? No. More rows reduce sampling error around the similarity of the chosen representation; they do not make that representation semantically appropriate.
Sets, Signatures and Collision Probability
Let $A$ and $B$ be finite, nonempty subsets of a universe $U$. Their Jaccard similarity is $J(A,B)=|A\cap B|/|A\cup B|$. Choose a uniformly random permutation $\pi$ of $U$, and define $h_\pi(A)=\min\{\pi(x):x\in A\}$. The minimum element of $A\cup B$ is equally likely to be any union member. The two minima match exactly when that element lies in $A\cap B$. Therefore
$$ \Pr[h_\pi(A)=h_\pi(B)]=\frac{|A\cap B|}{|A\cup B|}=J(A,B). $$
With $k$ independent MinHash rows, let $X_i$ indicate a collision in row $i$ and let $\widehat J=k^{-1}\sum_i X_i$. Then $\mathbb E[\widehat J]=J$ and $\operatorname{Var}(\widehat J)=J(1-J)/k$. This statement quantifies randomness over the chosen hashes while the sets remain fixed. It neither promises semantic similarity nor guarantees a small error for every pair simultaneously without an additional concentration and union-bound argument.
b-bit MinHash keeps only the lowest $b$ bits of each minimum. It saves space but introduces accidental matches. In the common large-universe approximation, the observed bit-match probability is $q\approx 2^{-b}+(1-2^{-b})J$, so an approximately debiased estimate is $(q-2^{-b})/(1-2^{-b})$.
For nonzero vectors $x,y\in\mathbb R^d$, cosine similarity is $c(x,y)=x\cdot y/(\lVert x\rVert_2\lVert y\rVert_2)$ and angular distance is $\theta/\pi$, where $\theta=\arccos c$. If $r$ is drawn from a rotationally symmetric distribution and $h_r(x)=\operatorname{sign}(r\cdot x)$, then random-hyperplane or SimHash satisfies $\Pr[h_r(x)=h_r(y)]=1-\theta/\pi$. For $\ell_p$ distance with $0\lt p\le 2$, p-stable LSH projects onto a random p-stable vector and quantizes the result into shifted intervals; its collision probability decreases with $\lVert x-y\rVert_p$.
flowchart TD
A[Choose representation] --> B{Geometry}
B -->|Sets| C[Jaccard similarity]
B -->|Directions| D[Angular distance]
B -->|Coordinate distance| E[lp distance]
C --> F[Random minimum]
D --> G[Random hyperplane]
E --> H[p-stable projection]
F --> I[Collision probability equals Jaccard]
G --> J[Collision probability equals one minus angle over pi]
H --> K[Collision probability decreases with distance]
I --> L[Repeat independent hashes]
J --> L
K --> L
L --> M[Estimate or amplify]
classDef navy fill:#17365D,color:#fff,stroke:#17365D;
classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
class A,B navy;
class C,D,E teal;
class F,G,H purple;
class I,J,K crimson;
class L,M navy;
| Definition or claim | Exact scope | Required assumptions | What it does not imply | Failure example | Consequence |
|---|---|---|---|---|---|
| MinHash collision identity | $\Pr[h(A)=h(B)]=J(A,B)$ for fixed nonempty finite sets | Uniform random permutation, or a hash construction with the needed minwise behavior | A single collision establishes high similarity | Two disjoint sets may collide after aggressive b-bit truncation | Repeat full MinHash rows or correct truncated matches |
| MinHash estimator | Mean of $k$ collision indicators is unbiased with variance $J(1-J)/k$ | Independent or adequately independent rows | Every pair has low error merely because one pair does | Reusing one hash as if it supplied independent rows understates uncertainty | Size $k$ from an error and confidence target |
| SimHash identity | Hyperplane-sign agreement is $1-\theta/\pi$ | Nonzero vectors and rotationally symmetric random normals | Cosine captures vector magnitude | $(1,1)$ and $(100,100)$ collide always although magnitudes differ | Normalize only when scale should be irrelevant |
| p-stable LSH | Quantized projection collision probability decreases with $\ell_p$ distance | $0\lt p\le2$, correct p-stable distribution, common bucket width and random shift | One parameter is optimal for every distance scale | A bucket width far below measurement noise destroys useful collisions | Tune width around the operational radius |
| LSH sensitivity | Near pairs collide at least $p_1$ and far pairs at most $p_2$, with $p_1\gt p_2$ | Declared metric, thresholds $R$ and $cR$, and probability bounds | Middle-distance pairs receive a guarantee | Points between $R$ and $cR$ may behave arbitrarily | State the approximation gap explicitly |
| b-bit compression | Low bits reduce signature storage | Known accidental-match baseline and sufficiently large universe | Bit matches equal raw MinHash matches | With $b=1$, unrelated rows match about half the time | Debias and validate at the intended similarity range |
The central MinHash invariant is that the minimum of a randomly ordered union belongs to the intersection exactly when both sets report the same minimum. Hence the collision probability equals Jaccard similarity—not approximately in the ideal model, but exactly; approximation enters when finitely many hashes estimate that probability or when practical hashes and truncation replace ideal permutations.
Locality-Sensitive Families and Candidate Amplification
An $(R,cR,p_1,p_2)$-sensitive family for a distance $d$ obeys two quantified promises: every pair with $d(x,y)\le R$ collides with probability at least $p_1$, and every pair with $d(x,y)\ge cR$ collides with probability at most $p_2$, where $c\gt1$ and $p_1\gt p_2$. It says nothing mandatory about the gray zone between $R$ and $cR$.
Amplification combines independent base hashes. An AND construction concatenates $r$ hashes, so a pair with base collision probability $s$ survives one table with probability $s^r$. This suppresses far collisions, but also loses some true neighbors. An OR construction builds $b$ independent tables and accepts a pair if any table matches. Its candidate probability is
$$ P_{b,r}(s)=1-(1-s^r)^b. $$
For MinHash banding, $s$ is Jaccard similarity. The curve is often described by a rough transition near $s\approx(1/b)^{1/r}$, but it is not a hard threshold. The correct tuning question is operational: choose $b$ and $r$ so that $P_{b,r}(s_{near})$ meets the required recall while $P_{b,r}(s_{far})$ keeps the candidate workload affordable.
Independence enters twice: the $r$ rows in a band justify multiplying probabilities, and the $b$ bands justify the complement-product formula. Correlated hashes can make the calculated curve optimistic. Candidate verification therefore recomputes the chosen exact similarity or a higher-quality approximation on the retrieved pairs.
flowchart TD
A[Premise: fixed pair has base collision probability s] --> B[Independent rows within a band]
B --> C[All r rows match with probability s to the r]
C --> D[Independent bands]
D --> E[No band matches with probability one minus s to the r, raised to b]
E --> F[At least one band matches with complementary probability]
F --> G{Compare operating points}
G -->|Near probability meets recall| H[Keep parameters]
G -->|Far probability overloads verification| I[Increase rows or reduce bands]
B -. correlation breaks product .-> X[Calculated curve may be wrong]
D -. reused randomness .-> X
H --> J[Verify candidates with exact similarity]
I --> A
classDef navy fill:#17365D,color:#fff,stroke:#17365D;
classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
class A,B,D navy;
class C,E,F purple;
class G,H,J teal;
class I,X crimson;
Locality-Sensitive Families and Candidate Amplification
Assume MinHash similarity $s$, $r=3$ rows per band, and $b=4$ bands.
- One band: all three rows must match, so $P_{AND}(s)=s^3$.
- All bands fail: one band fails with probability $1-s^3$; four independent bands fail with probability $(1-s^3)^4$.
- At least one succeeds: $P_{4,3}(s)=1-(1-s^3)^4$.
- For a near pair with $s=0.8$, $s^3=0.512$ and $P_{4,3}(0.8)=1-0.488^4\approx0.943$. For a far pair with $s=0.3$, $s^3=0.027$ and $P_{4,3}(0.3)=1-0.973^4\approx0.104$.
- In a collection containing $999{,}000$ far objects at similarity around $0.3$, the rough expected far-candidate count is still about $104{,}000$. A probability that looks small can be operationally huge.
Assumption-breaking variation: suppose all four bands reuse the same three rows. Then the four band events are identical, not independent, and the candidate probability is $s^3$, not $1-(1-s^3)^4$. State which predicted recall and load figures must be discarded.
| Analytical tool | What it establishes | Assumptions | Tightness or limitation | Representative failure case |
|---|---|---|---|---|
| Indicator expectation | Expected number or fraction of collisions | Correct marginal collision probability | Gives no high-confidence guarantee alone | Mean recall is acceptable but run-to-run variance is large |
| Binomial variance and concentration | Signature length needed for a target additive error | Independent bounded trials | Worst-case bounds may be conservative | Correlated rows make the advertised interval too narrow |
| AND construction | Far collisions shrink from $p_2$ to $p_2^r$ | Independent hashes within a band | Near collisions also shrink | Excessive $r$ produces many false negatives |
| OR construction | Recall rises to $1-(1-q)^b$ from per-table probability $q$ | Independent tables | Candidate volume also rises | Too many tables flood exact verification |
| Sensitivity exponent $\rho$ | Asymptotic query tradeoff, commonly $\rho=\log(1/p_1)/\log(1/p_2)$ | Stable near/far probabilities and an LSH data structure matching the analysis | Hides constants, skew, memory, and verification costs | A theoretically smaller $\rho$ loses in production due to giant buckets |
| Union bound | Converts per-pair failure bounds to many-pair guarantees | A known finite collection of events; independence not required | Can be loose | Claiming global accuracy from a per-query bound without accounting for query count |
| Empirical candidate curve | Tests model fit at operational thresholds | Representative labeled data and unchanged pipeline | Does not prove behavior under drift or attack | Evaluation corpus omits boilerplate-heavy documents |
Documents, Images and Duplicate Pipelines
For documents, convert normalized text into sets of word or character shingles, estimate Jaccard similarity with MinHash, retrieve candidates through banding, and verify them with exact Jaccard or an application-specific rule. This works well for near-duplicate detection, but the formal set model ignores word frequency and order beyond the shingle window.
For images, a perceptual embedding gives a numerical vector. Random-hyperplane LSH can retrieve vectors with small angular distance. The embedding—not SimHash—decides whether crops, recoloring, or semantically related scenes are near. If absolute feature magnitude is meaningful, cosine-based hashing may erase useful information.
For high-dimensional telemetry or product features, p-stable LSH can target $\ell_1$ or $\ell_2$ proximity. Units and normalization matter: an unscaled high-variance coordinate can dominate Euclidean distance. The method’s theorem applies to the vector space that the pipeline actually constructs, not to the real-world concept the team hoped those coordinates would represent.
Adversarial or misleading cases reveal the boundary. Boilerplate can inflate document overlap; repeated templated text can make unrelated pages appear near. Attackers who learn deterministic hash functions may craft bucket floods. Distribution drift can turn formerly balanced tables into hotspots. Exact verification protects precision, but it cannot recover true neighbors that preprocessing or candidate generation never surfaced.
Documents, Images and Duplicate Pipelines: Similarity, MinHash & Locality-Sensitive Hashing
A moderation team receives these token sets after normalization:
- $A=\{sale,today,red,shoes,free,ship\}$
- $B=\{sale,today,blue,shoes,free,ship\}$
- $C=\{weather,today,rain,west,coast\}$
Model selection: choose Jaccard because presence of normalized tokens matters and repeated counts are not trusted. Compute $J(A,B)=5/7\approx0.714$ and $J(A,C)=1/10=0.1$.
Use banding with $b=5$ and $r=2$. The candidate probability is $1-(1-s^2)^5$. For $A,B$, it is approximately $0.972$; for $A,C$, it is approximately $0.049$. With a verification threshold of $0.7$, $B$ should be retrieved and accepted, while $C$ should usually not become a candidate and must be rejected if it does.
Success criteria: on a labeled set of at least 500 pairs, candidate recall at Jaccard $0.7$ or above is at least $95\%$, verified precision is at least $99\%$, and the median number of candidates per query is below the agreed budget. Explain why the common token “today” should be monitored: frequent boilerplate can increase bucket load without expressing meaningful duplication.
Documents, Images and Duplicate Pipelines: Similarity, MinHash & Locality-Sensitive Hashing
A marketplace must detect copied listings among $50$ million active items. It ingests $2{,}000$ updates per second, requires candidate recall of at least $98\%$ for labeled duplicates, permits at most $200$ exact comparisons per query at the 99th percentile, and must respond within $150$ ms.
Proposed model: use language-aware normalization and character shingles for text, a separately calibrated image embedding for photographs, MinHash bands for text, and angular LSH for images. Generate candidates from either channel, then verify with exact text overlap, embedding distance, seller metadata, and policy rules. Do not combine unrelated collision probabilities as though they were independent until measured.
Evidence to collect: labeled near-duplicate and hard-negative pairs by language and category; empirical collision curves; bucket-size distributions; p50/p95/p99 candidate counts and latency; recall before verification; precision after verification; hash-seed sensitivity; drift after template or embedding changes; and adversarial tests using boilerplate stuffing and repeated image borders.
Risks and controls: cap or split hot buckets, rotate keyed hashes when abuse is plausible, retain multiple versions during representation migrations, and monitor recall through sampled exact-search audits. A candidate cap protects latency but silently damages recall unless overflow is measured.
Decision artifact: recommend parameters only if the lower confidence bound for duplicate recall exceeds $98\%$ in every critical segment and the p99 candidate count remains below $200$. Otherwise revise the representation or add a second retrieval path before adjusting verification thresholds; verification cannot recover omitted candidates.
Tune a Similarity Search System
Mastery means being able to move in both directions: from an application’s meaning of “near” to a mathematical geometry and collision curve, and from the curve back to recall, memory, verification load, and failure monitoring. The exercises below deliberately separate representation error, estimation error, retrieval error, and verification error.
Practice: Tune a Similarity Search System
Use a corpus of $N=1{,}000{,}000$ objects. Product owners call Jaccard similarity $0.8$ or above “near” and $0.3$ or below “far.” Candidate recall must be at least $0.95$, and expected far candidates must be below $20{,}000$ per query.
Tier 1 — Definitions. Write exact definitions for Jaccard, cosine similarity, angular distance, and an $(R,cR,p_1,p_2)$-sensitive family. Give one input for which cosine is undefined. Checkpoint: every definition states its domain and quantifiers.
Tier 2 — Estimation. For $k=200$ independent MinHash rows and true $J=0.8$, compute the standard deviation $\sqrt{0.8(0.2)/200}\approx0.0283$. Use a normal approximation to give a rough $95\%$ interval. Expected artifact: approximately $0.8\pm0.055$. Then explain why this is a per-pair approximation rather than a simultaneous guarantee for all corpus pairs.
Tier 3 — Amplification. Evaluate $P_{b,r}(s)=1-(1-s^r)^b$ for $(b,r)=(10,5)$ at $s=0.8$ and $s=0.3$. You should obtain near recall about $0.981$ and far probability about $0.0240$, implying roughly $24{,}000$ far candidates—recall passes, load fails. Try $(b,r)=(9,5)$: near recall is about $0.974$, while far candidates fall to about $21{,}700$, still above budget. Search integer pairs with $br\le100$ and report the smallest signature satisfying both constraints, or demonstrate that your search range contains no solution.
Tier 4 — Counterexample. Construct two unrelated web pages sharing a large navigation footer. Compare word-set Jaccard before and after boilerplate removal. Debugging prompt: if increasing signature length leaves false matches unchanged, suspect the representation rather than estimator variance.
Tier 5 — Application. Choose among MinHash, SimHash, and p-stable LSH for (a) shingle sets, (b) normalized semantic embeddings, and (c) unnormalized Euclidean sensor vectors. Justify the geometry, preprocessing, collision interpretation, and exact verifier.
Tier 6 — Professional judgment. Produce a one-page tuning memo containing: target near and far thresholds; empirical collision plots; selected $b,r$ or equivalent parameters; confidence intervals; candidate-count percentiles; memory and latency estimates; skew and adversarial tests; fallback behavior for hot buckets; and a rollback trigger.
Stretch goal: compare a single LSH configuration with two configurations optimized for different similarity ranges. Discuss additional memory, recall, and operational complexity.
Rubric (10 points): definitions and domains 2; correct derivations 2; representation-aware counterexample 2; measurable parameter decision 2; monitoring and failure analysis 2. Full credit requires distinguishing candidate recall from verified precision and stating where independence is used.
Decision checklist: choose the meaning and geometry of similarity first; validate the base collision law; tune amplification at explicit near and far operating points; budget candidates, memory, and latency; verify retrieved pairs; and monitor skew, drift, and adversarial inputs. Do not confuse a signature match with identity, a sharp-looking banding curve with a hard threshold, or more hashes with a cure for poor features. This chapter builds on randomized hashing and cardinality sketches; next, connect these ideas to sliding windows, mergeable sketches, and systems where the data distribution changes over time.
Next in the Series
In Sliding Windows & Time Decay, we'll explore Make summaries reflect recent rather than lifetime data..