# Nearest neighbor search in n-dimensions

Suppose a list of items such as:
L1 = RandomReal[{0, 100}, 1000];

I need to find the position of each k-neighbor in the original list. And very quickly if possible.
As we can see, the problem is divided into two main parts :
- The search for k-neighbors.
- The search for their positions in the original list.

Mathematica code

On Mathematica 9.0

Doedalos :

KPosition1[x_, y_] :=
Block[
{step0, step1, step2},
step0 = Range[1, Length@x, 1];
step1 = (Nearest[x, x[[#]], y][[2 ;; -1]]) & /@ step0;
step2 = Map[Position[x, #][[1, 1]] &, step1, {2}]
];

KPosition2[x_, y_] :=
Block[
{step0, step1, step2},
step0 = Thread[x -> Range[1, Length@x, 1]];
step1 = Nearest[step0 , #, y] & /@ x
];


Bill s :

KPosition3[x_, y_] :=
Block[
{step0, step1, step2},
step0 = Thread[x -> Range[1, Length@x, 1]];
step1 = Nearest[step0];
step2 = Map[step1[#, y][[2 ;; -1]] &, x]
];


On Mathematica 10.0

kale :

KPosition4[x_, y_] :=
With[
{p = PositionIndex[x]},
Map[p[#][[1]] &, Nearest[x, x, y][[All, 2 ;; -1]], {2}]
];


Mr.Wizard :

KPosition5[x_, y_] := Nearest[x -> Range@Length@x, x, y];


Benchmarking

Warning : Only Kposition1, Kposition2 and Kposition3 are tested.

1) By varying the length of the lists.

2) By varying the dimension of the points.

Commentary

On Mathematica 9.0

Sort by execution's speed :
Kposition3 > Kposition2 > Kposition1

On Mathematica 10.0

If somebody wants to make the benchmarks... Currently, I has not the version 10 of Mathematica.

You can speed it up by only invoking the NearestFunction once:

KPosition3[x_, y_] :=
Module[{step0, step1, nf},
step0 = Thread[x -> Range[1, Length@x, 1]];
nf = Nearest[step0];
step1 = nf[#, y] & /@ x];


Running your three timing tests gives:

{0.003057, 0.004344, 0.051009}

• Is it possible to show the dynamics of the search process via a suitable graph? Commented Jun 19, 2015 at 6:57
• Thanks for your answer. I do not think it's possible to be faster with a simpler code. Commented Jun 19, 2015 at 8:44
• I suspect that it is almost always possible to find faster and simpler code! Commented Jun 19, 2015 at 9:27

Here's a way using Nearest a little differently, remembering Nearest's second argument can be a list...

KPosition[x_, y_] := With[{p = PositionIndex[x]},
Map[p[#][[1]] &, Nearest[x, x, y][[All, 2 ;;]], {2}]]


And my timings:

KPosition[Tst1, 8]; // AbsoluteTiming
KPosition[Tst2, 8]; // AbsoluteTiming
KPosition[Tst3, 8]; // AbsoluteTiming


{0.00255016, Null}

{0.0201945, Null}

{0.103676, Null}

• I'm seeing a ~3% speedup using WorkingPrecision -> MachinePrecision in Nearest[] in your implementation of KPosition[]. Varying Method and DistanceFunction had no oveservable improvement. (Octrees were substantially worse.) 3% may not be sufficient for the OP. Commented Jun 18, 2015 at 21:11

Edit: now including Michael E2's improvement.

Building on your own code and the existing answers this seems both cleaner and faster:

wizKP[x_List, n_] := Nearest[x -> Automatic, x, n]

• I will made new benchmarks soon... Commented Jun 19, 2015 at 10:28
• Actually, when I try to test your code I have the following error : " Nearest :: dmtch : The dimension of ... and ... does not match" Commented Jun 19, 2015 at 11:25
• @Doedalos A limitation of version 9 perhaps. Please tell me what you get from Nearest[Thread[x -> Range @ Length @ x], x, n] ? Commented Jun 19, 2015 at 11:36
• I have the same error. I think you're right about Mathematica 9. I see nothing in the documentation of version 9, which mentions the possibility of using a list in second position. This is not the case in the documentation of version 10. I think, it is time for me to change. Commented Jun 19, 2015 at 11:48
• Shouldn't Nearest[x -> Automatic, x, n] work? Commented Jun 20, 2015 at 3:58