Consider sklearn NearestNeighbors:
nbrs = NearestNeighbors(n_neighbors=2, algorithm=method ).fit(X) # 'ball_tree' distances, indices = nbrs.kneighbors(X)
There are several choices for 'algorithm' - ‘ball_tree’ will use BallTree ‘kd_tree’ will use KDTree ‘brute’ will use a brute-force search. ‘auto’ will attempt to decide the most appropriate algorithm based on the values passed to fit method.
Question 1 Is there any explanation why kd/ball tree work slower and why they are used as "auto" ? It seems like a bug in sklearn.
Let us look on the speed of kd_tree:
Question 2 what is the theoretical complexity of the kd_tree and ball_tree with respect to sample_size and dimension of the space ? (May be other things - the simulation is done for the uniformly sampled points [0,1]^d).
Remark: it is clear that for "brute" complexity grows quadratically with respect to sample size. As one can see from data above - kd_tree works quite linearly with respect to sample_size.
The code was running on colab.research.google.com
import time from sklearn.neighbors import NearestNeighbors import numpy as np import pandas as pd dim = 5 n_sample = 10**4 df_stat = pd.DataFrame() c = 0 t00 = time.time() for i in range(1): # repeat test several times for dim in [5,10,20]: for n_sample in [10**5]: X = np.random.rand(n_sample, dim) for method in ['brute','kd_tree','ball_tree','auto']: c += 1 df_stat.loc[c, 'Method'] = method df_stat.loc[c, 'Dim'] = dim df_stat.loc[c, 'N_sample'] = n_sample t0 = time.time() nbrs = NearestNeighbors(n_neighbors=2, algorithm=method ).fit(X) # 'ball_tree' distances, indices = nbrs.kneighbors(X) df_stat.loc[c, 'Time'] = time.time()-t0 if method == 'brute': indices_save = indices.copy() difr = indices_save - indices df_stat.loc[c, 'Coincide with Brute'] = (np.sum( np.abs(difr)) == 0) print(df_stat.tail(1)) df_stat
The motivation to ask comes from: