title: Implement minhash LSH using Spark (Java)
body: <p>this is quite long, and I am sorry about this.</p>
  
  <p>I have been trying to implement the Minhash LSH algorithm discussed in <a href="http://infolab.stanford.edu/~ullman/mmds/ch3.pdf" rel="nofollow noreferrer">chapter 3</a> by using Spark (Java). I am using a toy problem like this:</p>
  
  <pre><code>+--------+------+------+------+------+
  |element | doc0 | doc1 | doc2 | doc3 |
  +--------+------+------+------+------+
  |   d    |   1  |  0   |  1   |  1   |
  |   c    |   0  |  1   |  0   |  1   |
  |   a    |   1  |  0   |  0   |  1   |
  |   b    |   0  |  0   |  1   |  0   |
  |   e    |   0  |  0   |  1   |  0   |  
  +--------+------+------+------+------+
  </code></pre>
  
  <p>the goal is to identify, among these four documents (<code>doc0</code>,<code>doc1</code>,<code>doc2</code> and <code>doc3</code>), which documents are similar to each other. And obviously, the only possible candidate pair would be <code>doc0</code> and <code>doc3</code>.</p>
  
  <p>Using Spark's support, generating the following "characteristic matrix" is as far as I can reach at this point:</p>
  
  <pre><code>+----+---------+-------------------------+
  |key |value    |vector                   |
  +----+---------+-------------------------+
  |key0|[a, d]   |(5,[0,2],[1.0,1.0])      |
  |key1|[c]      |(5,[1],[1.0])            |
  |key2|[b, d, e]|(5,[0,3,4],[1.0,1.0,1.0])|
  |key3|[a, c, d]|(5,[0,1,2],[1.0,1.0,1.0])|
  +----+---------+-------------------------+
  </code></pre>
  
  <p>and here is the code snippets:</p>
  
  <pre><code>CountVectorizer vectorizer = new CountVectorizer().setInputCol("value").setOutputCol("vector").setBinary(false);
  Dataset&lt;Row&gt; matrixDoc = vectorizer.fit(df).transform(df);
  
  MinHashLSH mh = new MinHashLSH()
    .setNumHashTables(5)
    .setInputCol("vector")
    .setOutputCol("hashes");
  
  MinHashLSHModel model = mh.fit(matrixDoc);
  </code></pre>
  
  <p>Now, there seems to be two main calls on the <code>MinHashLSHModel model</code> that one can use: <code>model.approxSimilarityJoin(...)</code> and <code>model.approxNearestNeighbors(...)</code>. Examples about using these two calls are here: <a href="https://spark.apache.org/docs/latest/ml-features.html#lsh-algorithms" rel="nofollow noreferrer">https://spark.apache.org/docs/latest/ml-features.html#lsh-algorithms</a></p>
  
  <p>On the other hand, <code>model.approxSimilarityJoin(...)</code> requires us to join two datasets, and I have only one dataset which has 4 documents and I would like to figure out which ones in these four are similar to each other, so I don't have a second dataset to join... Just to try it out, I actually joined my only dataset with itself. Based on the result, seems like <code>model.approxSimilarityJoin(...)</code> just did a pair-wise Jaccard calculation, and I don't see any impact by changing the number of Hash functions etc, left me wondering about where exactly the minhash signature was calculated and where the band/row partition has happened...</p>
  
  <p>The other call, <code>model.approxNearestNeighbors(...)</code>, actually asks a comparison point, and then the model will identify the nearest neighbor(s) to this given point... Obviously, this is not what I wanted either, since I have four toy documents, and I don't have an extra reference point.</p>
  
  <p>I am running out of ideas, so I went ahead implemented my own version of the algorithm, using Spark APIs, but <strong>not</strong> much support from <code>MinHashLSHModel model</code>, which really made me feel bad. I am thinking I must have missed something... ??</p>
  
  <p>I would love to hear any thoughts, really wish to solve the mystery.</p>
  
  <p>Thank you guys in advance!</p>