KD Tree gives different results to brute force method
<p>I have an array of 1000 random 3D points &amp; I am interested in the closest 10 points to any given point. <a href="http://stackoverflow.com/questions/2486093/millions-of-3d-points-how-to-find-the-10-of-them-closest-to-a-given-point">In essence the same as this post.</a></p>

<p>I checked the 2 solutions offered by J.F. Sebastian, namely a brute force approach &amp; a KD Tree approach. </p>

<p>Although both give me the same indices for the closest points, they give different results for the distances</p>

<pre><code>import numpy as np
from scipy.spatial import KDTree

a = 100 * np.random.rand(1000,3)
point = a[np.random.randint(0, 1001)] # point chosen at random

# KD Tree
tree = KDTree(a, leafsize=a.shape[0]+1)
dist_kd, ndx_kd = tree.query([point], k=10)

# Brute force
distances = ((a-point)**2).sum(axis=1)  # compute distances
ndx = distances.argsort() # indirect sort 
ndx_brt = ndx[:10]
dist_brt = distances[ndx[:10]]

# Output
print 'KD Tree:'
print ndx_kd
print dist_kd
print
print 'Brute force:'
print ndx_brt
print dist_brt
</code></pre>

<p>My output,</p>

<blockquote>
  <p>KD Tree: 
  [[838 860 595 684 554 396 793 197 652 330]] 
  [[  0.   3.00931208   8.30596471   9.47709122  10.98784209
     11.39555636  11.89088764  12.01566931  12.551557    12.77700426]]</p>
  
  <p>Brute force: 
  [838 860 595 684 554 396 793 197 652 330]<br>
  [   0.   9.05595922   68.9890498    89.81525793  120.73267386
    129.8587047   141.3932089   144.37630888  157.54158301  163.25183793]</p>
</blockquote>

<p>So what is the issue here? Am I calculating the distance wrong?</p>

<p><code>KDTree</code> algorithm is computing the nearest points based on the square-root of the same distance used by <code>Brute-force</code> algorithm.</p>

<p>Basically KDtree uses: <code>sqrt(x^2+y^2+z^2)</code> 
and Brute-force algorithm uses: <code>x^2+y^2+z^2</code></p>

python numpy scipy kdtree