<h3 dir="auto">Description</h3>
<p dir="auto">Building a kd-Tree can be done in O(n(k+log(n)) time and should (to my knowledge) not depent on the details of the data. However, the KDTree implementation in scikit-learn shows a really poor scaling behavior for my data. I cannot produce this behavior with data generated by sklearn.datasets.samples_generator.make_blobs</p>
<h3 dir="auto">Steps/Code to Reproduce</h3>
<p dir="auto">download numpy data (search.npy) from <a href="https://webshare.mpie.de/index.php?6b4495f7e7" rel="nofollow">https://webshare.mpie.de/index.php?6b4495f7e7</a> and run the following code on python 3</p>
<div class="highlight highlight-source-python notranslate position-relative overflow-auto" dir="auto" data-snippet-clipboard-copy-content="import numpy as np
from sklearn.neighbors import NearestNeighbors
from sklearn.datasets.samples_generator import make_blobs
from scipy.spatial     import KDTree as KDTree_Scipy
from sklearn.neighbors import KDTree as KDTree_Sklearn
from time import sleep, perf_counter as pc

search_raw_artificial, dev_null = make_blobs(n_samples=6830160,n_features=5,centers=1000,cluster_std=0.4,random_state=0)
search_raw_real                 = np.load('search.npy')

N = [240000,2400000,4800000,6000000]

for search_raw in [search_raw_artificial,search_raw_real]:
  for i,n in enumerate(N):

    search = search_raw[0:n,:] 
    print('data shape',search.shape)
    print('delta',np.amax(search,0)-np.amin(search,0))
    t0 = pc()
    neigh = NearestNeighbors(algorithm='ball_tree').fit(search)
    print('sklearn.neighbors (ball_tree) build finished in {}s'.format(pc()-t0))
    t0 = pc()
    neigh = NearestNeighbors(algorithm='kd_tree').fit(search)
    print('  sklearn.neighbors (kd_tree) build finished in {}s'.format(pc()-t0))
    t0 = pc()
    neigh = KDTree_Sklearn(search)
    print('    sklearn.neighbors KD tree build finished in {}s'.format(pc()-t0))
    t0 = pc()
    neigh = KDTree_Scipy(search)
    print('    scipy.spatial     KD tree build finished in {}s'.format(pc()-t0))
    print('')"><pre class="notranslate"><span class="pl-k">import</span> <span class="pl-s1">numpy</span> <span class="pl-k">as</span> <span class="pl-s1">np</span>
<span class="pl-k">from</span> <span class="pl-s1">sklearn</span>.<span class="pl-s1">neighbors</span> <span class="pl-k">import</span> <span class="pl-v">NearestNeighbors</span>
<span class="pl-k">from</span> <span class="pl-s1">sklearn</span>.<span class="pl-s1">datasets</span>.<span class="pl-s1">samples_generator</span> <span class="pl-k">import</span> <span class="pl-s1">make_blobs</span>
<span class="pl-k">from</span> <span class="pl-s1">scipy</span>.<span class="pl-s1">spatial</span>     <span class="pl-k">import</span> <span class="pl-v">KDTree</span> <span class="pl-k">as</span> <span class="pl-v">KDTree_Scipy</span>
<span class="pl-k">from</span> <span class="pl-s1">sklearn</span>.<span class="pl-s1">neighbors</span> <span class="pl-k">import</span> <span class="pl-v">KDTree</span> <span class="pl-k">as</span> <span class="pl-v">KDTree_Sklearn</span>
<span class="pl-k">from</span> <span class="pl-s1">time</span> <span class="pl-k">import</span> <span class="pl-s1">sleep</span>, <span class="pl-s1">perf_counter</span> <span class="pl-k">as</span> <span class="pl-s1">pc</span>

<span class="pl-s1">search_raw_artificial</span>, <span class="pl-s1">dev_null</span> <span class="pl-c1">=</span> <span class="pl-en">make_blobs</span>(<span class="pl-s1">n_samples</span><span class="pl-c1">=</span><span class="pl-c1">6830160</span>,<span class="pl-s1">n_features</span><span class="pl-c1">=</span><span class="pl-c1">5</span>,<span class="pl-s1">centers</span><span class="pl-c1">=</span><span class="pl-c1">1000</span>,<span class="pl-s1">cluster_std</span><span class="pl-c1">=</span><span class="pl-c1">0.4</span>,<span class="pl-s1">random_state</span><span class="pl-c1">=</span><span class="pl-c1">0</span>)
<span class="pl-s1">search_raw_real</span>                 <span class="pl-c1">=</span> <span class="pl-s1">np</span>.<span class="pl-en">load</span>(<span class="pl-s">'search.npy'</span>)

<span class="pl-v">N</span> <span class="pl-c1">=</span> [<span class="pl-c1">240000</span>,<span class="pl-c1">2400000</span>,<span class="pl-c1">4800000</span>,<span class="pl-c1">6000000</span>]

<span class="pl-k">for</span> <span class="pl-s1">search_raw</span> <span class="pl-c1">in</span> [<span class="pl-s1">search_raw_artificial</span>,<span class="pl-s1">search_raw_real</span>]:
  <span class="pl-k">for</span> <span class="pl-s1">i</span>,<span class="pl-s1">n</span> <span class="pl-c1">in</span> <span class="pl-en">enumerate</span>(<span class="pl-v">N</span>):

    <span class="pl-s1">search</span> <span class="pl-c1">=</span> <span class="pl-s1">search_raw</span>[<span class="pl-c1">0</span>:<span class="pl-s1">n</span>,:] 
    <span class="pl-en">print</span>(<span class="pl-s">'data shape'</span>,<span class="pl-s1">search</span>.<span class="pl-s1">shape</span>)
    <span class="pl-en">print</span>(<span class="pl-s">'delta'</span>,<span class="pl-s1">np</span>.<span class="pl-en">amax</span>(<span class="pl-s1">search</span>,<span class="pl-c1">0</span>)<span class="pl-c1">-</span><span class="pl-s1">np</span>.<span class="pl-en">amin</span>(<span class="pl-s1">search</span>,<span class="pl-c1">0</span>))
    <span class="pl-s1">t0</span> <span class="pl-c1">=</span> <span class="pl-en">pc</span>()
    <span class="pl-s1">neigh</span> <span class="pl-c1">=</span> <span class="pl-v">NearestNeighbors</span>(<span class="pl-s1">algorithm</span><span class="pl-c1">=</span><span class="pl-s">'ball_tree'</span>).<span class="pl-en">fit</span>(<span class="pl-s1">search</span>)
    <span class="pl-en">print</span>(<span class="pl-s">'sklearn.neighbors (ball_tree) build finished in {}s'</span>.<span class="pl-en">format</span>(<span class="pl-en">pc</span>()<span class="pl-c1">-</span><span class="pl-s1">t0</span>))
    <span class="pl-s1">t0</span> <span class="pl-c1">=</span> <span class="pl-en">pc</span>()
    <span class="pl-s1">neigh</span> <span class="pl-c1">=</span> <span class="pl-v">NearestNeighbors</span>(<span class="pl-s1">algorithm</span><span class="pl-c1">=</span><span class="pl-s">'kd_tree'</span>).<span class="pl-en">fit</span>(<span class="pl-s1">search</span>)
    <span class="pl-en">print</span>(<span class="pl-s">'  sklearn.neighbors (kd_tree) build finished in {}s'</span>.<span class="pl-en">format</span>(<span class="pl-en">pc</span>()<span class="pl-c1">-</span><span class="pl-s1">t0</span>))
    <span class="pl-s1">t0</span> <span class="pl-c1">=</span> <span class="pl-en">pc</span>()
    <span class="pl-s1">neigh</span> <span class="pl-c1">=</span> <span class="pl-v">KDTree_Sklearn</span>(<span class="pl-s1">search</span>)
    <span class="pl-en">print</span>(<span class="pl-s">'    sklearn.neighbors KD tree build finished in {}s'</span>.<span class="pl-en">format</span>(<span class="pl-en">pc</span>()<span class="pl-c1">-</span><span class="pl-s1">t0</span>))
    <span class="pl-s1">t0</span> <span class="pl-c1">=</span> <span class="pl-en">pc</span>()
    <span class="pl-s1">neigh</span> <span class="pl-c1">=</span> <span class="pl-v">KDTree_Scipy</span>(<span class="pl-s1">search</span>)
    <span class="pl-en">print</span>(<span class="pl-s">'    scipy.spatial     KD tree build finished in {}s'</span>.<span class="pl-en">format</span>(<span class="pl-en">pc</span>()<span class="pl-c1">-</span><span class="pl-s1">t0</span>))
    <span class="pl-en">print</span>(<span class="pl-s">''</span>)</pre></div>
<h3 dir="auto">Expected Results</h3>
<p dir="auto">Time complexity scaling of scikit-learn KDTree should be similar to scaling of scipy.spatial KDTree</p>
<h3 dir="auto">Actual Results</h3>
<h4 dir="auto">Artificial Data, scikit-learn outperforms scipy.spatial</h4>
<p dir="auto">data shape (240000, 5)<br>
delta [ 22.7311549   22.61482157  22.57353059  22.65385101  22.77163478]<br>
sklearn.neighbors (ball_tree) build finished in 0.1524970519822091s<br>
sklearn.neighbors (kd_tree) build finished in 0.17296032601734623s<br>
sklearn.neighbors KD tree build finished in 0.172917598974891s<br>
scipy.spatial     KD tree build finished in 2.265735782973934s</p>
<p dir="auto">data shape (2400000, 5)<br>
delta [ 23.38025743  23.22174801  22.88042798  22.8831237   23.31696732]<br>
sklearn.neighbors (ball_tree) build finished in 3.462802237016149s<br>
sklearn.neighbors (kd_tree) build finished in 3.7110973289818503s<br>
sklearn.neighbors KD tree build finished in 3.5682168990024365s<br>
scipy.spatial     KD tree build finished in 19.92274082399672s</p>
<p dir="auto">data shape (4800000, 5)<br>
delta [ 23.38025743  23.26302877  23.22210673  22.97866792  23.31696732]<br>
sklearn.neighbors (ball_tree) build finished in 8.922708058031276s<br>
sklearn.neighbors (kd_tree) build finished in 9.238389031030238s<br>
sklearn.neighbors KD tree build finished in 8.879073369025718s<br>
scipy.spatial     KD tree build finished in 38.43681587401079s</p>
<p dir="auto">data shape (6000000, 5)<br>
delta [ 23.42236957  23.26302877  23.22210673  23.20207953  23.31696732]<br>
sklearn.neighbors (ball_tree) build finished in 12.75000820402056s<br>
sklearn.neighbors (kd_tree) build finished in 13.30022174998885s<br>
sklearn.neighbors KD tree build finished in 12.794657755992375s<br>
scipy.spatial     KD tree build finished in 48.33784791099606s</p>
<h4 dir="auto">My Data, scipy.spatial outperforms scikit-learn for increasing data size</h4>
<p dir="auto">data shape (240000, 5)<br>
delta [ 2.14487407  2.14472508  2.14499087  8.86612151  0.15491879]<br>
sklearn.neighbors (ball_tree) build finished in 0.39374090504134074s<br>
sklearn.neighbors (kd_tree) build finished in 0.21525143302278593s<br>
sklearn.neighbors KD tree build finished in 0.21449304796988145s<br>
scipy.spatial     KD tree build finished in 2.244567967019975s</p>
<p dir="auto">data shape (2400000, 5)<br>
delta [ 2.14502773  2.14502543  2.14502904  8.86612151  1.59685522]<br>
sklearn.neighbors (ball_tree) build finished in 4.199425678991247s<br>
sklearn.neighbors (kd_tree) build finished in 4.40237572795013s<br>
sklearn.neighbors KD tree build finished in 4.295626600971445s<br>
scipy.spatial     KD tree build finished in 26.322200270951726s</p>
<p dir="auto">data shape (4800000, 5)<br>
delta [ 2.14502773  2.14502864  2.14502904  8.86612151  3.19371044]<br>
sklearn.neighbors (ball_tree) build finished in 110.31694995303405s<br>
sklearn.neighbors (kd_tree) build finished in 112.8703724470106s<br>
sklearn.neighbors KD tree build finished in 114.07325625402154s<br>
scipy.spatial     KD tree build finished in 51.79352715797722s</p>
<p dir="auto">data shape (6000000, 5)<br>
delta [ 2.14502838  2.14502902  2.14502914  8.86612151  3.99213804]<br>
sklearn.neighbors (ball_tree) build finished in 2458.668528069975s<br>
sklearn.neighbors (kd_tree) build finished in 2451.2438263060176s<br>
sklearn.neighbors KD tree build finished in 2801.8054143560003s<br>
scipy.spatial     KD tree build finished in 62.066240190993994s</p>
<h4 dir="auto">Comments</h4>
<p dir="auto">cKDTree from scipy.spatial behaves even better<br>
I cannot use cKDTree/KDTree from scipy.spatial because calculating a sparse distance matrix (sparse_distance_matrix function) is extremely slow compared to neighbors.radius_neighbors_graph/neighbors.kneighbors_graph and I need a sparse distance matrix for DBSCAN on large datasets (n_samples &gt;10 mio) with low dimensionality (n_features = 5 or 6)</p>
<h3 dir="auto">Versions</h3>
<p dir="auto">Linux-4.7.6-1-ARCH-x86_64-with-arch<br>
Python 3.5.2 (default, Jun 28 2016, 08:46:01)  [GCC 6.1.1 20160602]<br>
NumPy 1.11.2<br>
SciPy 0.18.1<br>
Scikit-Learn 0.18</p>
<p dir="auto">I don't know if this is related to <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="125766835" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/6147" data-hovercard-type="issue" data-hovercard-url="/scikit-learn/scikit-learn/issues/6147/hovercard" href="https://github.com/scikit-learn/scikit-learn/issues/6147">#6147</a>. I am using "<em>The scikit-learn version is 0.18.dev0</em>" and I have no exception though, so this is different.</p>
<p dir="auto">In any case, this is my code (the data I am using is the same as the data for the Santander kaggle competition, too big to attach).</p>
<p dir="auto"><code class="notranslate">alg = XGBClassifier(max_depth=4, min_child_weight = 1, n_estimators=1000, learning_rate=0.0202,     gamma=0, nthread=4, subsample=0.6815, colsample_bytree=0.701, seed=1, silent=False)</code></p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="param_test1 = {
 'max_depth':range(3,10,2),
 'min_child_weight':range(1,10,2)
}

gsearch1 = GridSearchCV(estimator = alg, param_grid = param_test1, scoring='roc_auc', iid=False, n_jobs=4, cv=5)
gsearch1.fit(train_data[predictors].as_matrix(),train_data[target].as_matrix())"><pre class="notranslate"><code class="notranslate">param_test1 = {
 'max_depth':range(3,10,2),
 'min_child_weight':range(1,10,2)
}

gsearch1 = GridSearchCV(estimator = alg, param_grid = param_test1, scoring='roc_auc', iid=False, n_jobs=4, cv=5)
gsearch1.fit(train_data[predictors].as_matrix(),train_data[target].as_matrix())
</code></pre></div>
<p dir="auto">The program will not crash, will not throw an exception, but will not do anything (activity monitor shows no activity). Quick debugging shows the program enters <code class="notranslate">_fit</code> in <code class="notranslate">grid_search.py</code> but never reaches line 564. I did not debug further. A quick search brought me to issue <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="125766835" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/6147" data-hovercard-type="issue" data-hovercard-url="/scikit-learn/scikit-learn/issues/6147/hovercard" href="https://github.com/scikit-learn/scikit-learn/issues/6147">#6147</a> and tried removing the <code class="notranslate">n_jobs</code>variable.</p>
<p dir="auto">Removing<code class="notranslate">n_jobs</code> from the <code class="notranslate">GridSearchCV</code> call solves the issue.</p>