Amplifying a Locality Sensitive Hash

Question

I'm trying to build a cosine locality sensitive hash so I can find candidate similar pairs of items without having to compare every possible pair. I have it basically working, but most of the pairs in my data seem to have cosine similarity in the -0.2 to +0.2 range so I'm trying to dice it quite finely and pick things with cosine similarity 0.1 and above.

I've been reading Mining Massive Datasets chapter 3. This talks about increasing the accuracy of candidate pair selection by Amplifying a Locality-Sensitive Family. I think I just about understand the mathematical explanation, but I'm struggling to see how I implement this practically.

What I have so far is as follows

1. I have say 1000 movies each with ratings from some selection of 1M users. Each movie is represented by a sparse vector of user scores (row number = user ID, value = user's score)
2. I build N random vectors. The vector length matches the length of the movie vectors (i.e. the number of users). The vector values are +1 or -1. I actually encode these vectors as binary to save space, with +1 mapped to 1 and -1 mapped to 0
3. I build sketch vectors for each movie by taking the dot product of the movie and each of the N random vectors (or rather, if I create a matrix R by laying the N random vectors horizontally and layering them on top of each other then the sketch for movie m is R*m), then taking the sign of each element in the resulting vector, so I end with a sketch vector for each movie of +1s and -1s, which again I encode as binary. Each vector is length N bits.
4. Next I look for similar sketches by doing the following
   1. I split the sketch vector into b bands of r bits
   2. Each band of r bits is a number. I combine that number with the band number and add the movie to a hash bucket under that number. Each movie can be added to more than one bucket.
   3. I then look in each bucket. Any movies that are in the same bucket are candidate pairs.

Comparing this to 3.6.3 of mmds, my AND step is when I look at bands of r bits - a pair of movies pass the AND step if the r bits have the same value. My OR step happens in the buckets: movies are candidate pairs if they are both in any of the buckets.

The book suggests I can "amplify" my results by adding more AND and OR steps, but I'm at a loss for how to do this practically as the explanation of the construction process for further layers is in terms of checking pairwise equality rather than coming up with bucket numbers.

Can anyone help me understand how to do this?

Answer 1

I think I've worked something out. Basically I'm looking for an approach that works in a map/reduce type environment and I think this approach does it.

So,

• suppose I have b bands of r rows and I want to add another AND stage, say another c ANDs.
• so instead of b * r bits I need hashes of b * r * c bits
• and I run my previous procedure c times, each time on b * r bits
• If x and y are found to be a candidate pair by any of these procedures it emits a key value pair ((x, y), 1), with the tuple of IDs (x,y) as the key and the value 1
• At the end of the c procedures I group these pairs by key and sum
• Any pair (x,y) with a sum equal to c was a candidate pair in each of the c rounds, and so is a candidate pair of the entire procedure.

So now I have a workable solution, and all I need to do is work out whether using 3 steps like this will actually help me get a better result with fewer overall hash bits or better overall performance...

Answer 2

I would have just commented but I can't. I've been looking for a practical treatment of amplification in LSH and what you've presented makes a lot of sense. From what I gather, the primary hash function is $$h(x,v)=\left\{ \begin{array}{ll}0 & \mbox{if }\textrm{sgn}(x\cdot v) < 0\\ 1 & \mbox{else}\end{array} \right.$$ for some random vector $v$, after the AND this becomes $h'(x,i) = (h(x,v_{i+1}),...,h(x,v_{i+r}))$, and finally after the OR, $h''(x,j) =f(h'(x,rj),j)$ or $$h''(x,y) =\left\{ \begin{array}{ll}1 & \mbox{if }h''(x,j) = h''(y,j) \mbox{ for any }j \in [0,b)\\ 0 & \mbox{else}\end{array} \right.$$ Now you can AND/OR using $h''(x,y)$ as you describe. You would then just be choosing candidates based on AND/OR logical statements; you're not really hashing anymore. At this point to continue hashing, you'd need a mapping $\hat{h}:S\to S'$ of the bins such that each vector only appears once in $S'$, but doing so will also likely introduce false positives and/or negatives. One idea for a hash is the minimum of $h''(x,j)$ for all $j$ (or the minimum across all $j$ and all directly and indirectly associated $y$). Both clearly would introduce bias. I might try one of these, though I'm not sure the hashes from one random AND/OR will be meaningful the next time around. But considering a uniform distribution of random $v$ and large number of replications, maybe?