# What is complexity of Nearest Neigbor graph calculation and why kd/ball_tree works slower than brute?

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.

Observe a strange thing - "brute" works faster, than tree methods, if the dimension of the space is large enough:

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


PS

The motivation to ask comes from:

https://cstheory.stackexchange.com/questions/47034/number-of-connected-components-of-a-random-nearest-neighbor-graph/47039?noredirect=1#comment104468_47039