# 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[#][] &, 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? – thils Jun 19 '15 at 6:57
• Thanks for your answer. I do not think it's possible to be faster with a simpler code. – Doedalos Jun 19 '15 at 8:44
• I suspect that it is almost always possible to find faster and simpler code! – bill s Jun 19 '15 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[#][] &, 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. – Eric Towers Jun 18 '15 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... – Doedalos Jun 19 '15 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" – Doedalos Jun 19 '15 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] ? – Mr.Wizard Jun 19 '15 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. – Doedalos Jun 19 '15 at 11:48
• Shouldn't Nearest[x -> Automatic, x, n] work? – Michael E2 Jun 20 '15 at 3:58