Python optomise nearest neighbour for large arrays
Question: I have an array of points in 4D space (my array is roughly 1,000,000 long).
For each value in my array I need to find the kth (where k = 81) nearest
neighbours

I then do some further code based on that..

_[in brief, I'm effectively trying to extend the SSIM algorithm but for a
picture sitting in 4D - I have a list of values with len(my_values)=1,000,000
= len(my_coords). Although as an added complication my 'picture' is not made
of points in a simple grid, but is more like a collection of 1,000,000 'point-
stars' distributed psudo-randomly in 4D space - that for difference sets of
'my_values' have difference brightnesses, but always the same location... That
context may not be needed :) ]._

Roughly I need to do:

    
    
    from scipy.spatial import KDTree 
    mytree = KDTree(my_coords)
    for i in range(len(my_coords)):
        dist, locs = mytree.query(my_coords[i], k=k)
        ....
        result.append(some_function(dist,locs,my_values_pic1[locs],my_values_pic2[locs]))
    

I tried querying mytree with the full 'my_coords' but this caused a memory
problem. - also obviously that for loop takes forever.... so needs to be
optomized.

I'm trying to change my loop to do chunks of about 300 points at a time and
then stiching together the result - I'm just wondering if I'm missing
something obvious that could make this even faster?


Answer: KNN only works efficiently for small datasets. In order to deal with larger
ones efficiently, you'll have to perform data reduction by selecting prototype
points that are capable of representing your classes accurately.

[Wikipedia has a good overview of the
process](https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm#Data_reduction)

