title: Nearest neighbors in high-dimensional data?
body: <p>I have asked a <a href="https://stackoverflow.com/questions/5684370/finding-k-nearest-neighbors-for-a-given-vector">question</a> a few days back on how to find the nearest neighbors for a given vector. My vector is now 21 dimensions and before I proceed further, because I am not from the domain of Machine Learning nor Math, I am beginning to ask myself some fundamental questions:</p>
  
  <ul>
  <li>Is Euclidean distance a good metric for finding the nearest neighbors in the first place? If not, what are my options?</li>
  <li>In addition, how does one go about deciding the right threshold for determining the k-neighbors? Is there some analysis that can be done to figure this value out?</li>
  <li>Previously, I was suggested to use kd-Trees but the Wikipedia page clearly says that for high-dimensions, kd-Tree is almost equivalent to a brute-force search. In that case, what is the best way to find nearest-neighbors in a million point dataset efficiently?</li>
  </ul>
  
  <p>Can someone please clarify the some (or all) of the above questions?</p>