A KD-tree, k-dimensional tree, recursively partitions space into nested regions, organizing points so that a nearest-neighbor query can eliminate large portions of the search space at once rather than computing the distance to every single point — for a well-balanced tree, this reduces a typical nearest-neighbor search from checking every point down to roughly logarithmic time. Once built, the tree's .query() method finds the nearest point, or the k nearest points, to a given query location efficiently.
1Understanding spatial.KDTree()
A KD-tree, k-dimensional tree, recursively partitions space into nested regions, organizing points so that a nearest-neighbor query can eliminate large portions of the search space at once rather than computing the distance to every single point — for a well-balanced tree, this reduces a typical nearest-neighbor search from checking every point down to roughly logarithmic time. Once built, the tree's .query() method finds the nearest point, or the k nearest points, to a given query location efficiently.
Build a KDTree once and reuse it for many queries — the tree-building step itself takes some upfront time, but it pays off quickly once you need to run more than a handful of nearest-neighbor searches against the same fixed set of points.
from scipy.spatial import KDTree
import numpy as np
points = np.array([[0, 0], [5, 5], [9, 9], [1, 1]])
tree = KDTree(points)
distance, index = tree.query([0.5, 0.5])
print(distance, index)2Practical Example
Here is a real-world application of spatial.KDTree() showing how it is used in production SciPy code.
from scipy.spatial import KDTree
import numpy as np
points = np.array([[0, 0], [5, 5], [9, 9], [1, 1]])
tree = KDTree(points)
distances, indices = tree.query([0.5, 0.5], k=2)
print(indices)3Best Practices
Follow these guidelines when working with spatial.KDTree():
1. Use KDTree.query() for nearest-neighbor lookups instead of manually computing distances to every point and finding the minimum yourself
2. Build the tree once and reuse it across many queries, rather than rebuilding it for each individual lookup
3. Pass k greater than 1 to query() when you need the several nearest neighbors at once, rather than calling query() repeatedly
Tip: Build a KDTree once and reuse it for many queries — the tree-building step itself takes some upfront time, but it pays off quickly once you need to run more than a handful of nearest-neighbor searches against the same fixed set of points.
from scipy.spatial import KDTree
import numpy as np
points = np.array([[0, 0], [5, 5], [9, 9], [1, 1]])
tree = KDTree(points)
distance, index = tree.query([0.5, 0.5])
print(distance, index)