10-605 · Randomized algorithms 2 · LSH

SimHash bitstrings for MSML course titles

Each course title is a sparse vector x whose features f are its tokens. Bit i of its signature is a random hyperplane test, LSH[i] = sum(x[f]·r[i,f] for f in x) > 0 ? 1 : 0, with r[i,f] ~ Normal(0,1). Two vectors at angle θ disagree on a bit with probability θ/π, so similar titles get codes with small Hamming distance. The vertical dividers split each n-bit code h into m substrings h(1),…,h(m) for multi-index hashing.

 
 
 
 

Signatures, sorted by Hamming distance to q

courseLSH bits Ham cos
10 bit differs from q number after h⁽ᶻ⁾ = Hamming(q⁽ᶻ⁾, h⁽ᶻ⁾), bold green if < r/m, gray otherwise Hamming(q⁽ᶻ⁾, h⁽ᶻ⁾) ≤ D, for the D picked in q's row under h⁽ᶻ⁾

Click a title to make it q · click a bit to see how it was computed · click the Ham or cos column to plot Hamming distance against cosine.

Multi-index hashing

Algorithm

LSH(x):
  for i = 1 to outputBits:
    LSH[i] = sum(x[f]*r[i,f] for f in x) > 0 ? 1 : 0
  pooled: r[i,f] = pool[hash(i,f) % poolSize]
MIH candidates for q, radius r:
  split each code h into h(1),…,h(m)
  return all h with Hamming(q(z), h(z)) < r/m
         for some z

One bit

Hamming distance vs. cosine

E[Ham/n] = θ/π MIH candidate not a candidate r/n ★the row you clicked

Each dot is one course h. A course is a multi-index-hashing candidate if some substring has Hamming(q(z), h(z)) < r/m. Every dot below the dashed line (Hamming < r) must be one: that is the pigeonhole claim. Click a dot to make it q.