title: kNN with big sparse matrices in Python
body: <p>I have two large sparse matrices:</p>
  
  <pre><code>In [3]: trainX
  Out[3]: 
  &lt;6034195x755258 sparse matrix of type '&lt;type 'numpy.float64'&gt;'
          with 286674296 stored elements in Compressed Sparse Row format&gt;
  
  In [4]: testX
  Out[4]: 
  &lt;2013337x755258 sparse matrix of type '&lt;type 'numpy.float64'&gt;'
          with 95423596 stored elements in Compressed Sparse Row format&gt;
  </code></pre>
  
  <p>About 5 GB RAM in total to load.  Note these matrices are HIGHLY sparse (0.0062% occupied).</p>
  
  <p>For each row in <code>testX</code>, I want to find <strong><em>the</em></strong> Nearest Neighbor in <code>trainX</code> and return its corresponding label, found in <code>trainY</code>.  <code>trainY</code> is a list with the same length as <code>trainX</code> and has many many classes. (A class is made up of 1-5 separate labels, each label is one of 20,000, but the number of classes is not relevant to what I am trying to do right now.)</p>
  
  <p>I am using <code>sklearn</code>'s KNN algorithm to do this:</p>
  
  <pre><code>from sklearn import neighbors
  
  clf = neighbors.KNeighborsClassifier(n_neighbors=1)
  clf.fit(trainX, trainY)
  clf.predict(testX[0])
  </code></pre>
  
  <p>Even predicting for 1 item of <code>testX</code> takes a while (i.e. something like 30-60 secs, but if you multiply by 2 million, it becomes pretty much impossible).  My laptop with 16GB of RAM starts to swap a bit, but does manage to complete for 1 item in <code>testX</code>.</p>
  
  <p>My questions is, how can I do this so it will finish in reasonable time? Say one night on a large EC2 instance?  Would just having more RAM and preventing the swapping speed it up enough (my guess is no).  Maybe I can somehow make use of the sparsity to speed up the calculation?</p>
  
  <p>Thank you.</p>