# Manually specifying distance metric to Nearest slows down calculation

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 the 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?

-
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. –  Szabolcs Dec 2 '12 at 21:10
Maybe this (actually: the links therein) will be an interesting read. –  Szabolcs Dec 2 '12 at 21:22
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). –  Daniel Lichtblau Dec 2 '12 at 21:31
If you feel up to rolling your own octree variant for a chessboard Nearest, some of the responses here might be of use. –  Daniel Lichtblau Dec 2 '12 at 21:36
@Daniel please consider making that an answer! –  Mr.Wizard Dec 3 '12 at 4:56

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.

-
Any chance for a better Nearest with more versatile distance function portability...in the next version? –  PlatoManiac Jan 31 at 2:08
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.) –  Daniel Lichtblau Jan 31 at 16:16
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! –  PlatoManiac Jan 31 at 23:08
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. –  Daniel Lichtblau Feb 1 at 0:06

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}
*)

-