9
$\begingroup$

Why does manually specifying the distance metric to Nearest slow down the calculation so much?

This is relevant to my previous question. I've been using Select to find sets of points close to a center point but I figured that an alternative (although uncompilable) solution might be to use Nearest with the ChessboardDistance.

However, I've found that if you specify the DistanceFunction to Nearest you tremendously slow down the calculation by orders of magnitude, with ChessboardDistance being the worst of the bunch by another order of magnitude. These results were observed in 1D, 2D and 3D with random data. I'm not sure what the effect, if any, of structured data would be.

Here is the example code for 3D points. I will give all the timings below. I've simply created a set of 1000 points and computed the NearestFunction and then computed closest point in the first set of 1000 points to each point in a second set of another 1000 points.

data1 = RandomReal[10, {10^3, 3}];
data2 = RandomReal[10, {10^3, 3}];

nf1 = Nearest[data1];
nf1 /@ data2; // AbsoluteTiming

nf2 = Nearest[data1, DistanceFunction -> EuclideanDistance];
nf2 /@ data2; // AbsoluteTiming

nf3 = Nearest[data1, DistanceFunction -> ManhattanDistance];
nf3 /@ data2; // AbsoluteTiming

nf4 = Nearest[data1, DistanceFunction -> ChessboardDistance];
nf4 /@ data2; // AbsoluteTiming

Here are the timings:

nf1 {0.0160009, Null}

nf2 {1.1730671, Null}

nf3 {1.1720671, Null}

nf4 {26.4165109, Null}

Very similar timings were found for 1D and 2D so I won't list all of them here.

The documentation says: If the elements are vectors or matrices of numbers, Nearest by default in effect uses the metric Norm[#1-#2]&.

So I tried to manually use Norm[#1-#2]& as the DistanceFunction.

nf5 = Nearest[data1, DistanceFunction -> (Norm[#1 - #2] &)];
nf5 /@ data2; // AbsoluteTiming

This is, surprisingly, even slower.

nf5 {3.9752274, Null}

I figured that maybe the default distance transform, even though it is given in the documentation, is compiled. Lets try that.

euclideandistanceC = 
  Compile[{{pt1, _Real, 1}, {pt2, _Real, 1}}, Norm[pt1 - pt2], 
   CompilationTarget -> "C", RuntimeAttributes -> {Listable}, 
   Parallelization -> True, RuntimeOptions -> "Speed"];

nf6 = Nearest[data, DistanceFunction -> euclideandistanceC];
nf6 /@ data2; // AbsoluteTiming

nf6 {0.8990514, Null}

Better but still slower. What's going on? Why is the default method so much faster, and most importantly, how can I use other distance metrics without a huge performance penalty?

Improve this question
$\endgroup$
  • $\begingroup$ Probably because the default algorithm uses properties of the default distance metric that arbitrary metrics do not have. So it can't use the same algorithm in the general case. Also, probably with the default settings it doesn't need to call back to the kernel to calculate the distance (as is the case with any custom metric). All of these are guesses, of course. $\endgroup$ – Szabolcs Dec 2 '12 at 21:10
  • $\begingroup$ Maybe this (actually: the links therein) will be an interesting read. $\endgroup$ – Szabolcs Dec 2 '12 at 21:22
  • 8
    $\begingroup$ In this case nearest simply has no code in place to use its fast octree approach with metrics other than Euclidean. This is, admittedly, a shame, because other l_n spaces could in principle be supported in the same way. In particular l_infinity (aka Chessboard) is quite amenable to that underlying technology. Just has not been implemented thus far. It's in our suggestions data base to do this, by the way (I put it there almost three years ago). $\endgroup$ – Daniel Lichtblau Dec 2 '12 at 21:31
  • $\begingroup$ If you feel up to rolling your own octree variant for a chessboard Nearest, some of the responses here might be of use. $\endgroup$ – Daniel Lichtblau Dec 2 '12 at 21:36
  • 1
    $\begingroup$ @Daniel please consider making that an answer! $\endgroup$ – Mr.Wizard Dec 3 '12 at 4:56
13
$\begingroup$

In this case Nearest simply has no code in place to use its fast octree approach with metrics other than Euclidean. This is, admittedly, a shame, because other $\ell_n$ spaces could in principle be supported in the same way. In particular $\ell_\infty$ (aka chessboard) is quite amenable to that underlying technology, but it just has not been implemented thus far. It is in our suggestions data base to do this, by the way (I put it there almost three years ago).

If you feel up to rolling your own octree variant for a chessboard Nearest, some of the responses here might be of use.

Improve this answer
$\endgroup$
  • $\begingroup$ Any chance for a better Nearest with more versatile distance function portability...in the next version? $\endgroup$ – PlatoManiac Jan 31 '14 at 2:08
  • $\begingroup$ Yes. Next release will recognize ManhattanDistance and ChessboardDistance and handle them with reasonable efficiency. (Strangely enough, I was putting the interface to those in place around the time you sent this query.) $\endgroup$ – Daniel Lichtblau Jan 31 '14 at 16:16
  • $\begingroup$ That's a strange coincidence indeed. Yesterday I was trying to use Nearest with mercator distance on a large ($>10^7$) set of geolocations. I compiled the distance function to C but without the octree code performance suffered badly. The default distance function was doing the similar sized job still extremely fast. It will be great if on the fly optimization similar to the default ones could be supported for user defined distance functions. After all we are waiting for a major release this time..the version number $10$ must be very special to everybody..Thx a lot for replying! $\endgroup$ – PlatoManiac Jan 31 '14 at 23:08
  • $\begingroup$ Something similar (geographic distance support) was, again coincidently, requested in-house today or maybe late yesterday. Problem with that is I do not know how to support it effectively in NearestFunction. $\endgroup$ – Daniel Lichtblau Feb 1 '14 at 0:06
  • $\begingroup$ In molecular dynamics and molecular simulations in general distances are usually based on the minimum image periodic boundary conditions. This distance is Euclidean in nature but with some modifications to account for the periodicity. Here is how such a distance can be implemented in Mathematica: f[x_,y_,boxLength_] := Sqrt[Plus @@ (((x - y) - boxLength Round[(x - y)/boxLength])^2)]. Is it possible to incorporate such a distance function in Nearest to speed it up? My attempt to use a compiled version of the above function with Nearest was 2 orders of magnitude slower than the default. $\endgroup$ – RunnyKine Jun 24 '15 at 5:40
5
$\begingroup$

This is usual in Mathematica: supplying comparison functions tends to slow things down, probably because of having to come up from the kernel to execute user-level code. Example:

lst = RandomReal[{-1, 1}, 100000];
AbsoluteTiming[Do[Sort[lst], {i, 10}];]
AbsoluteTiming[Do[Sort[lst, OrderedQ[{#1, #2}] &], {i, 10}];]

(*
{0.190045, Null}
{13.598207, Null}
*)
Improve this answer
$\endgroup$
2
$\begingroup$

Looks like @DanielLichtblau's speed improvements made it into M10:

data1=RandomReal[10,{10^3,3}];
data2=RandomReal[10,{10^3,3}];

nf1=Nearest[data1];
nf1/@data2;//AbsoluteTiming

nf2=Nearest[data1,DistanceFunction->EuclideanDistance];
nf2/@data2;//AbsoluteTiming

nf3=Nearest[data1,DistanceFunction->ManhattanDistance];
nf3/@data2;//AbsoluteTiming

nf4=Nearest[data1,DistanceFunction->ChessboardDistance];
nf4/@data2;//AbsoluteTiming

{0.001588, Null}

{0.001529, Null}

{0.00141, Null}

{0.001215, Null}

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.