do you have a tiny bench script to share?

do you have a tiny bench script to share?

No, I could create one if it would be useful

Here's a quick test:

from sklearn.datasets import make_blobs
from sklearn.neighbors import KDTree

import sklearn
print(sklearn.__version__)

X, y = make_blobs(n_samples=100000, n_features=3)

X1 = X[:50000]
X2 = X[50000:]

%timeit KDTree(X1).query(X2, 1)

Current release:

0.19.1
151 ms ± 1.66 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

On this branch:

0.20.dev0
136 ms ± 2.28 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Exploring a bit more... the interesting thing is that the use of the correct radius does not seem to appreciably impact the query time... as currently written, it ends up being essentially a proxy for number of points in the node.

We could probably explicitly rank query nodes by number of points rather than by radius and marginally improve both memory use (from not having to store each node's radius) as well as tree construction time (from not having to compute each node's radius), without an appreciable impact on query time in most cases... but that's probably for another PR.

from sklearn.datasets import make_blobs
from sklearn.neighbors import KDTree

import sklearn
print(sklearn.__version__)

X, y = make_blobs(n_samples=100000, n_features=3)

X1 = X[:50000]
X2 = X[50000:]

%timeit KDTree(X1)

tree = KDTree(X1)
%timeit tree.query(X2, 5)

0.19.1
32.4 ms ± 920 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
214 ms ± 14.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

0.20.dev0
14.9 ms ± 550 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
214 ms ± 3.28 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Appveyor had failed. I've restarted.

thx @jakevdp

@jnothman can you reastart appveyor here?

@jakevdp can you just add a what's new entry? thx

This PR is soon to be processed by appveyor, let's wait a bit.

can someone restart appveyor here?

rebased to restart CIs

Thanks a lot for this fix @jakevdp ! Appveyor passed, merging.

BTW, if you have an opinion on #11103 and #597 (comment) it would be very much appreciated.