title: K Nearest Neighbors (KNN) for sparse matrices using custom distance metric
body: <p>Given a sparse matrix (created using <a href="https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.sparse.csr_matrix.html" rel="nofollow noreferrer"><code>scipy.sparse.csr_matrix</code></a>) of size NxN (N = 900,000), I'm trying to find, for every row in testset, top k nearest neighbors (sparse row vectors from the input matrix) using a custom distance metric. Basically, each row of the input matrix represents an item and for each item (row) in testset, I need to find it's knn.</p>
  
  <p>Attempts:</p>
  
  <ul>
  <li><p>Tried using <a href="http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.NearestNeighbors.html#sklearn.neighbors.NearestNeighbors" rel="nofollow noreferrer"><code>sklearn.neighbors.NearestNeighbor</code></a>. However, it appears that sklearn doesn't take callable metric function as input when dealing with sparse matrices:</p>
  
  <pre><code>ValueError: metric '&lt;function &lt;lambda&gt; at 0x7f92ce221938&gt;' not valid for sparse input
  </code></pre></li>
  <li><p>Currently trying to use <a href="https://github.com/facebookresearch/pysparnn" rel="nofollow noreferrer">facebookresearch/pysparnn</a> (looks really promising!). It has a certain provision for implementing one's own custom distance class. However, after execution, it's taking quite long to build the index (still running after 24 hrs) and as <a href="https://github.com/facebookresearch/pysparnn/issues/11#issuecomment-285901090" rel="nofollow noreferrer">mentioned</a> by the author, it seems that </p>
  
  <blockquote>
    <p>using distance types from <code>scipy.spatial.distance.cdist</code> (or sklearn distance metrics) is much slower than what is currently in pysparnn.</p>
  </blockquote>
  
  <p>We're in process of debugging this performance issue of sklearn/scipy distance metrics by writing something custom.</p></li>
  </ul>
  
  <p>I'd like to know if there is any other efficient implementation of nearest neighbor search for sparse matrices which provides for using a custom distance metric?<br>
  (Will be executed on a server with 64 GB RAM, 12 cores)</p>
  
  <p>Thanks!</p>