K-nearest neighbours in C# for large number of dimensions
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
}


This is a code smell. You shouldn't use a jagged double array to store an array of distances and indexes. Despite the comment, what you're doing is unclear, and it's very confusing to have a variable named distances that stores both distances and indexes. The only justification for this would be if you actually had hard profiling evidence that it caused a significant speedup.

Make a separate class (or struct, if you're worried about overhead) with members double distance; int index; and then trainInfo (the former distances) should just be a trainNumber-sized array of that type.

Also, since you only need the top K elements, you don't need to sort the whole list (n log n time). You ought to be able to do it with a partial sort (actual code sample) which is almost linear-speed. There are also parallel algorithms for this; you could probably get a speedup using PLINQ with a custom aggregate.

On to the next refactoring.

foreach (var voter in votingDistances)
{
    if (trainClasses[(int)voter[1]] == 1)  
       yea++;
    else
       nay++;
}


This code is also crying out for LINQ. How about

yea = votingDistances.AsParallel().Count(voter=&gt;trainClasses[voter.index] == 1);
nay = votingDistances.Count - yea;


And I'd refactor this:

for (var i = 0; i &lt; sample1.Count; i++)
{   
    var temp = sample1[i] - sample2[i];
    distance += temp * temp;
}


to this:

var differences = sample1.AsParallel().Zip(sample2,(s1,s2)=&gt;s1-s2);
distance = differences.Sum(x=&gt;x*x);


though you could get improved performance from a custom aggregate.