Amplifying a Locality Sensitive Hash
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...