<blockquote>
  <p>use a kd-tree</p>
</blockquote>

<p>Unfortunately, in high dimensions this data structure suffers severely from the <a href="https://en.wikipedia.org/wiki/Curse_of_dimensionality" rel="nofollow noreferrer">curse of dimensionality</a>, which causes its search time to be comparable to the brute force search.</p>

<blockquote>
  <p>reduce the number of dimensions</p>
</blockquote>

<p><a href="https://en.wikipedia.org/wiki/Dimensionality_reduction" rel="nofollow noreferrer">Dimensionality reduction</a> is a good approach, which offers a fair trade-off between accuracy and speed. You lose some information when you reduce your dimensions, but gain some speed.</p>

<p>By accuracy I mean finding the exact Nearest Neighbor (NN).</p>

<p>Principal Component Analysis(<a href="https://en.wikipedia.org/wiki/Dimensionality_reduction#Principal_component_analysis_.28PCA.29" rel="nofollow noreferrer">PCA</a>) is a good idea when you want to reduce the dimensional space your data live on.</p>

<blockquote>
  <p>Is there some clever algorithm or data structure to solve this exactly in reasonable time?</p>
</blockquote>

<p>Approximate nearest neighbor search (<a href="https://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_nearest_neighbor" rel="nofollow noreferrer">ANNS</a>), where you are satisfied with finding a point that might not be the exact Nearest Neighbor, but rather a good approximation of it (that is the 4th for example NN to your query, while you are looking for the 1st NN).</p>

<p>That approach cost you accuracy, but increases performance significantly. Moreover, the probability of finding a good NN (close enough to the query) is relatively high.</p>

<p>You could read more about ANNS in the introduction our kd-GeRaF <a href="https://arxiv.org/pdf/1603.09596.pdf" rel="nofollow noreferrer">paper</a>.</p>

<p>A good idea is to combine ANNS with dimensionality reduction.</p>

<p>Locality Sensitive Hashing (<a href="https://en.wikipedia.org/wiki/Locality-sensitive_hashing" rel="nofollow noreferrer">LSH</a>) is a modern approach to solve the Nearest Neighbor problem in high dimensions. The key idea is that points that lie close to each other are hashed to the same bucket. So when a query arrives, it will be hashed to a bucket, where that bucket (and usually its neighboring ones) contain good NN candidates).</p>

<p><a href="https://github.com/FALCONN-LIB/FALCONN" rel="nofollow noreferrer">FALCONN</a> is a good C++ implementation, which focuses in cosine similarity. Another good implementation is our <a href="https://github.com/gsamaras/Dolphinn" rel="nofollow noreferrer">DOLPHINN</a>, which is a more general library.</p>
How to efficiently find k-nearest neighbours in high-dimensional data?
<p>So I have about 16,000 75-dimensional data points, and for each point I want to find its k nearest neighbours (using euclidean distance, currently k=2 if this makes it easiser)</p>

<p>My first thought was to use a kd-tree for this, but as it turns out they become rather inefficient as the number of dimension grows. In my sample implementation, its only slightly faster than exhaustive search.</p>

<p>My next idea would be using PCA (Principal Component Analysis) to reduce the number of dimensions, but I was wondering: Is there some clever algorithm or data structure to solve this exactly in reasonable time?</p>