Getting indices of nearest neighbor in one go

[Datseris]

Hi Kristoffer

Let's say that I have a tree:

using NearestNeighbors, StaticArrays
data = [rand(SVector{3}) for i in 1:1000]
tree = KDTree(data, Euclidean())

I found that I am implementing an algorithm where I want the nearest neighbor of a point very frequently. Sometimes I am also quering about it multiple times. I was wondering whether there is some way I can get the indices of nearest neighbors from the tree structure.

Of course I know I can do:

nind = [knn(tree, data[j], 1, false, i -> i == j)[1][1] for j in 1:length(data)]

but is there some "faster way" ?

edit: the tree is not an argument to my high-level function but created inside. so if there is a way to do what I want even during construction, then it will still be super useful

[KristofferC]

nind = knn(tree, data, 2)[1]; [ind[1] for ind in nind] is probably faster.

[Datseris]

You are right:

@time nind = [knn(tree, data[j], 1, false, i -> i == j)[1][1] for j in 1:length(data)]
@time nind2 = (x = knn(tree, data, 2)[1]; [ind[1] for ind in x])

  0.242659 seconds (107.59 k allocations: 5.473 MiB)
  0.062895 seconds (14.75 k allocations: 796.444 KiB)

(I don't know whether I should close this)

[JonasIsensee]

Hey there,
I continued working on this but I encountered another problem.
For large trees and low dimension there can be multiple identical points in the tree.

This is a problem since I need the nearest neighbor with norm(x[i] - x[j]) > 0 because this expression
is used in the denominator.
As a temporary solution I just skip those points but strictly speaking this is wrong.

[KristofferC]

Can't you filter identical points first, before creating the tree?

Also, #52 might be useful here.

[JonasIsensee]

Good question!
I'm working with delay embedding of timeseries, so I'm not sure if removing points would be a problem.
(Since that definitely would change indices of the following points and thereby mess up the time evolution)
I'll have to talk with @Datseris about this.

[KristofferC]

I meant only when creating the tree. If the problem is that you have two points in the exact same point you need to handle it somehow if you compute e.g. some 1/distance force between them since that is an unphysical result of the simulation