KD-Tree for nearest neighbors in SciPy - Step-by-Step Execution

Concept Flow - KD-Tree for nearest neighbors

Start with data points

↓

Build KD-Tree from points

↓

Query KD-Tree with target point

↓

Traverse tree to find nearest neighbors

↓

Return nearest neighbor indices and distances

↓

End

We start with data points, build a KD-Tree, then query it with a target point to find nearest neighbors efficiently.

Execution Sample

SciPy

from scipy.spatial import KDTree
points = [[1,2], [3,4], [5,6], [7,8]]
tree = KDTree(points)
dist, idx = tree.query([4,4], k=2)
print(idx, dist)

This code builds a KD-Tree from 4 points and finds the 2 nearest neighbors to point [4,4].

Execution Table

Step	Action	Input/State	Output/Result
1	Create points list	[[1,2], [3,4], [5,6], [7,8]]	Points stored
2	Build KD-Tree	Points list	KD-Tree structure created
3	Query KD-Tree	Target point [4,4], k=2	Search starts at root
4	Traverse tree	Compare target to node splits	Check left/right branches
5	Find nearest neighbors	Distances calculated	Nearest indices [1, 2], distances [1.0, 2.236]
6	Return results	Indices and distances	Output printed: [1 2] [1.00000000 2.23606798]

💡 Nearest neighbors found and returned after tree traversal

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 5	Final
points	None	[[1,2], [3,4], [5,6], [7,8]]	[[1,2], [3,4], [5,6], [7,8]]	[[1,2], [3,4], [5,6], [7,8]]	[[1,2], [3,4], [5,6], [7,8]]	[[1,2], [3,4], [5,6], [7,8]]
tree	None	None	KDTree object	KDTree object	KDTree object	KDTree object
target_point	None	None	None	[4,4]	[4,4]	[4,4]
idx	None	None	None	None	[1, 2]	[1, 2]
dist	None	None	None	None	[1.00000000, 2.23606798]	[1.00000000, 2.23606798]

Key Moments - 3 Insights

Why does the KD-Tree traversal check both left and right branches sometimes?

Because the nearest neighbor might be on the other side of the split, so the algorithm checks both branches if needed, as shown in step 4 of the execution_table.

What does the 'k' parameter in tree.query control?

It controls how many nearest neighbors to find. In the example, k=2 means the two closest points are returned, as seen in step 3 and 5.

Why are distances returned along with indices?

Distances tell how far each neighbor is from the target point, helping understand closeness, as shown in step 5 and 6.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what are the indices of the nearest neighbors found?

A [0, 1]

B [1, 2]

C [2, 3]

D [3, 2]

💡 Hint

Check the 'Output/Result' column at step 5 in the execution_table.

At which step does the KD-Tree get built from the points?

A Step 3

B Step 1

C Step 2

D Step 4

💡 Hint

Look for the action 'Build KD-Tree' in the execution_table.

If we change k=1 in the query, how would the 'idx' variable change after step 5?

A It would be a single index of the closest neighbor

B It would be the same two indices

C It would be empty

D It would contain all points

💡 Hint

Refer to the 'key_moments' about the meaning of 'k' and the 'variable_tracker' for 'idx'.

Concept Snapshot

KD-Tree for nearest neighbors:
- Build tree with KDTree(points)
- Query with tree.query(target, k)
- Returns indices and distances of k closest points
- Efficient for multi-dimensional nearest neighbor search
- Checks tree branches to find closest points

Full Transcript

We start with a list of points and build a KD-Tree from them. Then, we query the tree with a target point and a number k to find the k nearest neighbors. The tree is traversed by comparing the target to node splits, sometimes checking both branches to ensure the closest points are found. The query returns the indices of the nearest neighbors and their distances from the target. This process is efficient for searching neighbors in multi-dimensional data.