<p>There were some requirements for the algorithm on the relation between training instances and the dimensions of your vectors , but you can try <a href="https://databricks.com/blog/2014/10/20/efficient-similarity-algorithm-now-in-spark-twitter.html" rel="nofollow noreferrer">DIMSUM</a>.</p>

<p>You can find the paper <a href="https://arxiv.org/abs/1304.1467" rel="nofollow noreferrer">here</a>.</p>
Find top K cosine similar vectors to a given vector efficiently
<p><strong><em>The problem:</em></strong></p>

<p>Suppose I have a group of around 1,000,000 short documents D (no more than 50 words each), and I want to let users to supply a document from the same group D, and and get the top K similar documents from D.</p>

<p><strong><em>My approach:</em></strong></p>

<p>My first approach was to preprocess the group D by applying simple tf-idf, and after I have vector for each document, which is extremely sparse, to use a simple nearest neighbours algorithm based on cosine similarity.
Then, on query time, to justuse my static nearest neighbours table which its size is 1,000,000 x K, without any further calculations.</p>

<p>After applying tf-idf, I got vectors in size ~200,000, which means now I have a very sparse table (that can be stored efficiently in memory using sparse vectors) in size 1,000,000 x 200,000.
However, calculating the nearest neighbours model took me more than one day, and still haven't finished.
I tried to lower the vectors dimension by applying HashingTF, that utilizes the <a href="https://en.wikipedia.org/wiki/Feature_hashing" rel="noreferrer">hasing trick</a>, instead, so I can set the dimension to a constant one (in my case, i used 2^13 for uninfied hashing),  but still I get the same bad performance.</p>

<p>Some technical information:</p>

<p>I use Spark 2.0 for the tf-idf calculation, and sklearn NearestNeighbours on the collected data.</p>

<p>Is thier any more efficient way to achieve that goal?</p>

<p>Thanks in advance.</p>

<p><strong>Edit:</strong></p>

<p>I had an idea to try a <a href="https://en.wikipedia.org/wiki/Locality-sensitive_hashing" rel="noreferrer">LSH</a> based approximation similarity algorithm like those implemented in spark as described <a href="https://spark.apache.org/docs/latest/ml-features.html#locality-sensitive-hashing" rel="noreferrer">here</a>, but could not find one that supports the 'cosine' similarity metric.</p>