title: How to implement LSH by MapReduce?
body: <p>Suppose we wish to implement Local Sensitive Hashing(LSH) by MapReduce. Specifically, assume chunks of the signature matrix consist of columns, and elements are key-value pairs where the key is the column number and the value is the signature itself (i.e., a vector of values).</p>
  
  <p>(a) Show how to produce the buckets for all the bands as output of a single
  MapReduce process. Hint: Remember that a Map function can produce
  several key-value pairs from a single element.</p>
  
  <p>(b) Show how another MapReduce process can convert the output of (a) to
  a list of pairs that need to be compared. Specifically, for each column i,
  there should be a list of those columns j > i with which i needs to be
  compared.</p>