<p>You are seeking an approach for the <em>K</em>-nearest neighbor problem consisting of two steps:</p>

<ol>
<li>Finding the Euclidean distances between the elements;</li>
<li>Finding the first <code>K</code> elements providing the <code>K</code> smallest distances.</li>
</ol>

<p>It seems that such an approach is already existing and has been implemented in</p>

<p><a href="http://arxiv.org/pdf/0906.0231.pdf" rel="nofollow">K.Kato and T.Hosino, "Solving <em>k</em>-Nearest Neighbor Problem on Multiple Graphics Processors"</a></p>

<p>and presented at the 2009 GTC Conference as</p>

<p><a href="http://on-demand.gputechconf.com/gtc/2009/presentations/1034-Multi-GPU-Recommendation-System.pdf" rel="nofollow">K.Kato and T.Hosino, "You Might Also Like: A Multi-GPU Recommendation System"</a>.</p>

<p>The approach solves the above two steps by</p>

<ol>
<li>using the classical <em>N</em>-body approach developed in L.Nyland, M.Harris, J.Prins, "Fast <em>N</em>-body simulation with CUDA," In: GPU Gems III. NVIDIA (2007) 677–695 to calculate the Euclidean distances;</li>
<li>using the <a href="http://www.lsi.upc.edu/~conrado/research/talks/aofa04.pdf" rel="nofollow">partial sorting</a> technique, based on a parallel heapsort idea.</li>
</ol>

<p>Again, as mentioned in my comment above, a better approach avoiding your "brute-force" one would be to use <a href="https://sites.google.com/a/nirmauni.ac.in/cudacodes/cuda-projects/proj-12-gpu-nearest-neighbors-using-a-minimal-kd-tree" rel="nofollow">KD-trees</a>. </p>
Sorting the smallest K elements of a vector to implement a brute-force K-nearest neighbor algorithm on GPU
<p>I have implemented a <em>K</em>-nearest neighbor on the GPU using both pure CUDA and Thrust library function calls.</p>

<p>Euclidean distances are computed with a pure CUDA kernel. Then, Thrust sorting facilities (radix sort) are used to sort the distances in increasing order. Finally, the <em>K</em> first elements (i.e. the <em>K</em> nearest neighbors) are retrieved from the sorted vectors.</p>

<p>My implementation works well. However, sorting the entire euclidean distances matrix (sets can contain more than <code>250000</code> train samples) just to retrieve the <em>K</em>-nn seems non-optimal.</p>

<p>Therefore, I'm searching for a GPU algorithm implementation which allows to stop the sorting computations once the <em>K</em> smallest elements are found, or which performs an efficient <em>K</em> out of <em>N</em> sorting. It would indeed be faster for small <em>K</em> than sorting the entire matrix.</p>

<p>If such an implementation is not available, I would also be interested by advices to implement it efficiently in pure CUDA or Thrust. I was thinking to use a few threads per test samples to look for <em>K</em> nearest, each thread running to a part of the euclidean distances. I would maintain a buffer of size <em>K</em> in shared memory. I would run through the distances and insert the Knn in the shared memory vector. However, it would require some warp level synchronization and thread divergence.</p>

<p>Thank you for your help.</p>