10-605 · Randomized algorithms 2 · LSH

Multi-index hashing with MinHash bands

Goal: given q, find all q′ with sim(q,q′) > s₀. Every string gets M MinHashes k_i(q) = min(h_i(w) for w in q), grouped into b bands of r rows (M = b·r), with one inverted index per band. q′ is a candidate if it matches q on all r hashes of any band, so Pr(q′ is missed) = (1 − sim(q,q′)^r)^b. Here each q is a cartoon character's name, and its words w are character 3-grams.

query q pick a name or type anything

bands b

rows per band r

threshold s₀

presets (slide 50)

Words w in q

Signatures k(q) , grouped into bands — cells show the w achieving the min; hover for the value

Following the b inverted indices

Algorithm

Build:
  for each q′ in the collection:
    k(q′) = (k₁(q′), …, k_M(q′)),  k_i(q′) = min(h_i(w) for w in q′)
    for z = 1, …, b:
      index_z[ k_(z−1)r+1(q′), …, k_zr(q′) ] += q′
Query q:
  recompute k(q)
  candidates = ∪_z index_z[ k_(z−1)r+1(q), …, k_zr(q) ]
  optionally rescore: keep q′ with sim(q, q′) > s₀

Candidate recall vs. sim(q, q′)

1 − (1 − s^r)^b q′ is a candidate not a candidate s₀

Each dot is one q′ in the collection, placed at its true Jaccard similarity on the curve of the probability that it becomes a candidate. Click a dot to compare its signature with q.

Summary

The collection

q′	sim	bands	Pr(cand)	status

found: sim > s₀ and a candidate · missed: sim > s₀ but no band matched · extra: a candidate with sim ≤ s₀ (discarded by rescoring).