How scikit-learn KNN chooses brute force, KDTree, or BallTree

Start here

This page alternates short explanations with practice that checks your answers. Each practice set finishes when you answer two questions in a row correctly; a wrong answer shows what usually causes it and where to reread. After sections 4, 7, 10, and 11a, a checkpoint quiz mixes everything so far. Answer the quizzes from memory, without scrolling back: recalling is what makes the material stay.

If you already know some of this material, the eight questions below tell you where to start. Leave a question blank if you do not know the answer.

1The decision we want to explain

We use eight training rows with two features, x₁ and x₂. Our query point is q = (0.2, 0.1). We want its k = 3 nearest rows.

Fit the classifier twice. The only change between the two fits is n_neighbors.

import numpy as np
from sklearn.neighbors import KNeighborsClassifier

X = np.array([[0, 0], [0, 1], [1, 0], [1, 1], [10, 10], [10, 11], [11, 10], [11, 11]], dtype=float)
y = np.array(["A", "A", "A", "A", "B", "B", "B", "B"])

model_k3 = KNeighborsClassifier(n_neighbors=3).fit(X, y)
model_k4 = KNeighborsClassifier(n_neighbors=4).fit(X, y)

print(model_k3._fit_method)  # kd_tree
print(model_k4._fit_method)  # brute
assert model_k3._fit_method == "kd_tree"
assert model_k4._fit_method == "brute"

The attribute _fit_method stores the search method. The search method is the procedure that kneighbors(), and so predict(), uses to find the nearest training rows. It has three possible values: "brute", "kd_tree", and "ball_tree". You can choose one with the algorithm parameter. The default, algorithm="auto", tells fit() to choose with a fixed list of rules. Those rules are in NeighborsBase._fit, at lines 777–836.

One caution about this small example: with the default leaf_size=30, eight rows give a KD tree with a single leaf, so this kd_tree still measures all eight distances. Section 5 draws the tree that scikit-learn builds with leaf_size=1, the smallest setting where a search can skip rows, and section 7 shows why.

Changing k from 3 to 4 changed the search method. This lesson explains that rule and every other rule in the list. Each rule protects one of two requirements:

1. Correctness. The search must return the true k nearest rows. A tree search returns wrong rows when its distance does not have certain properties.
2. Speed. The search method should do less work than the alternatives. A tree saves work only for some data shapes and some values of k.

The auto rules are in two groups, and this lesson calls them gates. Gate 1 contains three conditions. If any one of them is true, the result is brute force, because a tree is not expected to save work. Gate 2 runs only when Gate 1 lets a tree through. It contains five rules, tested in order, that choose a tree whose search is correct for the metric, or brute force when no such tree exists. A separate safety check runs after both gates.

To understand the rules, we need four ideas, in this order:

• how scikit-learn calculates a distance (section 2);
• which distances obey the rules of a true distance (section 3);
• what brute force costs (section 4);
• how a tree skips work (sections 5 and 6);
• how scikit-learn builds and searches both trees from the raw rows (section 7).

Sections 8 and 9 then use these ideas to explain each rule. Section 10 reads the code.

2Measure distance with the Minkowski family

Take the query q = (0.2, 0.1) and row 2, which is (1, 0). The difference in each feature is:

• feature 1: |0.2 − 1| = 0.8;
• feature 2: |0.1 − 0| = 0.1.

There are several useful ways to combine these two differences into one distance:

Manhattan distance is the length of a path that moves only parallel to the feature axes. Euclidean distance is the length of the straight line between the two points. Chebyshev distance counts only the feature with the largest difference.

All three combinations are cases of one formula with a parameter p. Here, D is the number of features and j numbers the features from 1 to D:

Read the formula from the inside out. For each feature, raise the absolute difference to the power p. Add the results. Then raise the sum to the power 1/p.

• With p = 1: (0.8 + 0.1)¹ = 0.9. This is Manhattan distance.
• With p = 2: (0.64 + 0.01)^1/2 = 0.806. This is Euclidean distance.
• With p = 3: (0.512 + 0.001)^1/3 = 0.513^1/3 = 0.8005.

As p increases, the largest difference has more effect on the result. In the limit p → ∞, only the largest difference remains, so the result is the Chebyshev distance, 0.8. This family of distances is called the Minkowski distance. The scikit-learn default is metric="minkowski", p=2, which is Euclidean distance.

Weighted Minkowski distance. You can pass a weight for each feature with metric_params={"w": w}. The formula then multiplies each feature's term by its weight before the sum:

A small weight makes a feature count less. A weight of 0 makes scikit-learn ignore the feature.

Where the weights go. Feature weights have no parameter of their own. They belong to the distance function, so you pass them inside metric_params, which hands extra arguments to whichever metric you chose. The default metric is already Minkowski, so this call is enough:

KNeighborsClassifier(n_neighbors=3, metric_params={"w": [100, 1]})

w needs one number for each feature. Do not confuse it with the parameter weights, which has a similar name and does a different job:

Here is the effect of w on the eight rows, with the query (0.4, 0.3) and k = 3. The weight [100, 1] makes a gap in feature 1 very costly. So row 1, which is (0, 1), moves ahead of row 2, which is (1, 0), because row 1 is closer to the query in feature 1. The search method also changes, for a reason that section 8 explains.

How fit renames the metric

Before the selection rules run, fit() calculates effective_metric_ (lines 699–718). This step replaces a Minkowski metric with a specialized name when one exists. A specialized name lets later code use a faster implementation of the same formula.

The rename happens only when w is None. The code tests whether a weight array exists. It does not test whether the weights change the result. So the selection rules in section 10 see effective_metric_ == "minkowski" only for an unusual p or when you give weights.

import numpy as np
from sklearn.metrics import DistanceMetric

q = np.array([0.2, 0.1])
row_2 = np.array([1.0, 0.0])

def minkowski(a, b, p):
    """Return the Minkowski distance of order p between two 1-D arrays."""
    return float(np.sum(np.abs(a - b) ** p) ** (1 / p))

assert np.isclose(minkowski(q, row_2, 1), 0.9)
assert np.isclose(minkowski(q, row_2, 2), np.sqrt(0.65))
assert np.isclose(minkowski(q, row_2, 3), 0.513 ** (1 / 3))
assert np.isclose(np.max(np.abs(q - row_2)), 0.8)

# scikit-learn's weighted Minkowski multiplies each term by its weight.
w = np.array([0.01, 0.01])
weighted = DistanceMetric.get_metric("minkowski", p=2, w=w).pairwise([q], [row_2])[0, 0]
assert np.isclose(weighted, np.sqrt(0.01 * 0.8**2 + 0.01 * 0.1**2))
print("Minkowski checks passed")

3The four rules of a true distance

A distance function d(a, b) is a metric, or true distance, when it obeys four rules for all points a, b, and c:

1. Rule 1Zero for the same pointd(a, a) = 0
2. Rule 2Positive for different pointsif a ≠ b, then d(a, b) > 0
3. Rule 3Symmetryd(a, b) = d(b, a)
4. Rule 4Triangle inequalityd(a, c) ≤ d(a, b) + d(b, c)

Rule 4 needs the most attention. Test it with Euclidean distance and three points from our example. Let a = q = (0.2, 0.1), b = row 0 = (0, 0), and c = row 2 = (1, 0).

• Direct distance: d(q, row 2) = 0.806.
• First part of the detour: d(q, row 0) = √(0.2² + 0.1²) = √0.05 = 0.224.
• Second part of the detour: d(row 0, row 2) = 1.

The direct distance, 0.806, is not larger than the detour, 0.224 + 1 = 1.224. So rule 4 holds for these three points. In words, rule 4 says that a detour through a third point is never shorter than the direct path.

Every Minkowski distance with p ≥ 1 obeys all four rules. The proof of rule 4 for these distances is called the Minkowski inequality. Section 6 uses rule 4 to build the ball-tree lower bound. So a distance that breaks rule 4 makes that bound wrong.

Two distances that break rule 4

Minkowski distance with p = 0.5. Let a = (0, 0), b = (0, 1), and c = (1, 1).

• d(a, b) = (0^0.5 + 1^0.5)² = 1.
• d(b, c) = (1^0.5 + 0^0.5)² = 1.
• d(a, c) = (1^0.5 + 1^0.5)² = 2² = 4.

The direct distance is 4, but the detour is 1 + 1 = 2. The detour is shorter, so rule 4 fails. The cause is the final power. When p < 1, the final power 1/p is greater than 1. That power makes the combined distance of two differences larger than the two separate distances added together.

Cosine distance. Cosine distance is 1 − cos θ, where θ is the angle between two vectors. It measures only the difference in direction. Let A = (1, 0), B = (1, 1), and C = (0, 1).

• A and C are 90° apart, so d(A, C) = 1 − 0 = 1.
• A and B are 45° apart, so d(A, B) = 1 − 0.7071 = 0.293.
• B and C are also 45° apart, so d(B, C) = 0.293.

The detour is 0.293 + 0.293 = 0.586, which is shorter than the direct distance, 1. So rule 4 fails. Cosine distance also breaks rule 2. The points (1, 0) and (2, 0) are different, but they have the same direction, so their cosine distance is 0.

True distances that are not Minkowski distances

scikit-learn supports some true distances that do not belong to the Minkowski family. Two of them appear in later sections:

• Haversine distance is the distance along the surface of a sphere, from latitude and longitude in radians. Its formula multiplies the longitude difference by the cosines of both latitudes. So the same longitude difference gives a smaller distance near the poles.
• Mahalanobis distance is the Euclidean distance after a linear transformation of the features, given by a matrix VI. The transformation combines features, so a difference in one feature changes the effect of a difference in another feature.

These two distances obey all four rules. But neither one is a sum of separate terms, one term for each feature. Section 6 shows why that difference matters for the KD tree.

You can also pass a Python function as the metric. scikit-learn calls such a function a callable metric. scikit-learn cannot check the four rules for your function, so it assumes that the function obeys them.

import numpy as np

def minkowski(a, b, p):
    """Return the Minkowski distance of order p between two 1-D arrays."""
    return float(np.sum(np.abs(np.subtract(a, b)) ** p) ** (1 / p))

def cosine_distance(u, v):
    """Return 1 minus the cosine of the angle between vectors u and v."""
    return float(1 - np.dot(u, v) / (np.linalg.norm(u) * np.linalg.norm(v)))

q, row_0, row_2 = [0.2, 0.1], [0, 0], [1, 0]
assert minkowski(q, row_2, 2) <= minkowski(q, row_0, 2) + minkowski(row_0, row_2, 2)

a, b, c = [0, 0], [0, 1], [1, 1]
assert np.isclose(minkowski(a, c, 0.5), 4.0)
assert np.isclose(minkowski(a, b, 0.5) + minkowski(b, c, 0.5), 2.0)

A, B, C = np.array([1.0, 0.0]), np.array([1.0, 1.0]), np.array([0.0, 1.0])
assert cosine_distance(A, C) > cosine_distance(A, B) + cosine_distance(B, C)
assert np.isclose(cosine_distance(A, 2 * A), 0.0)
print("Metric-rule checks passed")

4Brute force calculates every distance

Brute force is the direct method. For one query, it calculates the distance to each of the N training rows. Then it keeps the k smallest distances. Here are the Euclidean distances from q = (0.2, 0.1) to all eight rows. The bar in each row is the distance drawn to one scale, and the three highlighted rows are the nearest:

The three nearest rows are rows 0, 2, and 1. All three have class A, so the prediction is A.

Work. One Euclidean distance needs D subtractions, D squares, and D − 1 additions. So one query needs about N · D arithmetic steps, plus the selection of the k smallest values. Here, that is 8 × 2 = 16 subtractions. This cost does not change with the positions of the rows, and it changes little with k. Brute force also needs no work in fit(). The code only sets self._tree = None (lines 862–863).

Why brute force can still be fast

Brute force calculates every distance, so its speed depends on the cost of one distance. scikit-learn does not calculate the squared Euclidean distance in the direct way. It rewrites the distance with algebra, so that almost all of the work becomes one matrix multiplication. This subsection derives the rewrite from row 2, then shows why it is faster, and then shows its one disadvantage.

Step 1Calculate the distance in the direct way

The table above uses the direct method: subtract, square, and add. For row 2, x = (1, 0) and q = (0.2, 0.1):

The direct method subtracts first. The difference q − x is different for each pair of a query and a row, so the method must handle every pair separately.

Step 2Expand one coordinate

For one coordinate, ordinary algebra gives:

Check the identity with coordinate 1 of row 2, where a = 0.2 and b = 1. The left side is (0.2 − 1)² = 0.64. The right side is 0.04 + 1 − 0.4 = 0.64. The two sides are equal.

Step 3Add the coordinates

The squared distance is the sum of the squared differences of all coordinates. Apply the identity from step 2 to each coordinate. Then add each type of term separately, column by column. Each colored column below becomes one colored term of the formula:

Each table row obeys the identity from step 2: 0.04 + 1 − 0.4 = 0.64, and 0.01 + 0 − 0 = 0.01. So the column sums also obey it. The three column sums on the right have names:

• ‖q‖² = Σ_j q_j² = 0.05 is the squared length of the query. It depends only on the query.
• ‖x‖² = Σ_j x_j² = 1 is the squared length of the training row. It depends only on the row.
• q · x = Σ_j q_j x_j = 0.2 is the dot product of the query and the row. It is the only term that depends on both points. The last column holds −2 q · x = −0.4.

Together, the three sums give the expanded formula:

This is the same 0.65 as in step 1.

Step 4Apply the formula to all rows at the same time

For one pair of points, the expanded formula needs more operations than the direct method. The advantage appears when there are many pairs. This table applies the formula to the query and all eight rows:

The last column is equal to the squared-distance column of the first table. Each of the other columns has a different cost:

• The ‖q‖² column contains one number, repeated for each row. It is calculated once for each query.
• The ‖x‖² column depends only on the training rows. It is calculated once for each call to kneighbors, and then it is used for every query in that call.
• The q · x column is the only part that needs each pair. For M queries and N rows, all M × N dot products form one matrix product, QX^⊤. Here, Q is the M × D matrix of queries, and X is the N × D matrix of training rows.

So the full M × N matrix of squared distances is:

NumPy adds the M × 1 column to each column of the matrix, and it adds the 1 × N row to each row of the matrix. This addition is called broadcasting.

Step 5Why one matrix multiplication is fast

The speed of this calculation depends more on memory than on arithmetic. The processor can multiply numbers much faster than main memory (RAM) can deliver them. So the fastest method is the one that does the most multiplications with each number that it loads.

A loop that handles one pair at a time loads one query row and one training row, which is 2 × D numbers. It multiplies the two rows coordinate by coordinate, adds the products, and moves to the next pair. So each loaded number takes part in only one multiplication.

Matrix multiplication in NumPy runs in BLAS (Basic Linear Algebra Subprograms). BLAS is a standard library of optimized routines for vector and matrix operations. BLAS splits the matrices into blocks that fit in the cache, a small and fast memory next to the processor. Then it calculates every dot product inside a block before it loads the next block. Figure 4.2 shows the difference with D = 100 and an example block of 64 rows from each matrix.

The direct method cannot use this routine. BLAS calculates sums of products, q₁x₁ + q₂x₂ + …. The direct method calculates sums of squared differences, (q₁ − x₁)² + (q₂ − x₂)² + …, and no BLAS routine subtracts before it multiplies. The expansion in step 3 moves the subtraction outside the sum. So the only expensive part that remains, QX^⊤, is a plain sum of products.

A vectorized direct method also needs much more memory. To avoid a Python loop, NumPy must first store every difference, which is an array of shape (M, N, D). The expanded method needs only the M × N result, two short lists of squared lengths, and the input matrices.

scikit-learn uses the expansion in two places:

• _euclidean_distances (lines 15052–15103) calculates the squared lengths with row_norms (lines 15065 and 15075). Then it calculates -2 * safe_sparse_dot(X, Y.T) and adds the two lists of squared lengths (lines 15085–15087).
• For the Euclidean metric, the brute-force search for neighbors uses EuclideanArgKmin (line 8440). It calculates the squared lengths of the training rows once per search (lines 8496–8499). Then it calculates the −2 QX^⊤ term chunk by chunk, with a helper that the code calls the "middle term" (lines 8478–8486). It keeps only the k smallest distances of each chunk, so it never stores the full M × N matrix.

CostThe disadvantage: rounding error for close points

The expansion has one numerical problem. Suppose that q and x are far from the origin but close to each other. Then ‖q‖² + ‖x‖² and 2 q · x are two large numbers that are almost equal. A computer stores each number with about 16 significant digits. The subtraction cancels the leading digits, and the result contains mostly rounding error. The direct method does not have this problem, because it subtracts the coordinates first, while the numbers are still small.

For example, let q = (100000, 100000) and x = (100000.001, 100000.001). The true squared distance is 0.000002. Each squared length is about 2 × 10¹⁰. The rounding error at that size is about 0.000004, which is larger than the true answer. In float64, the expanded formula gives exactly 0.

The rounding error can also make the result a small negative number. The square root of a negative number is nan. So scikit-learn changes each negative result to 0 (lines 15089–15092). When it calculates the distances from a matrix to itself, it also sets the diagonal to exactly 0 (lines 15096–15097). These two fixes prevent nan values and wrong self-distances. They do not restore the lost accuracy. For KNN, the consequence is small: when two training rows are almost equally close to a query, they can change rank.

ResultBrute force is cheap per distance

For Euclidean distance, brute force calculates every distance, but each distance is cheap, because BLAS calculates the shared part for all pairs together. A tree must skip enough distances to repay its extra work at each step. This shortcut exists only for Euclidean distance, and the subsections below show what brute force does for other metrics. Section 9 measures how much of brute force's lead comes from BLAS and how much comes from a tree that can no longer skip rows.

import numpy as np

X = np.array([[0, 0], [0, 1], [1, 0], [1, 1], [10, 10], [10, 11], [11, 10], [11, 11]], dtype=float)
q = np.array([0.2, 0.1])

# Direct calculation: subtract, square, add.
direct_squared = ((X - q) ** 2).sum(axis=1)

# Expanded calculation: one squared length for the query, one squared length
# for each row, and the dot products. The X @ q term is the part that BLAS calculates.
query_squared_length = q @ q
row_squared_lengths = (X ** 2).sum(axis=1)
dot_products = X @ q
expanded_squared = query_squared_length + row_squared_lengths - 2 * dot_products

assert np.isclose(query_squared_length, 0.05)
assert np.allclose(row_squared_lengths, [0, 1, 1, 2, 200, 221, 221, 242])
assert np.allclose(dot_products, [0, 0.1, 0.2, 0.3, 3.0, 3.1, 3.2, 3.3])
assert np.allclose(direct_squared, expanded_squared)

nearest_three = np.argsort(direct_squared)[:3]
assert nearest_three.tolist() == [0, 2, 1]
print(np.round(np.sqrt(direct_squared), 3), nearest_three)

# Rounding error: two points that are close to each other but far from the origin.
far_query = np.array([100000.0, 100000.0])
far_row = far_query + 0.001
far_direct = ((far_query - far_row) ** 2).sum()
far_expanded = far_query @ far_query + far_row @ far_row - 2 * (far_query @ far_row)
assert np.isclose(far_direct, 0.000002)
assert abs(far_expanded - far_direct) > 0.5 * far_direct
print(far_direct, far_expanded)

Line up the shapes: broadcasting, worked through

The expanded formula describes one training row and one query. The code must apply it to every pair. With n training rows and m queries, the three parts have these shapes when X comes first in the product:

Every cell of the grid needs one ‖x‖² and one ‖q‖². Across a row, ‖x‖² stays the same, because the training row is the same. Down a column, ‖q‖² stays the same, because the query is the same. So each stored number must be reused in several cells, and broadcasting is the NumPy rule that does this reuse.

NumPy compares shapes from the right, and a dimension of size 1 stretches to match. Adding the two flat lists directly does not say which way to stretch. It adds them position by position, so training row 0 meets query 0, and training row 1 meets query 1. Indexing with None adds a dimension of size 1, and that fixes the direction:

distances_squared = X_squared[:, None] + query_squared[None, :] - 2 * X @ query.T
#                   (n, 1)               (1, m)                   (n, m)

The flat version does not fail in a helpful way. With eight training rows, its result depends on the number of queries:

Each cell of the grid combines one training row and one query. Here is the bottom-left cell of Fig. 4.5:

1. Read the squared lengths. The training row (3, 4) has ‖x‖² = 25, and the query (1, 1) has ‖q‖² = 2.
2. Compute the product term. x · q = 3 + 4 = 7, so −2 x · q = −14.
3. Add the three parts. 25 + 2 − 14 = 13, which equals (3 − 1)² + (4 − 1)².

Getting ‖x‖²: the names, and four ways to compute it

scikit-learn's main Euclidean path uses two BLAS routines. Their names are abbreviations:

The source calls the second one _gemm, which covers the double-precision and the single-precision versions. NumPy's @ also passes float matrices to this routine. In the installed scikit-learn 1.8.0, the row loop is in metrics/_pairwise_distances_reduction/_base.pyx.tp:41, the matrix product is in _middle_term_computer.pyx.tp:440, and _argkmin.pyx.tp:494-498 adds the three terms for each pair. When that path does not apply, row_norms uses np.einsum instead (utils/extmath.py:89).

Why XX^⊤ is not the answer. Entry (i, j) of XX^⊤ is row i dotted with row j, so the matrix holds every pair of rows. Only its diagonal holds the squared lengths:

X = [[1, 2],        X @ X.T = [[ 5, 11, 17],      np.diag(X @ X.T) = [5, 25, 61]
     [3, 4],                   [11, 25, 39],
     [5, 6]]                   [17, 39, 61]]

The 25 is row 1 with itself, 3² + 4². The 11 is row 0 with row 1, 1·3 + 2·4, which is not a sum of squares.

What einsum means. The name comes from Einstein summation. You write a recipe for how the indices combine, and any index that is missing from the output is summed away:

np.einsum('ij,ij->i', X, X)
# ij,ij  take X[i, j] from both inputs and multiply them, so each value is squared.
# ->i    keep the row index. The column index j is missing, so columns are summed.

Here are all the options on 5,000 rows and 20 features. Each one gives the same values:

The product is the slowest option even though it runs on BLAS, because it answers a bigger question. It works out 25 million pairs and needs 200 MB to store them, when you need only 5,000 numbers. The gap grows with the data. Each doubling of the rows roughly doubles the time of einsum, and roughly quadruples the time of the full grid:

So the choice depends on what you need. One number per row means einsum, and every query against every row means @. BLAS has no routine for "dot each row with itself": ddot on two whole arrays returns one total, so per-row values need a loop around it.

Compiled and interpreted loops

The ddot loop above loses to einsum even though ddot is fast. It spends about 140 nanoseconds per row, while einsum spends about 4 nanoseconds per row on everything. Most of the 140 nanoseconds is Python fetching each row and making each call. To see why, separate two kinds of code:

• Interpreted Python. Python translates your source into bytecode, a list of general instructions. Then a program called the interpreter reads these instructions one at a time while your code runs. The instruction for * does not say which multiplication to run, because the type of the values is not fixed until the line runs. The same line works on integers, floats, and arrays, and raises TypeError on two strings. So the interpreter makes that choice again on every pass through the loop.
• Compiled code. A compiler translated the loop into machine instructions before the program ran, with the type fixed as a 64-bit float. So each pass goes straight to the arithmetic. scikit-learn's Cython loops are compiled when the package is built, and NumPy's einsum and .sum are compiled C. You call them from Python, but their loops do not run in Python.

The same function shows the difference when it runs both ways. Numba compiles a Python function to machine code when the types are known:

That is about 600 times faster, for three reasons. The compiled loop makes no type decision on each pass. It works on raw 8-byte numbers that sit side by side in memory, where interpreted Python creates a new float object of 24 bytes for each result. And with a known type and neighboring values, it can use the processor's vector instructions, which handle several numbers in one step.

einsum does not use BLAS. Limiting BLAS to one thread shows this, on 200,000 rows and 20 features. The product slows down and einsum does not change beyond measurement noise:

Storing less explains only the smaller part of its speed. (X**2).sum(axis=1) builds a whole temporary matrix and then reads it back, while einsum keeps one running total per row, and this gives its lead of about 3 times. The much larger lead over plain Python is not about storage, because a plain Python loop stores no extra matrix either. That lead comes from being compiled.

When scikit-learn computes ‖x‖²

fit could compute ‖x‖², because the value needs only the training rows. It does not. For brute force, fit stores the rows and nothing else. Each kneighbors call computes ‖x‖² again and uses it for all the queries in that call (_argkmin.pyx.tp:360-371 in the installed source). So "once" in the table above means once per call. No attribute keeps it for the next call.

The cost of this choice depends on how many queries arrive in one call. On 200,000 rows and 20 features:

So recomputing costs little for batches and more for one query at a time. Your own class may store ‖x‖² in fit, at the cost of one array of n numbers. Both choices give the same distances. The source does not state a reason for scikit-learn's choice.

Each entry of X @ X.T pairs two rows, and only the diagonal pairs a row with itself. With X = [[1, 2], [3, 4], [5, 6]] from the example above:

1. Read an entry. Entry (i, j) is row i dotted with row j.
2. Off the diagonal. Entry (0, 1) is 1 · 3 + 2 · 4 = 11, two different rows.
3. On the diagonal. Entry (1, 1) is 3² + 4² = 25, the squared length of row 1.

Brute force for every other metric

The expansion depends on squaring, which splits one difference into three separate pieces. For p = 1 or 3, the distance contains |q − x|, and the sign inside it depends on which value is larger. So the term does not split into a part for q, a part for x, and a plain product. The check in the source is if metric in ("euclidean", "sqeuclidean") (_argkmin.pyx.tp:62). The default minkowski reaches it because fit renames p = 2 without weights to euclidean (section 2).

Every other metric uses a compiled double loop over the pairs. It does not call BLAS. The structure is:

for each query i:                               # _argkmin.pyx.tp:161
    for each training row j:                    # _argkmin.pyx.tp:162
        d = 0
        for each column c:                      # inside the metric's rdist
            d += pow(fabs(q[i, c] - x[j, c]), p)
        push d onto the heap of query i         # _argkmin.pyx.tp:163-167

The column loop depends on the metric. All three lines are in metrics/_dist_metrics.pyx.tp. For the example, take q = (1, 1) and x = (3, 5), so the gaps are 2 and 4:

During the search, the loop compares 72 and skips the final root, because the root does not change which rows are nearest. Only the reported distances get the root. This is the reduced distance from section 7.

A power is not a repeated dot product. A difference dotted with itself gives Σ gap², which is p = 2 only. A dot product multiplies and adds in one step, so it cannot cube each gap before it adds. BLAS has no routine that raises each value to a power, and p can also be a value such as 1.5, which is not repeated multiplication.

So the cost of brute force changes a lot between metrics. Here are 100 queries against 100,000 rows with 20 features:

The last row is a choice by scikit-learn, not a limit of the mathematics. A weighted p = 2 distance expands in the same way. But anything with w takes the general path, so it costs about 75 times more than plain p = 2 here.

Memory in NumPy. Your own NumPy version needs the gaps of each column, which the Euclidean shortcut never needed. If it stores them all at once, the array has shape (n, m, D). For 100 queries, 100,000 rows, and 20 columns, that is 200 million values, or 1.6 GB. Looping over the queries holds one query's gaps at a time and avoids this array.

Each metric combines the same gaps in its own way. With q = (1, 1) and x = (3, 5):

1. Find the gaps. 2 and 4.
2. Combine them. Manhattan adds them, 2 + 4 = 6. p = 3 cubes and adds them, 8 + 64 = 72. Chebyshev keeps the largest, 4.
3. Take the root only for the report. The search compares 72, and the reported p = 3 distance is 72^1/3 = 4.16.

Keep the k smallest distances

scikit-learn's compiled loop keeps one max-heap for each query (section 7 explains the heap), because it receives one distance at a time. In NumPy, all the distances already sit in one array, so a Python heap has the same problem as the ddot loop. On 1 million distances with k = 5, all of these found the same five values:

np.argpartition moves the k smallest to the front in no particular order, using the same idea as the median split in section 7. So it needs one more sort of those k values when the order matters. scikit-learn's own fallback path does exactly this (neighbors/_base.py:743-746).

Checkpoint quiz

Closed-book: answer from memory, without scrolling back. The questions mix sections 2 to 4; a missed question links to the part to review, and you can retake the quiz.

5Skip a group of rows with a lower bound

We want the same answer as brute force, but without calculating the distances to rows 4–7. The difficulty is that we cannot know a row's distance without calculating it. But the table in section 1 gives a hint. All four rows have both coordinates between 10 and 11, and q is near (0, 0). A short description of the group could prove that all four rows are far away.

The current k-th best distance

Suppose that we calculated the distances to rows 0–3 first. The three best rows so far are row 0 (0.224), row 2 (0.806), and row 1 (0.922). We call these three rows the candidates. The largest candidate distance is 0.922. We call it the current k-th best distance and write it as t. A new row can replace a candidate only if its distance is smaller than t.

A lower bound for a group

Now suppose that we have a number L for the group of rows 4–7, with this guarantee: every row in the group is at least L away from q. Such a number is a lower bound for the group. Section 6 calculates L = 13.93 for this group.

Compare L with t. Because 13.93 > 0.922, every row in the group is farther than every candidate. No row in the group can replace a candidate, so the search can skip the group. We get the same three rows with four fewer distance calculations.

This method works only when two conditions are true:

1. The lower bound must be correct. L must never be larger than the true distance of any row in the group. If L is too large, the search can skip a group that contains a true neighbor. The result is wrong, and no error occurs.
2. The lower bound must be useful. L must often be larger than t. If L ≤ t for most groups, the search skips few rows. It then pays for the lower bounds and for the distances.

Section 8 explains the rules that protect condition 1. Section 9 explains the rules that protect condition 2.

From one group to a search tree

A search tree applies the grouping idea repeatedly. The first group, called the root, contains all rows. The tree divides it into two child groups, and then it divides each child again. Each group is a node, and a node without children is a leaf. Each node stores a short summary that gives a lower bound for its rows.

scikit-learn sets the depth before it builds anything. It computes the number of levels from the number of rows and leaf_size (default 30), so that every leaf holds between leaf_size and 2 × leaf_size rows. When there are fewer rows than leaf_size, the whole tree is one leaf. Section 7 works this rule out for our eight rows.

A search starts at the root. It visits the more promising child first, and it calculates the distances for the rows in each leaf that it visits. It skips any node whose lower bound is larger than t. Step through the search for our query in Figure 5.2.

A KD tree and a ball tree use the same search. They differ only in the summary that each node stores, and so in how each node calculates L.

6Summarize a group with a box or a ball

Section 5 needs a lower bound L for each group of rows. The tree cannot calculate L from the rows themselves, because that would mean calculating every distance in the group, which is the work we want to skip. So each node stores a short summary of its rows, and the search calculates L from the summary alone. A KD tree summarizes a group with a box, and a ball tree summarizes it with a ball. This section calculates both bounds for the group of rows 4–7. For each bound, it then explains why the bound is correct and which metrics it works for.

The box summary used by KDTree

What the node stores. A KD node stores the smallest and the largest value of each feature in its group. For rows 4–7, x₁ is between 10 and 11, and x₂ is between 10 and 11. These two intervals form a bounding box, and every row of the group is inside it.

How the search calculates the bound. For each feature, the search finds the smallest possible difference between q and any value inside that feature's interval. If the query coordinate is inside the interval, the smallest difference is 0. If the query coordinate is outside the interval, the smallest difference is the distance to the nearer end of the interval.

The search then combines the smallest differences with the same distance formula that it uses for a row:

The two smallest differences lead to the corner (10, 10) of the box. That corner is the point of the box nearest to q. So L_box is the distance from q to the nearest point of the box.

Why the box bound is correct. Take any row in the box, for example row 7, which is (11, 11). Its differences from q are 10.8 and 10.9. Each of these differences is at least the smallest difference for its feature, 9.8 and 9.9, because row 7 is inside each interval. Euclidean distance squares each difference and adds the squares. A larger difference gives a larger square, so the sum for row 7, 235.45, is at least the box sum, 194.05. The same comparison holds for every row in the box. So no row in the group can be closer than L_box, and L_box is a correct lower bound.

Which metrics the box bound works for. The argument compares the distance one feature at a time. So the argument works only when the metric has both of these properties:

1. The distance is built from one separate term for each feature. The Minkowski formula adds the terms, and Chebyshev distance takes the largest term.
2. Each term depends only on the difference in its own feature, and the term grows when that difference grows.

The Minkowski family has both properties. Haversine and Mahalanobis distances do not have property 2 (section 3, Figure 3.2). In haversine distance, the effect of a longitude difference depends on the latitudes. In Mahalanobis distance, the matrix VI combines features. For both distances, the smallest difference in each feature does not give the smallest possible distance, so the box gives no correct lower bound. That is why KDTree.valid_metrics contains only Minkowski names: euclidean, l2, manhattan, cityblock, l1, chebyshev, infinity, minkowski, and p (lines 4239–4244 and 11939–11948).

Those nine names describe only four distances, because most are aliases. For the rows (0, 0) and (3, 4):

The same box gaps serve all four. With gaps of 2 and 1 to a box, the bound is 2 + 1 = 3 for Manhattan, √(4 + 1) = 2.236 for Euclidean, and max(2, 1) = 2 for Chebyshev. The list also reflects what scikit-learn built, and not only what the mathematics allows. seuclidean divides each squared gap by a per-feature variance, so it is a sum of per-feature terms and could have a box bound. But the KD code sums plain gaps only, so seuclidean is not on the list.

The box argument did not use rule 4. Remember this fact for section 8.

Cost. The scikit-learn code for this bound is min_rdist at lines 4332–4356. The build stores each node's smallest and largest values (lines 4309–4313). To find those values, the build needs only comparisons and no distance calculations, so a KD tree is cheap to build.

The ball summary used by BallTree

What the node stores. A ball node stores two values:

• the centroid c, which is the mean of the rows in the group;
• the radius r, which is the largest distance from c to a row in the group.

Every row of the group is inside the ball with center c and radius r. For rows 4–7, the centroid is c = (10.5, 10.5). Each row is 0.5 away from c in each feature, so each row's distance from c is √(0.25 + 0.25) = 0.707. So r = 0.707. The scikit-learn code calculates these values at lines 4047–4063.

How the search calculates the bound. The search calculates one distance, from q to the centroid, and subtracts the radius:

For our group, d(q, c) = √(10.3² + 10.4²) = √214.25 = 14.637. So L_ball = 14.637 − 0.707 = 13.930. The code is fmax(0, dist_pt - radius) at line 4077. The comparison with 0 is necessary when q is inside the ball. In that case, d(q, c) − r is negative, and a distance cannot be negative.

Why the ball bound is correct: the picture. Draw the straight line from q to c. The edge of the ball crosses this line at a distance r before c. Every row is inside the ball, so no row can be closer to q than that crossing point.

This picture is true for Euclidean distance. The proof below shows the same result for any true distance.

Check the result with row 4, which is (10, 10). Its true distance is d(q, row 4) = 13.930, and the bound is also 13.930. The two values are almost equal because row 4 lies almost exactly on the line from q to c, at the edge of the ball.

Which metrics the ball bound works for. The proof used only rule 4, in step 1, and the symmetry rule. Symmetry is necessary because the build measures the radius from c to each row, and step 3 needs d(x, c) = d(c, x). Any true distance obeys both rules. So the ball bound is correct for haversine, Mahalanobis, weighted Minkowski, and a callable metric that obeys the rules. That is why the BallTree list (lines 3950–3969) is much longer than the KDTree list, and why it includes pyfunc, the wrapper for a callable metric. Section 8 lists every name, and it shows that a few of them are not true distances.

Cost. To build a ball node, the tree calculates a mean and then one distance for each row in the node. That is more work than the smallest and largest values of a KD node. During a search, each visited ball node also needs one distance, from q to the centroid.

Compare the two bounds

To more decimal places, L_ball = 13.93017, L_box = 13.93018, and the true distance to row 4 is 13.93018. Both bounds are correct, and the box bound is very slightly larger here. A larger correct bound lets the search skip more groups. For other data, the ball bound can be the larger one, because the result depends on the shape of each group. Move q in Figure 6.4 to see both effects.

import numpy as np

q = np.array([0.2, 0.1])
group = np.array([[10, 10], [10, 11], [11, 10], [11, 11]], dtype=float)

# Box bound: move q to the nearest point inside the box, then measure.
nearest_box_point = np.clip(q, group.min(axis=0), group.max(axis=0))
box_bound = np.linalg.norm(q - nearest_box_point)

# Ball bound: distance to the centroid minus the radius, never below 0.
centroid = group.mean(axis=0)
radius = max(np.linalg.norm(row - centroid) for row in group)
ball_bound = max(0.0, np.linalg.norm(q - centroid) - radius)

true_distances = np.linalg.norm(group - q, axis=1)
assert np.allclose(nearest_box_point, [10, 10])
assert np.isclose(box_bound, np.sqrt(194.05))
assert np.isclose(radius, np.sqrt(0.5))
assert box_bound <= true_distances.min() + 1e-12
assert ball_bound <= true_distances.min() + 1e-12
print(f"box={box_bound:.5f} ball={ball_bound:.5f} nearest row={true_distances.min():.5f}")

7Build and search the trees in scikit-learn

Sections 5 and 6 used a finished tree. This section builds both trees from the eight raw rows, exactly as scikit-learn 1.8.0 does, and then follows the search through the same source code. Four source files hold the whole procedure. _binary_tree.pxi.tp holds the build and the search that both trees share. _kd_tree.pyx.tp and _ball_tree.pyx.tp hold the two parts that differ: the node summary and the lower bound. _partition_nodes.pyx holds the median split. The last subsection rebuilds both trees in about 130 lines of Python and checks them against scikit-learn node by node.

Decide the shape before building

scikit-learn keeps all nodes in one array, so it computes the number of nodes before it builds anything. It takes the number of training rows N and leaf_size, and calculates:

Every split halves a group, so with this depth every leaf holds between leaf_size and 2 × leaf_size rows. When N is not larger than leaf_size, the formula gives one level, and the whole tree is a single leaf. For our eight rows:

• leaf_size=30: (8 − 1) / 30 = 0.23, and max(1, 0.23) = 1. Then log₂ 1 = 0, so the tree has 1 level and 1 node.
• leaf_size=2: 7 / 2 = 3.5, and log₂ 3.5 = 1.81. The floor is 1, so the tree has 2 levels and 3 nodes, with two leaves of 4 rows.
• leaf_size=1: 7 / 1 = 7, and log₂ 7 = 2.81. The floor is 2, so the tree has 3 levels and 7 nodes, with four leaves of 2 rows. This is the tree in Figure 5.2.

The nodes sit in the array level by level. The children of node i are nodes 2i + 1 and 2i + 2, so no node needs to store where its children are. Node i is a leaf when 2i + 1 is past the end of the array.

Build one node at a time

The build is one recursive function, _recursive_build. It starts at node 0 with all rows, and for every node it does the same four things:

1. Store the summary. It calls init_node. A KD node stores the smallest and the largest value of each feature. A ball node stores the centroid, which is the mean of its rows, and the radius, which is the largest distance from the centroid to one of its rows. This step is the only one that differs between the two trees.
2. Stop at a leaf. If 2i + 1 is past the end of the node array, the node is a leaf, and the function returns.
3. Choose the split feature. find_node_split_dim measures each feature's spread, which is its largest value minus its smallest value inside the node. It returns the feature with the largest spread. When two features tie, the first feature wins.
4. Split at the median, then recurse. partition_node_indices moves the n // 2 rows with the smallest values of that feature to the front of the node's slice. Rows with equal values are ordered by row number, so the split is fully determined. Then the function builds the left child from the front half and the right child from the back half, finishing the left side first.

The split does not sort the rows. It calls the C++ function std::nth_element, which only guarantees that every row before the middle position has a value no larger than every row after it. On average that takes time proportional to the number of rows, while a full sort takes n log n. Figure 7.6 steps through how it does this. The tree does not store the split value either. The search uses only the summaries.

Two details of the ball summary are important later. When the tree is built with sample_weight, the centroid is the weighted mean of the rows. And the build finds the radius by comparing squared distances, then takes one square root at the end, which saves a square root for every row.

How a fitted tree is stored

get_arrays() returns the four arrays that hold a fitted tree:

• data is a copy of the training rows.
• idx_array is a reordering of the row numbers. The build moves row numbers in this array and never moves the data itself.
• node_data has one record per node, with idx_start, idx_end, is_leaf, and radius. A node's rows are idx_array[idx_start:idx_end], so every node owns one unbroken slice of that array.
• node_bounds holds the summaries. For a KD tree its shape is (2, n_nodes, D): the lower bounds, then the upper bounds. For a ball tree its shape is (1, n_nodes, D): the centroids. The ball radii are in node_data.

A KD node also fills the radius field, with half the diagonal of its box, but the k-neighbors search never reads it.

Search with three cases

Both trees use one search function, _query_single_depthfirst. Before it starts, query() computes the root's lower bound. Then each call handles one node, in one of three cases:

1. Trim. If the node's bound is larger than the current k-th best distance, the call returns at once. No row inside can replace a candidate.
2. Leaf. If the node is a leaf, the call measures each of its rows and offers each distance to the heap of candidates.
3. Split. Otherwise the call computes the bounds of both children and visits the child with the smaller bound first. On a tie it visits the left child first.

The trees differ only in how they compute a bound. A KD bound is arithmetic on the stored box, as in section 6, so it never calls the metric. A ball bound calls the metric once, for the distance from q to the centroid, and returns max(0, d − r). Each metric call adds 1 to n_calls, which is the count that get_n_calls() reports. For Euclidean distance, the search compares squared distances, which scikit-learn calls reduced distances, and takes square roots only for the final results. Figure 5.2 traced this loop for the KD tree.

Keep the k best rows in a heap

The candidates and t from section 5 live in a small array for each query, inside NeighborsHeap. The array has k slots, all set to ∞ at the start, and it is kept as a max-heap: slot 0 always holds the largest kept distance, which is t. The children of slot s are slots 2s + 1 and 2s + 2, the same layout as the node array. The function heap_push handles each measured row:

1. If the new distance is not smaller than slot 0, the function rejects it, because it cannot be among the k best.
2. Otherwise the new distance replaces slot 0 and moves down. At each level it trades places with its larger child while that child is larger, and it takes the left child when both children are equal.

So the search reads t from slot 0 at no cost, and each accepted row costs about log₂ k trades. After the search, the k slots are sorted once, nearest first.

What the BallTree search pays

A BallTree has the same nodes and the same search loop as a KDTree, so it measures the same rows. It also measures one centroid for every node bound it computes. Figure 7.5 lists every distance call of the BallTree search for q.

So on the eight rows, the BallTree makes 9 calls and the KDTree makes 4. The 5 extra calls are centroid distances: one for the root, two for the root's children, and two for the leaves under rows 0–3. Brute force needs only 8. With many rows, one centroid distance serves every row below its node, so the extra calls become a small share of the work. Section 9 shows that on uniform data a BallTree still measures more distances than a KDTree, and Figure 9.4 compares their times.

The search also offers two other orders: query(..., breadth_first=True) keeps a queue of waiting nodes sorted by bound, and query(..., dualtree=True) builds a second tree over the queries. kneighbors() uses neither of them, so this lesson traces only the default single-tree, depth-first search.

What the build costs

Each level of the tree splits every row exactly once. At one level, the build scans every row and feature to find the spreads, which is about N · D work, and partitions the rows in about N work. A KD summary scans every row and feature once more. A ball summary computes a mean and then one distance for each row, which is also about N · D. There are about log₂(N / leaf_size) levels, so both builds take on the order of N · D · log₂(N / leaf_size) operations. The memory is the copy of the data, idx_array, and one small record and summary per node.

Measured with one thread, N = 10,000 rows, 10,000 queries, and k = 5, from the same runs as Figure 9.4. The build grows with D, but the query grows much faster, so the build is a small share of the total once the query becomes expensive. With only a few queries, the build can cost more than the searches save.

How the median is found: quickselect

std::nth_element usually implements an idea called quickselect. scikit-learn's own docstring calls its wrapper "essentially a partial in-place quicksort around a set pivot" (neighbors/_partition_nodes.pyx). Quickselect repeats three steps:

1. Pick a pivot from the current range of positions.
2. Partition the range. Move the smaller values to the pivot's left and the larger values to its right. The pivot is now exactly where it would be in sorted order.
3. Check the pivot's position. If the pivot is at the target position, stop. Otherwise repeat on the side that contains the target, and never look at the other side again.

Step 3 is why this is faster than sorting. A sort must finish both sides, and quickselect finishes one. Step through it on seven values, with target position 3. This version always takes the last value of the range as its pivot, which makes the steps easy to follow.

How much work this saves. With random data, each pivot discards about half of the range, so the ranges have sizes of about n, n/2, n/4, and so on. That sum is about 2n, which is linear. A sort needs about n log₂ n. Measured on a median of 20,000 values:

In time, on 5 million values, np.partition took 31 ms and np.sort took 231 ms.

A bad pivot rule. A last-value pivot on already sorted data removes only one value per step. On just 4,000 sorted values, it took 5,999,000 comparisons, which grows with the square of n. So real implementations choose pivots more carefully. One common rule, called median-of-three, takes the median of the first, middle, and last values, and it brings sorted data back to the 39,968 in the table. The exact rule inside std::nth_element belongs to the compiler's standard library, so scikit-learn specifies the result and not the steps.

Why ties do not make the tree random. The comparison that scikit-learn passes breaks equal values by row number: a_value == b_value ? a < b : a_value < b_value (_partition_nodes.pyx:38). So every position has one correct answer, whatever the pivots were, and the same data always builds the same tree. Equal values can still end up on both sides of a split, so a split is not a clean "less than" line.

Here is the first step of Fig. 7.6 in writing:

1. Pick the pivot. The last value of [7, 2, 9, 4, 1, 8, 3] is 3.
2. Partition. 2 and 1 are smaller, so they move left, and 3 ends at position 2.
3. Choose the side. The target, position 3, is right of position 2, so the next step works on positions 3 to 6 only.

Why the depth formula has that shape

A median split always halves a node, whatever the values are. So the tree is always balanced, and the number of rows at each level is known before the build looks at the data:

level 0:  N rows
level 1:  N / 2 rows per node
level 2:  N / 4 rows per node
level l:  N / 2^l rows per node

leaf_size is a minimum. So keep halving while the result stays at or above it. Solving N / 2^l ≥ leaf_size for l gives l = log₂(N / leaf_size), rounded down. Add 1 to count the root level, and you have the formula. The source writes it as 1 + max(0, floor(log2((n_samples - 1) / leaf_size))) (_binary_tree.pxi.tp:81).

The build stops as soon as one more halving would go below the minimum. So leaves hold between leaf_size and 2 × leaf_size rows. The name misleads here: leaf_size is not a maximum, and leaf_size=1 on the eight rows gives leaves of 2 rows. The N − 1 matters only on exact boundaries. With 8 rows and leaf_size=2, it gives 2 levels with leaves of 4, where plain N would give 3 levels with leaves of 2.

Because the depth is known first, scikit-learn allocates all 2^levels − 1 nodes at once, and that is what makes the array layout in Figure 7.1 possible.

The formula matched real scikit-learn trees on all twelve shapes below:

What leaf_size trades off

leaf_size never changes the answer. It changes only the speed, and it moves work between two places. Small leaves mean many levels, so the search walks more nodes and the build does more splitting. Large leaves mean fewer levels, so the search measures more rows in each leaf. Here are 200,000 rows, 5 columns, 1,000 queries, and k = 5. Every row of the table returned identical distances:

Build details that are easy to miss

• The split column belongs to the node, not the level. A textbook KD tree often cycles through the features by depth. scikit-learn measures the spread again inside every node. For the rows (0, 0), (1, 50), (2, 1), (3, 51), (100, 2), (101, 52), (102, 3), and (103, 53), the root's spreads are 103 and 53, so it splits on feature 1. Its left child holds the first four rows, whose spreads are 3 and 51, so that child splits on feature 2.
• Each box comes from the node's actual rows. A child could inherit its parent's box and cut it at the split value. scikit-learn recomputes the smallest and largest values from the rows instead (_kd_tree.pyx.tp:97-104). The source comment says that this is slightly slower but gives more compact trees and faster queries, and the reason is that a tighter box gives a larger bound.
• Odd counts go right. The left child gets n // 2 rows and the right child gets the rest, so 9 rows split into 4 and 5 (_binary_tree.pxi.tp:1048).
• Why the median and not the middle of the range. Splitting at the middle of the range could leave almost all the rows on one side when the data is skewed. The median gives equal halves, so the depth is known first and the node array has no gaps.

Build both trees yourself

The code below rebuilds both trees with the rules in this section and runs the search loop with the three cases. It is written for reading, so it sorts where scikit-learn partitions, and it keeps a list where scikit-learn keeps a heap. Neither change alters which rows go into which node, which rows the search measures, or the distances that it returns. Like scikit-learn, it compares squared distances, so it breaks exact ties the same way. When two rows are at exactly the same distance, scikit-learn may list them in a different order.

import math

import numpy as np


def build_tree(X, leaf_size=40, kind="kd_tree"):
    """Build a KDTree or BallTree with the same nodes as scikit-learn 1.8.0.

    The depth is fixed first, so every leaf holds leaf_size to 2 * leaf_size
    rows. Each node splits its rows at the median of the feature with the
    largest spread. Only the summary differs: a KD node keeps the smallest and
    largest value of each feature, a ball node keeps a centroid and a radius.

    Parameters
    ----------
    X : array of shape (n_rows, n_features)
        Training rows.
    leaf_size : int, default=40
        scikit-learn's leaf_size parameter.
    kind : {"kd_tree", "ball_tree"}
        Which summary to store in each node.

    Returns
    -------
    dict
        "kind", "X", "idx_array" (row numbers; node i owns
        idx_array[start:end]) and "nodes" (one dict per node in array order;
        the children of node i are nodes 2i + 1 and 2i + 2).
    """
    X = np.asarray(X, dtype=float)
    n_rows = X.shape[0]
    n_levels = int(math.log2(max(1, (n_rows - 1) / leaf_size)) + 1)
    n_nodes = 2 ** n_levels - 1
    idx_array = np.arange(n_rows)
    nodes = [None] * n_nodes

    def summarize(rows):
        points = X[rows]
        if kind == "kd_tree":
            return {"lower": points.min(axis=0), "upper": points.max(axis=0)}
        centroid = points.mean(axis=0)
        radius = math.sqrt(((points - centroid) ** 2).sum(axis=1).max())
        return {"centroid": centroid, "radius": radius}

    def build(i_node, start, end):
        rows = idx_array[start:end].copy()
        is_leaf = 2 * i_node + 1 >= n_nodes
        nodes[i_node] = {"start": start, "end": end, "is_leaf": is_leaf, **summarize(rows)}
        if is_leaf:
            return
        points = X[rows]
        # The feature with the largest spread; np.argmax keeps the first one on a tie.
        split_feature = int(np.argmax(points.max(axis=0) - points.min(axis=0)))
        # Order by that feature, breaking ties by row number, as scikit-learn's comparator does.
        # scikit-learn only partitions around the middle; sorting gives the same two halves.
        idx_array[start:end] = rows[np.lexsort((rows, points[:, split_feature]))]
        middle = start + (end - start) // 2
        build(2 * i_node + 1, start, middle)
        build(2 * i_node + 2, middle, end)

    build(0, 0, n_rows)
    return {"kind": kind, "X": X, "idx_array": idx_array, "nodes": nodes}


def query(tree, q, k):
    """Find the k nearest rows to q with scikit-learn's depth-first search.

    Parameters
    ----------
    tree : dict
        Output of build_tree.
    q : array of shape (n_features,)
        The query point.
    k : int
        Number of neighbors.

    Returns
    -------
    rows : list of int
        The k nearest rows, nearest first.
    distances : list of float
        Their Euclidean distances.
    calls : int
        Distance calls, counted like tree.get_n_calls(): every row measured,
        plus every centroid measured by a BallTree bound.
    """
    X, nodes, idx_array = tree["X"], tree["nodes"], tree["idx_array"]
    q = np.asarray(q, dtype=float)
    # Like scikit-learn, compare squared distances ("reduced distances"), so that
    # exact ties are decided the same way and no square root is taken per row.
    found = []  # (squared distance, row); scikit-learn keeps the best k in a max-heap
    calls = 0

    def squared_distance(point):
        nonlocal calls
        calls += 1
        return ((q - point) ** 2).sum()

    def squared_lower_bound(node):
        if tree["kind"] == "kd_tree":
            gap = np.maximum(0, np.maximum(node["lower"] - q, q - node["upper"]))
            return (gap ** 2).sum()  # box arithmetic, no distance call
        to_centroid = math.sqrt(squared_distance(node["centroid"]))  # one call per ball
        return max(0.0, to_centroid - node["radius"]) ** 2

    def kth_best():
        return sorted(found)[k - 1][0] if len(found) >= k else math.inf

    def visit(i_node, bound):
        node = nodes[i_node]
        if bound > kth_best():
            return  # trim: no row inside can replace a candidate
        if node["is_leaf"]:
            for row in idx_array[node["start"]:node["end"]]:
                found.append((squared_distance(X[row]), int(row)))
            return
        left, right = 2 * i_node + 1, 2 * i_node + 2
        left_bound, right_bound = squared_lower_bound(nodes[left]), squared_lower_bound(nodes[right])
        if left_bound <= right_bound:
            visit(left, left_bound)
            visit(right, right_bound)
        else:
            visit(right, right_bound)
            visit(left, left_bound)

    visit(0, squared_lower_bound(nodes[0]))
    nearest = sorted(found)[:k]
    return [row for _, row in nearest], [math.sqrt(d) for d, _ in nearest], calls

The check below builds both trees on 1,000 random rows and compares every node, every neighbor, and every count of distance calls with scikit-learn.

from sklearn.neighbors import BallTree, KDTree

rng = np.random.default_rng(0)
X = rng.random((1000, 3))
Q = rng.random((20, 3))

for kind, Tree in (("kd_tree", KDTree), ("ball_tree", BallTree)):
    ours = build_tree(X, leaf_size=10, kind=kind)
    theirs = Tree(X, leaf_size=10)
    _, idx_array, node_data, node_bounds = theirs.get_arrays()
    assert len(ours["nodes"]) == len(node_data)
    for i, node in enumerate(ours["nodes"]):
        their_rows = idx_array[node_data[i]["idx_start"]:node_data[i]["idx_end"]]
        assert set(ours["idx_array"][node["start"]:node["end"]]) == set(their_rows)
        assert node["is_leaf"] == bool(node_data[i]["is_leaf"])
    for q in Q:
        rows, distances, calls = query(ours, q, k=5)
        theirs.reset_n_calls()
        their_distances, their_rows = theirs.query([q], k=5)
        assert rows == their_rows[0].tolist() and calls == theirs.get_n_calls()
    print(kind, "matches scikit-learn:", len(ours["nodes"]), "nodes")

The verification script for this page (section 12) runs these two blocks as they appear on the page. It also tests them on 192 more cases, from 1 to 1,000 rows, including integer data with many exact ties. Every node, distance, and call count matches scikit-learn.

Checkpoint quiz

Closed-book: answer from memory, without scrolling back. The questions mix sections 2 to 7; a missed question links to the part to review, and you can retake the quiz.

8When a lower bound becomes wrong

This section explains the rules that protect condition 1 from section 5: the lower bound must be correct.

Minkowski distance with p < 1 breaks the ball bound

Take a group with two rows, x₁ = (1, 0) and x₂ = (0, 1). Its centroid is c = (0.5, 0.5). Use Minkowski distance with p = 0.5, and use the query q = (1, −1).

1. Radius. From c to x₁, the differences are 0.5 and 0.5. So d(c, x₁) = (√0.5 + √0.5)² = (0.7071 + 0.7071)² = 2.0. The distance to x₂ is the same, so r = 2.0.
2. Distance to the centroid. From q to c, the differences are 0.5 and 1.5. So d(q, c) = (0.7071 + 1.2247)² = 1.9319² = 3.732.
3. Ball bound. L_ball = 3.732 − 2.0 = 1.732.
4. True distance to x₁. The differences are 0 and 1. So d(q, x₁) = (0 + 1)² = 1.0.

The bound says that every row in the group is at least 1.732 away. But x₁ is only 1.0 away, so the bound is wrong. Suppose that the search had t = 1.5 from a row in another group. It would compare 1.732 > 1.5 and skip this group. Then it would miss x₁, which is the nearest row.

The cause is the derivation in section 6, which used rule 4. Minkowski distance with p = 0.5 breaks rule 4 (section 3). So the derivation does not hold.

The failure also occurs on real data. The BallTree class accepts p = 0.5 when you build it directly. On 2,000 random rows, its results differed from brute force by up to 0.053. The estimator prevents this failure: with algorithm="auto", the first rule in Gate 2 sends p < 1 to brute force (lines 794–798).

The KD box bound with p < 1. The box argument in section 6 did not use rule 4. Each term |gap|^0.5 still grows when the gap grows. So the box bound stays correct. In the same test, a KDTree built directly with p = 0.5 matched brute force to within rounding error. But the estimator still rejects algorithm="kd_tree" for p < 1 (lines 816–836). The source comment gives one reason for both trees: they "require a proper distance metric". So this rule is stricter than the KD search that we examined requires.

Feature weights break the KD box bound

The KD tree's box bound (lines 4350–4354) adds pow(0.5 * d, p) for each feature. The weights w do not appear in that sum. So with weights, the search compares weighted row distances against an unweighted box bound.

Use the group of rows 4–7 with p = 2 and weights w = (0.01, 0.01):

• The unweighted box bound is 13.930, as in section 6.
• The true weighted distance to row 4 is √(0.01 × 9.8² + 0.01 × 9.9²) = 0.1 × 13.930 = 1.393.

The bound, 13.930, is larger than a true distance, 1.393, so the bound is wrong. Weights smaller than 1 make the unweighted bound too large, as here. Weights larger than 1 make it smaller than necessary, which is correct but weak. The code has no way to check which case applies, so it rejects every weighted KD tree. An explicit algorithm="kd_tree" with weights raises ValueError (lines 846–855). With algorithm="auto", the second rule in Gate 2 sends weighted Minkowski to the ball tree (lines 799–805).

The ball tree is correct here because it calculates d(q, c) and r with the weighted distance itself. With positive weights and p ≥ 1, weighted Minkowski distance obeys the four rules. So the derivation in section 6 holds.

This is a gap in the code, not in the mathematics. A weighted distance is still a sum of separate per-feature terms, so the box argument from section 6 still works if the bound multiplies each gap term by its weight. For rows 4–7 with w = (0.01, 0.01), a bound with the weights gives √(0.01 × 9.8² + 0.01 × 9.9²) = 1.393, which is exactly the true distance to row 4. The KD code simply leaves w out of the sum (rdist += pow(0.5 * d, tree.dist_metric.p), at _kd_tree.pyx.tp:145 in the installed source).

The failure is real, and only the estimator protects you from it. The class KDTree accepts w when you build it directly, and it gives no warning. On 2,000 random rows and 200 queries, with k = 5 and w = (0.01, 0.01), it returned a wrong neighbor on 53 of the 200 queries. A BallTree built with the same arguments was wrong on 0 of them.

How the ball tree uses the weights

The centroid is not weighted, and the radius is. Here is what init_node stores for each node (_ball_tree.pyx.tp:86), and how the search uses it:

centroid  c  = plain mean of the node's rows                 # no w
radius    r  = largest d_w(c, x) over the node's rows x      # uses w
bound     L  = max(0, d_w(q, c) - r)                         # uses w, at query time

The radius must use the weights. The bound needs every row to lie within r of the centroid when it is measured in the way that queries are measured. Take rows 4–7 with p = 2 and w = (4, 1). Each row is 0.5 from the mean (10.5, 10.5) in both features, so the weighted radius is √(4 × 0.25 + 1 × 0.25) = √1.25 = 1.118. An unweighted radius would be 0.707. Rows at a weighted distance of 1.118 would stick out of that ball, the bound would be too large, and the tree would skip true neighbors. That is the KD problem again.

With w = (0.01, 0.01), the same calculation gives the numbers that the KD bound got wrong:

The centroid does not need the weights, for two reasons. First, the proof in Figure 6.3 never asks where the center is. For any point c, it gives d(q, x) ≥ d(q, c) − r, as long as r covers every row from c in the same metric. A poorly placed center makes r larger and the bound weaker, so the tree skips less, but the answer stays correct. Second, a weighted centroid would be the same point anyway. Weighting feature j is the same as stretching axis j by a factor of w_j^1/p and then measuring the ordinary distance. Averaging and stretching can happen in either order, so "stretch the rows, average them, then undo the stretch" lands on the plain mean. The same stretching argument shows why weighted Minkowski with positive weights and p ≥ 1 obeys rule 4: a stretch of the axes cannot make a detour shorter than the direct path.

Three different weights. When scikit-learn says "weighted centroid", it means a third kind of weight:

sample_weight is the if with_sample_weight: block at _ball_tree.pyx.tp:115-124. KernelDensity uses it. KNeighborsClassifier never passes row weights to the tree, so for KNN the centroid is always the plain mean.

Here is the ball for rows 4–7 with w = (4, 1), in three steps:

1. Take the plain centroid. The mean of the rows is (10.5, 10.5), with no weights.
2. Measure the radius with w. Every row is 0.5 away in both features, so r = √(4 × 0.25 + 1 × 0.25) = 1.118.
3. Bound with w. The bound is max(0, d_w(q, c) − 1.118), where the distance to the centroid also uses w.

Cosine distance has no tree bound

Cosine distance breaks rule 4, so the ball bound does not hold. It is also not a sum of separate per-feature terms, so the box bound does not hold. Neither tree list contains cosine. With algorithm="auto", the last rule in Gate 2 sends it to brute force (lines 813–814). An explicit algorithm="ball_tree" with metric="cosine" raises ValueError from _check_algorithm_metric (lines 611–619).

If you need a tree for cosine neighbors, there is another route. Divide each row by its length so that every row has length 1. For rows of length 1, ‖a − b‖² = 2(1 − cos θ). So Euclidean distance orders the neighbors in the same way as cosine distance, and Euclidean distance supports both trees.

Not every name in the BallTree list is a true distance

Section 6 said that the ball bound is correct for every true distance. That statement does not cover the reverse direction: the BallTree list also contains some names that are not true distances. The list has 22 names, the nine KD names and these 13. The first group works on ordinary numbers, with a = (1, 2) and b = (3, 1) in the examples:

The second group is for yes/no features, and these metrics differ in how they treat matches. Take x = [1, 1, 0, 0, 1] and y = [1, 0, 1, 0, 1]. Two positions have both values equal to 1, two positions differ, one position has both equal to 0, and there are N = 5 positions:

A test on random rows found these problems. It checked the rules on 200,000 random triples, and it compared a BallTree of 300 rows with brute force on 100 queries:

So auto can choose ball_tree for braycurtis and return a wrong neighbor now and then, with no warning. When you use braycurtis or dice, set algorithm="brute" yourself. The other tested names, canberra, jaccard, hamming, rogerstanimoto, sokalmichener, and sokalsneath, showed no violation in the same test, which is evidence and not a proof.

The yes/no metrics start from the same three counts. For x = [1, 1, 0, 0, 1] and y = [1, 0, 1, 0, 1]:

1. Count the positions. 2 differ, 2 have both values equal to 1, and N = 5.
2. Apply each formula. hamming is 2 / 5 = 0.4, jaccard is 2 / (2 + 2) = 0.5, and dice is 2 / (2 + 2 · 2) = 0.333.

The safety check after the auto rules

Lines 816–836 run after the auto block. They run for every value of algorithm. When effective_metric_ is "minkowski" and p < 1, this check does the following:

An explicit algorithm value skips the whole auto block. So for an explicit tree, this check is the only rule that prevents the failure in this section.

9When a correct lower bound stops saving work

This section explains the rules that protect condition 2 from section 5: the lower bound must be useful. In all these cases the tree returns correct results, but brute force is expected to be faster.

Many features

The following experiment measures how many distances a tree calculates. It uses N = 10,000 rows with values drawn uniformly at random from [0, 1] in each feature. It runs 200 queries with k = 5 and leaf_size=30. The method get_n_calls() counts the distance calculations. The table divides that count by N. A value of 1.0 means that the tree calculated as many distances as brute force.

The script below repeats the KDTree column for four feature counts. It draws different random rows from the run that produced the table, so its fractions differ slightly. For example, it prints 0.117 instead of 0.126 for 8 features.

import numpy as np
from sklearn.neighbors import KDTree

rng = np.random.default_rng(0)
n_rows, n_queries = 10_000, 200
fractions = {}
for n_features in [2, 8, 16, 32]:
    X = rng.random((n_rows, n_features))
    Q = rng.random((n_queries, n_features))
    tree = KDTree(X, leaf_size=30)
    tree.reset_n_calls()
    tree.query(Q, k=5)
    # Distances calculated per query, as a fraction of the brute-force count.
    fractions[n_features] = tree.get_n_calls() / n_queries / n_rows
    print(n_features, round(fractions[n_features], 3))

assert fractions[2] < 0.05
assert fractions[16] > 0.8

The last column of the table divides the distance to the nearest row by the distance to the farthest row, for each query, and shows the median over the 200 queries.

The test L > t needs groups that are clearly farther away than the k-th best row. The last column shows that this situation becomes rare as D increases. With 2 features, the nearest row is typically about 220 times closer than the farthest row. With 64 features, the nearest row is only about 1.7 times closer. When most distances are similar, t is close to the distance of most rows, so few group bounds are larger than t. This effect is one part of the curse of dimensionality. Beyer et al. (1999) proved that the ratio between the nearest and the farthest distance approaches 1 under broad conditions. They observed the effect at 10–15 dimensions.

At D = 16, the KD tree calculates 95% of the distances, and it also does the work of visiting nodes. Brute force calculates 100% of the distances, and for Euclidean distance it does so at BLAS speed (section 4). So Gate 1 sends _fit_X.shape[1] > 15 to brute force.

Limit of this rule. Uniform random data fills the whole space, so it is the most difficult case for a tree. Real data often lies near a surface with fewer directions. The intrinsic dimension is the number of directions in which the data actually varies. For example, 40 features that come from 3 underlying factors have an intrinsic dimension near 3. A tree can still skip many groups in that data. The scikit-learn guide says that "sparser data with a smaller intrinsic dimensionality leads to faster query times." But the rule counts columns, not the intrinsic dimension. So for such data, you must set algorithm yourself and measure the result.

Many neighbors

Repeat the experiment with D = 2 and change k instead:

The value t is the distance of the k-th best row. With k = 5,000 = N/2, t is close to the median distance of all rows. Half of all rows are closer than t, so the search must calculate their distances anyway. Most groups also contain some rows closer than t, so their bounds are smaller than t. As a result, the tree calculates 72% of the distances and also visits nodes.

So Gate 1 sends n_neighbors >= _fit_X.shape[0] // 2 to brute force. The operator // is integer division, which drops the remainder: 8 // 2 is 4, and 9 // 2 is also 4. In section 1, k = 3 gave 3 >= 4, which is false, so the auto rules chose a tree. And k = 4 gave 4 >= 4, which is true, so they chose brute force.

Limit of this rule. The rule reads n_neighbors from the constructor during fit(). A later call such as kneighbors(X_new, n_neighbors=500) does not run fit() again. So the search method stays the same, even when the new k would give a different result.

Precomputed distances

With metric="precomputed", you give fit() an N × N matrix instead of rows. The entry in row i and column j is the distance between training rows i and j. The code checks that the matrix is square (lines 741–749). There are no coordinates, so a tree cannot calculate a box or a centroid. Brute force reads the distances directly from the matrix, so Gate 1 sends this case to brute force.

Sparse input

A sparse matrix stores only the nonzero entries and their positions. The trees need dense rows of coordinates. The code handles sparse input before the selection rules (lines 755–775). It always uses brute force, and it warns you if you asked for a tree. So sparse input never reaches the rules in section 10.

Time, measured

The fractions above count distances, but they do not measure time. A tree pays for each distance in its own compiled loop and also pays to visit nodes, while with Euclidean distance, which this figure uses, brute force gets each distance from BLAS much more cheaply (section 4). So a tree can lose on time while it still skips most of the distances. Figure 9.4 times fit() plus kneighbors() for all three methods on uniform random rows.

What the measurement shows. On this machine, with one thread, the KD tree is the fastest method up to 8 features, and brute force is the fastest from 16 features on. At 8 features the KD tree measures about 13% of the distances, but it is also only about 13% faster than brute force. So here one tree distance costs about 7 brute-force distances, which is the BLAS effect from section 4. The rule n_features > 15 sends the data to brute force later than the measured crossover, which lies somewhere between 8 and 16 features.

With the default thread count, brute force uses all 12 cores while the KD tree query uses one, so the crossover moves lower. Brute force is already about 2.5 times faster at 8 features, where auto still chooses kd_tree. The same effect explains the k rule. With one thread, the KD tree is faster than brute force even at k = 5,000. With all cores, brute force wins there, as Gate 1 assumes.

Limits of this measurement. The rows are uniform random, which this section calls the most difficult case for a tree, so real data with a low intrinsic dimension can move the crossover up. A tree query can also use several cores through the n_jobs parameter, which this run did not set. Re-run verify_knn_lesson.py --timing on your own machine before you rely on these numbers.

The speed rules do not rest on BLAS

The BLAS shortcut exists only for Euclidean distance, yet Gate 1 sends every metric to brute force. So BLAS cannot be the main reason for that rule. The rule rests on what this section measured first: as the columns grow, a tree loses its ability to skip rows, and that happens for every metric. BLAS only widens the lead for Euclidean distance. This table times kneighbors for 50,000 uniform rows, 200 queries, and k = 5:

Brute force wins at 15 and 50 columns even for p = 1 and p = 3, which have no shortcut. At 50 columns the KD tree measures every row, so it does all of brute force's distance work and also pays to walk the tree, to test bounds that it cannot use, and to jump around in memory. At 15 columns with p = 3, the tree measured only 36% of the rows and was still slower. So skipping some rows is not enough. A tree must skip enough rows to repay its extra work. The rule n_neighbors >= n_samples // 2 has the same basis: if you need half of the rows, a tree cannot skip much, whatever the metric is.

BLAS shows up in the size of the lead. At 50 columns, the KD tree takes 64 times as long as brute force for p = 2, 13 times for p = 1, and 3.8 times for p = 3. There is a limit on this measurement: scikit-learn's brute search runs on several threads, and these tree queries ran on one, so part of brute force's lead comes from threads. This run did not separate that part.

Column count is only a stand-in for structure. Here is the same test on 50 columns, with rows from 20 clusters that really live in 3 dimensions:

So keep the rule as a default, and set algorithm="kd_tree" yourself on data that you know is clustered.

What the auto rules do not measure

The scikit-learn guide states that the auto rules assume two conditions. First, the number of queries is at least about the same as the number of training rows. Second, leaf_size is close to the default, 30. The code checks neither condition. If you make only a few queries, the tree build can cost more than the searches save. The rules also never measure time. They predict which method is faster from fixed thresholds.

10Read the selection code

You now have the reason for every rule. This is the selection code from NeighborsBase._fit, lines 777–814:

self._fit_method = self.algorithm
self._fit_X = X
self.n_samples_fit_ = X.shape[0]

if self._fit_method == "auto":
    # A tree approach is better for small number of neighbors or small
    # number of features, with KDTree generally faster when available
    if (
        self.metric == "precomputed"
        or self._fit_X.shape[1] > 15
        or (
            self.n_neighbors is not None
            and self.n_neighbors >= self._fit_X.shape[0] // 2
        )
    ):
        self._fit_method = "brute"
    else:
        if (
            self.effective_metric_ == "minkowski"
            and self.effective_metric_params_["p"] < 1
        ):
            self._fit_method = "brute"
        elif (
            self.effective_metric_ == "minkowski"
            and self.effective_metric_params_.get("w") is not None
        ):
            # 'minkowski' with weights is not supported by KDTree but is
            # supported byBallTree.
            self._fit_method = "ball_tree"
        elif self.effective_metric_ in VALID_METRICS["kd_tree"]:
            self._fit_method = "kd_tree"
        elif (
            callable(self.effective_metric_)
            or self.effective_metric_ in VALID_METRICS["ball_tree"]
        ):
            self._fit_method = "ball_tree"
        else:
            self._fit_method = "brute"

Three Python details are useful here:

• callable(obj) returns True when obj can be called, for example a function. So it detects a callable metric.
• dict.get("w") returns None when the key "w" does not exist. So the weight test is safe when no weights were given.
• VALID_METRICS["kd_tree"] and VALID_METRICS["ball_tree"] are the metric-name lists of the two trees (line 225).

The code has two gates. Gate 1 asks whether a tree can save work. Gate 2 asks which tree, if any, gives a correct bound for the metric. The predictor below runs the same rules in the same order, plus the checks that run after the selection. Change a setting and watch which rule fires.

All eight checks as one list

The two gates are one sequence, and it is easier to remember as one numbered list. The first three checks are one if joined by or. The last five are its else branch, where the first match wins.

fit(X), algorithm == "auto"
│
├─ Gate 1: any one true gives "brute", and the decision ends here
│    1. metric == "precomputed"
│    2. X.shape[1] > 15
│    3. n_neighbors >= X.shape[0] // 2
│
└─ Gate 2: reached only when 1–3 are all false; the first match wins
     4. minkowski and p < 1                  → "brute"
     5. minkowski with feature weights w     → "ball_tree"
     6. metric is in the KD list             → "kd_tree"
     7. callable, or metric in the ball list → "ball_tree"
     8. anything else                        → "brute"

The order inside Gate 1 does not change the result, because all three checks lead to brute force. So an if and an elif give the same answer as one or. The order inside Gate 2 does change the result, as the next subsection shows.

Why the order in Gate 2 matters

The name "minkowski" is in the KDTree list. Suppose that the KDTree test came first. Then p = 0.5 would select "kd_tree", and the safety check would raise ValueError. Weighted Minkowski would also select "kd_tree", and line 846 would raise ValueError. The two Minkowski tests come first, so auto never selects a tree that a later check rejects.

Gate 2 tests the KDTree list before the BallTree list. Every KDTree metric is also in the BallTree list, so for those metrics the order of the two tests determines the result. The source comment explains the preference: KDTree is "generally faster when available". Section 6 gives one reason, which is that a KD node needs only comparisons to build.

After the selection

Lines 816–836 run the safety check from section 8. Then lines 838–865 build the structure for the selected method:

• "ball_tree": BallTree(X, leaf_size, metric=effective_metric_, **effective_metric_params_);
• "kd_tree": KDTree(...) with the same arguments, after the weight check at line 846;
• "brute": self._tree = None, so no structure is built.

The value leaf_size affects only this build step. It has no effect on the selection rules.

Why fit keeps its decision apart from your setting

The estimator holds two kinds of information. A setting is what you asked for: algorithm="auto" means "choose for me, from the data". A decision is what fit worked out for this data: "8 rows and k = 4, so brute force". Fitting on other data can change the decision, and it must not change the setting. So self.algorithm never changes, and the decision goes into _fit_method.

Compare this with a toy model whose fit writes its decision back into self.algorithm:

On the toy's second fit, self.algorithm is no longer "auto", so the rules never run again. The model keeps a choice that it made for data it no longer has. The last row is why this matters beyond a refit. GridSearchCV, cross_val_score, and clone never reuse your object. For every fold and every combination of settings, they read the settings back from the attributes named after the __init__ arguments, build a new model from them, and fit the new model. So a stale brute would pass to every model of the search, and nothing would tell you.

The rule is that fit does not change anything that __init__ set. What fit learns or decides goes into a new attribute, with a trailing underscore (classes_, n_samples_fit_) or a leading one for internal values (_fit_method).

The same rule applies to metric_params. fit reads it into effective_metric_params_, using {} when it is None and otherwise a copy (neighbors/_base.py:529-531 in the installed source). The None default also avoids a Python problem: a default such as metric_params={} is created once, when Python defines the function, so all models built with that default share one dictionary. Adding "w" to one model's dictionary would add it to every other model's. The copy protects the fitted model in the other direction: a caller who edits their dictionary after fit cannot change the model.

Follow one estimator through two fits and a clone, with k = 4:

1. Fit on 8 rows. 4 ≥ 8 // 2, so _fit_method is brute, and algorithm stays "auto".
2. Fit on 1,000 rows. algorithm is still "auto", so the rules run again, and _fit_method becomes kd_tree.
3. Clone. The copy reads "auto" from algorithm and has no _fit_method until it is fitted.

Checkpoint quiz

Closed-book: answer from memory, without scrolling back. The questions mix sections 2 to 10; a missed question links to the part to review, and you can retake the quiz.

11Walk through every line scikit-learn runs

This section follows the real scikit-learn 1.8.0 code through three statements: creating KNeighborsClassifier(n_neighbors=3), calling .fit(X, y) on the eight rows, and calling .predict([[0.2, 0.1]]). A tracer recorded every scikit-learn function that those statements called, every line that ran, and the values that went in and came out. The code below is the installed files' own text, so its line numbers are the installed files' numbers. They differ from the line numbers of the source snapshot in section 10.

A second run with n_neighbors=4 makes fit choose brute force, and its predict takes a different route. The last four steps follow that route.

The walkthrough is written for a reader who knows basic Python. Its aim is that you can read the code itself, so each note first explains what a line does for any input, including the Python it uses, and only then says what happened with our eight rows, in a green In our run box. Where the code relies on a Python feature that basic Python does not cover, such as decorators, *args, with blocks, or generators, a Python you need for this step card explains it first, with a small example and the output it prints.

The KD tree itself is compiled Cython, which no Python tracer can see. Five steps after fit and four steps inside predict open its source from the template files that scikit-learn ships. They carry a compiled Cython chip and no run marks, and their values come from the finished tree: the fitted model's one-leaf tree, and the 7-node tree with leaf_size=1 from section 7, whose build splits and whose search prunes.

How to read this walkthrough

The format follows what research on learning from worked examples recommends. The code is cut into short steps, each with a label that names its subgoal, because segmented examples teach the same content with less effort than one long listing (Spanjers, van Gog, and van Merriënboer, 2012), and subgoal labels help programmers solve new problems (Margulieux, Catrambone, and Guzdial, 2016). Notes sit next to the lines they explain, and lines that did not run are dimmed, following the signaling and spatial-contiguity principles of multimedia learning (Mayer). And every step shows the values from the actual run, in the same way that Online Python Tutor shows the program's state next to the code (Guo, 2013). Each step has the same parts:

• a path that shows where the step sits in the call stack;
• a purpose box, before the code, that says what the step does and why;
• a Python you need panel, when the code uses a feature that needs explaining, with a card the first time and a link back to it later;
• one or more code excerpts with numbered marks, and the notes for those marks beside the code, each note followed by an In our run box when the run adds something;
• the values in our run, and a button that opens the whole function;
• excerpts that run at import, whose header says runs once at import. They show the imports, class lines, and decorators that Python ran when it loaded the module, and these lines determine which function runs for a call such as model.fit or self._fit. They have no run marks, because the trace starts after the import.

Figure 11.1 comes first, as a map of every call. Use it to see the whole path, and the steps to read it.

The steps

Practice: follow the code

Three questions on where the code you just read comes from. They use the class line, the MRO, and the decorator steps.

11aAfter the search: from neighbors to a prediction

The search returns the k nearest rows and their distances. The rest of predict does not depend on the search method, so all three methods give the same prediction from the same neighbors. Section 11 traced that code on one run. This section states its rules, and adds two decisions that the search rules do not make for you: the value of k and the scale of the features.

The vote

With weights="uniform", each of the k neighbors has one vote, and the most common class wins. With weights="distance", each neighbor votes with 1 / d, so a closer row counts more. predict_proba reports each class's share of the votes. For q = (0.2, 0.1) on the eight rows with k = 5, the neighbors are rows 0–4, so four are class A and one is class B:

Three edge cases are easy to miss:

• A tied vote goes to the smallest class label, not to the nearest row. With training rows 0 (class "b") and 1 (class "a"), the query 0.1, and k = 2, uniform voting predicts "a" even though the "b" row is much closer. With weights="distance", the same query predicts "b". An odd k avoids ties for two classes only.
• A distance of zero would make 1 / d infinite. So when a query equals one or more training rows, those rows get weight 1 and every other row gets weight 0 (_get_weights in neighbors/_base.py). With a query equal to a class A row and three class B rows as the other neighbors, the shares are 1.0 and 0.0.
• Rows at equal distances have no guaranteed order. When several rows tie for the k-th place, the method can change which one is kept, so two methods can differ in a tied case while both are correct.

A regressor uses the same neighbors and averages their targets. With targets 1, 2, 3, and 4 on rows 0–3, q as above, and k = 3, the neighbors are rows 0, 2, and 1. KNeighborsRegressor gives their plain mean, 2.0, with weights="uniform", and 1.525 with weights="distance", which pulls the answer toward row 0.

Here is the vote for q with k = 5, in two steps:

1. Count the uniform votes. Four neighbors are class A and one is class B, so A's share is 4 / 5 = 0.8.
2. Weight by 1 / d. Row 4 is 13.930 away, so its vote is about 0.07, and A's share rises to 0.9907.

A row is not its own neighbor, sometimes

kneighbors(X_new) searches among all the training rows, so a query that equals a training row finds that row at distance 0. kneighbors() with no argument means "the neighbors of each training row", and it leaves each row out of its own list. On the eight rows with n_neighbors=2, kneighbors(X[:1]) returns rows 0 and 1 for row 0, and kneighbors() returns rows 2 and 1 for row 0. So if you measure accuracy by predicting the training rows themselves, the result is too high: with k = 1, each row finds itself.

A regressor and a score on the training rows follow the same rules:

1. Find the neighbors. For q with k = 3, they are rows 0, 2 and 1, with targets 1, 3 and 2.
2. Average them. The plain mean is 2.0. With distance weights it is 1.525, nearer to row 0's target.
3. Score honestly. On the training rows, each row finds itself, so k = 1 scores 1.0 there whatever the data.

Choosing k

k is the one setting that changes the model's smoothness. A small k follows individual rows, and a large k averages over a wide region. With k close to N, the prediction approaches the most common class everywhere. Here is the cross-validated accuracy on the load_breast_cancer data, with scaled features and 5 folds:

Select k with cross-validation on your own data, and remember that a change of k at fit time can also change the search method (Gate 1).

Scale the features first

Every distance in this lesson adds gaps across features with no regard for their units. So a feature with a large range mostly determines the neighbors. Take the query (salary 50,000, age 26) and three rows:

By raw distance, row 1 is the nearest, even though its age differs by 34 years. The distance compares the salary gap of 10 and the age gap of 34 as plain numbers. After scaling, row 0 is the nearest. On real data the effect can be large, with k = 5 and 5-fold cross-validation:

Scaling also changes the tree. The build splits on the column with the widest raw spread, so without scaling it can keep splitting on the same large-scale column. Fit the scaler on the training rows only, which a Pipeline does for you, so that information from validation rows does not leak into it. metric="seuclidean" and w = 1 / variance give the same distances as scaling, but both send auto to the ball tree and lose the BLAS shortcut. Scaling first keeps plain Euclidean distance, so it keeps the KD tree and the shortcut.

Here is row 1 of the salary example, before and after scaling:

1. Measure the raw distance. The gaps are 10 and 34, so √(10² + 34²) = 35.4.
2. Divide each gap by its column's standard deviation. The scaled distance is 2.121, and row 0, at 0.027, becomes the nearest.

What each method costs

All three keep the training rows, because KNN has no other model. So the model grows with the data, and prediction, not training, is where the time goes.

Missing values. fit raises ValueError on NaN for every metric but one. In scikit-learn 1.8.0, metric="nan_euclidean" accepts NaN (neighbors/_base.py:708), and auto then chooses brute force. scikit-learn 1.5.2 still raised the error for that metric. So unless you use it, fill or drop missing values before you fit, for example with an imputer in a Pipeline.

Radius search. radius_neighbors uses the same trees and the same bounds. The test compares each bound with your fixed radius instead of the moving t, so it needs no heap.

12Check every rule against scikit-learn

The following script fits the estimator for each case in this lesson and checks the stored search method. Each row in the results table comes from this script, run with scikit-learn 1.8.0.

import warnings
import numpy as np
from sklearn.neighbors import KNeighborsClassifier, BallTree, KDTree

X8 = np.array([[0, 0], [0, 1], [1, 0], [1, 1], [10, 10], [10, 11], [11, 10], [11, 11]], dtype=float)
y8 = np.array([0, 0, 0, 0, 1, 1, 1, 1])
rng = np.random.default_rng(0)

def search_method(X, y, **settings):
    """Fit KNeighborsClassifier and return its search method, or the error class name."""
    with warnings.catch_warnings():
        warnings.simplefilter("ignore")
        try:
            return KNeighborsClassifier(**settings).fit(X, y)._fit_method
        except ValueError:
            return "ValueError"

X16 = rng.random((1000, 16))
y1000 = rng.integers(0, 2, 1000)
distance_matrix = np.abs(X8[:, None, :] - X8[None, :, :]).sum(axis=2)

expected = [
    ("k=3, Euclidean",              search_method(X8, y8, n_neighbors=3),                                         "kd_tree"),
    ("k=4, Euclidean",              search_method(X8, y8, n_neighbors=4),                                         "brute"),
    ("p=3",                         search_method(X8, y8, n_neighbors=3, p=3),                                   "kd_tree"),
    ("p=0.5",                       search_method(X8, y8, n_neighbors=3, p=0.5),                                 "brute"),
    ("p=0.5, explicit kd_tree",     search_method(X8, y8, n_neighbors=3, p=0.5, algorithm="kd_tree"),            "ValueError"),
    ("weights (0.01, 0.01)",        search_method(X8, y8, n_neighbors=3, metric_params={"w": np.array([0.01, 0.01])}), "ball_tree"),
    ("weights (1, 1)",              search_method(X8, y8, n_neighbors=3, metric_params={"w": np.array([1.0, 1.0])}),   "ball_tree"),
    ("weights, explicit kd_tree",   search_method(X8, y8, n_neighbors=3, metric_params={"w": np.array([4.0, 4.0])}, algorithm="kd_tree"), "ValueError"),
    ("cosine",                      search_method(X8 + 1, y8, n_neighbors=3, metric="cosine"),                   "brute"),
    ("cosine, explicit ball_tree",  search_method(X8 + 1, y8, n_neighbors=3, metric="cosine", algorithm="ball_tree"), "ValueError"),
    ("haversine",                   search_method(X8 / 20, y8, n_neighbors=3, metric="haversine"),               "ball_tree"),
    ("callable",                    search_method(X8, y8, n_neighbors=3, metric=lambda a, b: np.abs(a - b).sum()), "ball_tree"),
    ("16 features",                 search_method(X16, y1000),                                                    "brute"),
    ("16 features, explicit kd_tree", search_method(X16, y1000, algorithm="kd_tree"),                             "kd_tree"),
    ("precomputed",                 search_method(distance_matrix, y8, n_neighbors=3, metric="precomputed"),     "brute"),
]
for label, actual, wanted in expected:
    print(f"{label:32s} {actual}")
    assert actual == wanted, (label, actual, wanted)

# Direct tree construction with p = 0.5: BallTree gives wrong distances, KDTree does not.
X = rng.random((2000, 3))
Q = rng.random((300, 3))
brute_distances = np.sort((np.abs(Q[:, None, :] - X[None]) ** 0.5).sum(axis=2) ** 2, axis=1)[:, :5]
ball_distances, _ = BallTree(X, metric="minkowski", p=0.5).query(Q, k=5)
kd_distances, _ = KDTree(X, metric="minkowski", p=0.5).query(Q, k=5)
assert np.abs(ball_distances - brute_distances).max() > 0.01
assert np.allclose(kd_distances, brute_distances)
print("All search-method checks passed")

Check this whole page

The script above checks the table. A second script, assets/knn-search-method/verify_knn_lesson.py next to this lesson, checks the page itself against the installed scikit-learn. It recomputes the worked numbers and finds each one in the page text. It rebuilds the trees in Figures 5.2 and 7.5, logs the BallTree calls, and replays both searches from get_arrays(). It checks the section 7 build rules, the level count, every median split, and the heap, on the lesson rows and on random data with ties. It runs the reference implementation from section 7 exactly as the page prints it, and compares it with scikit-learn on 192 tree shapes. It re-traces the three statements of section 11 in a fresh interpreter and compares every function's source, every executed line, the call trees, and the printed values with the page, and it checks that every walkthrough note points at a line that ran, or is marked as not run. It compares every quoted Cython line with the template files that scikit-learn ships, recomputes the small-tree numbers that the compiled-code notes state, and runs every Python example on the concept cards to confirm the output they print. It recomputes every answer and known mistake in the practice, the quizzes, and the diagnostic, with NumPy arithmetic, real fit() calls, and scikit-learn's own trees, and requires the page's practice block to equal that computation. It compares tree results with brute force for every supported metric. It runs this page's own predictor from Figure 10.1 in Node over a few thousand settings and compares each answer with _fit_method. It re-runs the section 9 experiments. And it parses every sentence of the page, including the walkthrough notes and the practice, to confirm that none uses a construction that slows readers, such as a dropped "that" or a stack of three nouns. It exits with an error when any claim fails.

python verify_knn_lesson.py              # check the page
python verify_knn_lesson.py --timing     # also re-time Figure 9.4 and report the winners
python verify_knn_lesson.py --export     # rewrite the page's tree and trace data from scikit-learn first

A third script, assets/knn-search-method/verify_knn_additions.py, covers the subsections that verify_knn_lesson.py does not: broadcasting, ‖x‖², other metrics, quickselect, depth, leaf_size, the weights, the metric lists, settings and decisions, and the prediction step. --check finds its exact numbers in this page, and checks that every file:line citation still points at the code that the page describes. verify_knn_lesson.py runs it as its last stage. Timings are printed only, because they depend on the machine.

Last run on 2 November 2026 with scikit-learn 1.8.0: 142 checks passed and 0 failed. That includes 4,416 predictor configurations with no mismatch, and exact agreement with brute force for every supported metric.

13Common misconceptions and limits

14Exercises

Check yourself on everything

Ten closed-book questions over the whole lesson, in mixed order. Each missed question names the part to review.

A multi-part problem

One new setting, four parts. Each part uses one idea from an earlier section, in the order that fit() applies them.

Open exercises

Try each exercise before you open its answer. You can test your predictions for exercises 1 and 4 in the predictor in section 10.

15Summary

• fit() for KNN stores the data and chooses a search method: brute, kd_tree, or ball_tree.
• A tree skips a group of rows when the group's lower bound L is larger than the current k-th best distance t. This needs a correct bound and a useful bound.
• scikit-learn builds both trees with one function. It fixes the depth from N and leaf_size, splits each node at the median of its widest feature, with ties ordered by row number, and stores a box (KD) or a centroid and radius (ball). Both trees hold the same rows in every node.
• Both trees search with one depth-first loop and keep the k best rows in a max-heap whose top is t. A ball bound costs one distance call; a box bound costs none.
• The box bound of the KD tree is correct when the distance is a sum of separate per-feature terms. That is true only for the Minkowski family. The bound ignores feature weights.
• The ball bound max(0, d(q, c) − r) comes from the triangle inequality. So it is correct for every true distance and wrong for distances that break rule 4, such as Minkowski with p < 1.
• Gate 1 chooses brute force when a tree is not expected to save work: precomputed distances, more than 15 features, or n_neighbors >= n_samples // 2.
• Gate 2 chooses the first tree that gives a correct bound for the metric, with KDTree first. Otherwise it chooses brute force.
• The safety check rejects an explicit tree for Minkowski with p < 1. Line 846 rejects an explicit KD tree with weights.
• The rules are fixed thresholds. They do not measure time, intrinsic dimension, the number of queries, or the k used at query time.

16Review cards

Come back to these after about a day, a week, and a month. Try to answer each question before you open it. The same cards are below as Question::Answer lines that you can copy into a note tagged #flashcards for Obsidian's Spaced Repetition plugin.

What does fit() choose for a KNN estimator, and where does it store the choice?::The search method, brute, kd_tree, or ball_tree, stored in _fit_method.
When can a tree search skip a group of rows?::When the group's lower bound is larger than the current k-th best distance t.
Which property of a metric makes the KD box bound correct?::The distance is a sum (or maximum) of separate per-feature terms that grow with each difference: the Minkowski family.
Which property of a metric makes the ball bound correct?::The triangle inequality and symmetry, which every true distance has.
Why does Minkowski distance with p < 1 go to brute force?::It breaks the triangle inequality, so tree bounds can be wrong.
Why does weighted Minkowski go to the ball tree?::The KD tree's box bound ignores the weights; the ball tree measures with the weighted distance itself.
What are the three conditions of Gate 1?::Precomputed distances, more than 15 features, or n_neighbors >= n_samples // 2; any one gives brute force.
Why can brute force beat a tree that skips 90% of the distances?::The tree also pays to walk nodes and test bounds, and for Euclidean distance brute force gets its distances from one matrix product computed by BLAS, which is much cheaper per distance than a tree's loop.
How many levels does scikit-learn's tree have?::floor(log2(max(1, (N - 1) / leaf_size))) + 1, so every leaf holds leaf_size to 2 × leaf_size rows.
What does slot 0 of the neighbor heap hold?::The largest of the k kept distances, which is t.
What does the class store under the name fit?::The _fit_context decorator's wrapper; functools.wraps copied the original's name and docstring onto it.
Does kneighbors(X, n_neighbors=500) rerun the selection rules?::No. The method was chosen once in fit(), from the constructor's n_neighbors.
Where do per-feature weights go, and how do they differ from weights=?::Inside metric_params as w. They change the distance during the search, so they can change which rows are neighbors. weights= changes only how neighbors vote afterwards.
Is the KD tree's failure with w a limit of the mathematics?::No. The distance is still a sum of per-feature terms, so a bound that multiplied each term by its weight would be correct. The KD code leaves w out of the sum.
Why doesn't the ball centroid need the feature weights?::The bound holds for any center, as long as the radius covers every row in the same metric. And a weighted mean of stretched axes gives the plain mean anyway.
Why doesn't the rule for many features rest on BLAS?::BLAS applies to Euclidean distance only, and brute force still wins at 50 columns for other metrics. The tree stops skipping rows, so it does all the distance work and also walks the tree.
Why does the expansion work only for p = 2?::Squaring splits a difference into a query part, a row part, and a plain product. An absolute value or another power doesn't split in that way.
What does brute force do for p other than 2?::A compiled double loop over query and row pairs. It works one column at a time, does not call BLAS, and skips the final root during the search.
Why can't ddot alone give the squared length of each row?::ddot takes two vectors and returns one number, and BLAS has no per-row routine. So per-row values need a loop, which must be compiled to stay fast.
What does np.einsum run on?::NumPy's own compiled C loop, not BLAS. It keeps one running total per row, so it builds no temporary matrix.
Does scikit-learn keep the squared row lengths between kneighbors calls?::No. Each call computes them again and uses them for all the queries in that call.
What does std::nth_element guarantee?::The value at the target position is the one that sorting would put there, with no larger value before it and no smaller value after it. Neither side is sorted.
Why is quickselect about 2n and a sort about n log n?::Quickselect continues on only the side that holds the target, so its ranges shrink as n, n/2, n/4, and so on. A sort must finish both sides.
Is leaf_size the largest number of rows in a leaf?::No. It is the minimum. Leaves hold between leaf_size and 2 x leaf_size rows.
What does leaf_size change, and what does it never change?::It moves work between walking nodes and measuring leaf rows, so it changes speed and build time. It never changes the neighbors.
Why must fit leave self.algorithm alone?::The setting means choose from the data. If fit overwrote it, a later fit would skip the rules, and clone or GridSearchCV would copy the stale decision to every model.
Which class wins a tied uniform vote?::The smallest class label, not the class of the nearest row.
Why scale features before KNN?::The distance adds gaps across features as plain numbers, so a feature with a large range mostly determines the neighbors.

Sources

• scikit-learn developers. Nearest Neighbors, User Guide section 1.6. Describes brute force, KD tree, and ball tree, and lists the auto conditions and their assumptions.
• Snapshot of the scikit-learn source: teaching/algo from scratch/knn/sklearn_knn.py, commit 6aa2f57c2b3820348f7cbba6e4f149c5208f59e2. Upstream: sklearn/neighbors/_base.py.
• scikit-learn developers. euclidean_distances. Documents the expansion of the Euclidean distance into dot products.
• Netlib. BLAS (Basic Linear Algebra Subprograms). Defines BLAS and its routines that multiply matrices.
• Wikipedia. Metric space. States the four rules of a metric.
• Wikipedia. Minkowski distance. Defines the family and shows that p < 1 breaks the triangle inequality.
• Wikipedia. Ball tree. Describes the pruning test that uses a centroid and a radius and cites Omohundro, S. M. (1989), Five Balltree Construction Algorithms, ICSI Technical Report TR-89-063.
• Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. (1999). When Is "Nearest Neighbor" Meaningful? ICDT 1999, pp. 217–235. Shows that the nearest and farthest distances become similar as the dimension increases.
• VanderPlas, J. (2013). Benchmarking Nearest Neighbor Searches in Python. Explains how the structure of the data affects the query time of a tree but not the query time of brute force.
• scikit-learn 1.8.0 source files read for section 7 and Figures 5.2, 7.2, 7.5, and 10.1: sklearn/neighbors/_binary_tree.pxi.tp (the shared build _recursive_build, find_node_split_dim, the level count, _query_single_depthfirst, and n_calls), sklearn/neighbors/_ball_tree.pyx.tp (init_node, min_dist), sklearn/neighbors/_kd_tree.pyx.tp (init_node, min_rdist), sklearn/neighbors/_partition_nodes.pyx (the median split with std::nth_element and its tie rule), sklearn/utils/_heap.pyx (heap_push), and sklearn/neighbors/_base.py (the selection rules).
• Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509–517. The original KD tree.
• Friedman, J. H., Bentley, J. L., and Finkel, R. A. (1977). An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3(3), 209–226. The KD-tree nearest-neighbor search with bound-based pruning.
• Spanjers, I. A. E., van Gog, T., and van Merriënboer, J. J. G. (2012). Segmentation of worked examples: Effects on cognitive load and learning. Applied Cognitive Psychology, 26(3), 352–358. Segmented worked examples gave the same learning with less effort.
• Margulieux, L. E., Catrambone, R., and Guzdial, M. (2016). Employing subgoals in computer programming education. Computer Science Education, 26(1), 44–67. Worked examples with subgoal labels helped students solve programming problems.
• Mayer, R. E. (2020). Multimedia Learning (3rd ed.). Cambridge University Press. The segmenting, signaling, and spatial-contiguity principles.
• Guo, P. J. (2013). Online Python Tutor: Embeddable web-based program visualization for CS education. SIGCSE 2013. Stepping through code while seeing its run-time state.
• The code in section 11, Python and Cython, is quoted from scikit-learn 1.8.0, copyright the scikit-learn developers, under the BSD 3-Clause License. assets/knn-search-method/trace_knn_calls.py records it.
• Numbers in sections 6, 7, 8, and 10 come from scripts run with scikit-learn 1.8.0 and NumPy 2.4.4. Figure 9.2 runs its own random sample in this page. verify_knn_lesson.py --export writes the trees, the BallTree trace, the table of leaf sizes, and the timings in Figure 9.4 into this page.
• Some subsections name a file and line in full, such as neighbors/_kd_tree.pyx.tp:145. Those citations point at the source files of the installed scikit-learn 1.8.0. Their timing tables were measured with scikit-learn 1.5.2 and NumPy 2.2.6 on another machine.
• cppreference. std::nth_element. States the guarantee that the median split relies on.
• Numba developers. Numba. The compiler used for the compiled-loop measurement in section 4.

Visual edition of the lesson sklearn_knn_search_method_selection.md.