title: How to best implement K-nearest neighbours in C# for large number of dimensions?
body: <p>I'm implementing the K-nearest neighbours classification algorithm in C# for a training and testing set of about 20,000 samples each, and 25 dimensions.  </p>
  
  <p>There are only two classes, represented by '0' and '1' in my implementation. For now, I have the following simple implementation :</p>
  
  <pre><code>// testSamples and trainSamples consists of about 20k vectors each with 25 dimensions
  // trainClasses contains 0 or 1 signifying the corresponding class for each sample in trainSamples
  static int[] TestKnnCase(IList&lt;double[]&gt; trainSamples, IList&lt;double[]&gt; testSamples, IList&lt;int[]&gt; trainClasses, int K)
  {
      Console.WriteLine("Performing KNN with K = "+K);
  
      var testResults = new int[testSamples.Count()]; 
  
      var testNumber = testSamples.Count();
      var trainNumber = trainSamples.Count();
      // Declaring these here so that I don't have to 'new' them over and over again in the main loop, 
      // just to save some overhead
      var distances = new double[trainNumber][]; 
      for (var i = 0; i &lt; trainNumber; i++)
      {
         distances[i] = new double[2]; // Will store both distance and index in here
      }
  
      // Performing KNN ...
      for (var tst = 0; tst &lt; testNumber; tst++)
      {
          // For every test sample, calculate distance from every training sample
          Parallel.For(0, trainNumber, trn =&gt;
          {
              var dist = GetDistance(testSamples[tst], trainSamples[trn]);
              // Storing distance as well as index 
              distances[trn][0] = dist;
              distances[trn][1] = trn;
          });
  
          // Sort distances and take top K (?What happens in case of multiple points at the same distance?)
          var votingDistances = distances.AsParallel().OrderBy(t =&gt; t[0]).Take(K);
  
          // Do a 'majority vote' to classify test sample
          var yea = 0.0;
          var nay = 0.0;
  
          foreach (var voter in votingDistances)
          {
              if (trainClasses[(int)voter[1]] == 1)  
                 yea++;
              else
                 nay++;
          }
          if (yea &gt; nay)
              testResults[tst] = 1;
          else
              testResults[tst] = 0;
  
      }
  
      return testResults;
  }
  
  // Calculates and returns square of Euclidean distance between two vectors
  static double GetDistance(IList&lt;double&gt; sample1, IList&lt;double&gt; sample2)
  {
      var distance = 0.0;
      // assume sample1 and sample2 are valid i.e. same length 
  
      for (var i = 0; i &lt; sample1.Count; i++)
      {   
          var temp = sample1[i] - sample2[i];
          distance += temp * temp;
      }
      return distance;
  }
  </code></pre>
  
  <p>This takes quite a bit of time to execute. On my system it takes about 80 seconds to complete. How can I optimize this, while ensuring that it would also scale to larger number of data samples? As you can see, I've tried using PLINQ and parallel for loops, which did help (without these, it was taking about 120 seconds). What else can I do?</p>
  
  <p>I've read about KD-trees being efficient for KNN in general, but every source I read stated that they're not efficient for higher dimensions.</p>
  
  <p>I also found <a href="https://stackoverflow.com/questions/3962775/how-to-efficiently-find-k-nearest-neighbours-in-high-dimensional-data">this stackoverflow discussion</a> about this, but it seems like this is 3 years old, and I was hoping that someone would know about better solutions to this problem by now.</p>
  
  <p>I've looked at machine learning libraries in C#, but for various reasons I don't want to call R or C code from my C# program, and some other libraries I saw were no more efficient than the code I've written. Now I'm just trying to figure out how I could write the most optimized code for this myself.</p>
  
  <p>Edited to add - I cannot reduce the number of dimensions using PCA or something. For this particular model, 25 dimensions are required.</p>