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 followsI 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)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 0I 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.Next I look for similar sketches by doing the followingI split the sketch vector into b bands of r bitsEach 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.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?
Amplifying a Locality Sensitive Hash
machine learning
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 bitsand I run my previous procedure c times, each time on b * r bitsIf 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 1At the end of the c procedures I group these pairs by key and sumAny 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...