Nearest-neighbor search
Repeated nearest-neighbor lookups for coordinates in a geometric or scientific dataset.
SciPy · Class
spatial.KDTree
KDTree indexes k-dimensional points for fast nearest-neighbor and related spatial queries. It supports exact or approximate searches, radius-based searches, pair counting, and periodic domains.
How it works
KDTree indexes k-dimensional points by recursively partitioning their space into axis-aligned regions. After construction, its query methods search that index for exact or approximate nearest neighbors and can also find points or point pairs within distance limits.
Syntax
scipy.spatial.KDTree(data, leafsize=10, compact_nodes=True, copy_data=False, balanced_tree=True, boxsize=None)Parameters
| Name | Type | Description |
|---|---|---|
data | array_like | Input points with shape (n, m), where n is the number of points and m is their dimensionality. |
leafsize | int, optional | Number of points at which the algorithm switches to brute-force processing; must be positive. |
compact_nodes | bool, optional | Shrink hyperrectangles to the actual data range; this can improve query performance but may increase construction time. |
copy_data | bool, optional | Copy the input data instead of retaining a reference when possible. |
balanced_tree | bool, optional | Use the median to build a balanced tree; otherwise use the midpoint of the bounding interval. |
boxsize | array_like or scalar, optional | Box lengths for periodic, toroidal topology; input coordinates must lie in [0, boxsize). |
Returns
A KDTree object indexing the supplied points.
Key points
- Constructing a KDTree creates an index over k-dimensional data for repeated spatial searches.
- The data structure is binary and recursively partitions the search space.
- Every node corresponds to an axis-aligned hyperrectangle that bounds part of the data.
- Query operations can return a requested number of closest points.
- Nearest-neighbor queries can impose a distance ceiling.
- Approximate nearest-neighbor queries can improve efficiency when exact results are unnecessary.
Example: Nearest-neighbor lookup
import numpy as np
from scipy.spatial import KDTree
points = np.array([[0, 0], [1, 1], [3, 3]])
tree = KDTree(points)
distance, index = tree.query([0.8, 0.9])
print(index, distance)Builds a tree over 2-D points and finds the nearest point to a query coordinate.
When to use it
Radius queries
Finding all indexed points inside a radius around one or many query points.
Periodic spatial domains
Searching spatial data whose coordinates wrap around at fixed domain boundaries.
Sparse distance construction
Computing sparse proximity relationships between two point sets.
Interview questions
QHow does KDTree accelerate nearest-neighbor lookup?
KDTree stores k-dimensional points in a binary tree whose nodes represent axis-aligned hyperrectangles. Splitting by coordinate partitions the search space, allowing nearest-neighbor queries to avoid examining every point in favorable cases.
Follow-up: What does leafsize control? It sets the point count at which the algorithm switches to brute-force processing, trading tree overhead against local scan work.
QWhat is leafsize and why would you tune it?
leafsize is the number of points at which the algorithm switches to brute-force. A smaller value creates more tree structure, while a larger value leaves more work for direct scans.
Follow-up: Why might the best value depend on the workload? Build cost, query count, dimensionality, and point distribution affect the balance between traversal and brute-force scans.
QWhat does boxsize do?
boxsize applies a toroidal topology to the indexed coordinates. The input data must already lie within the half-open interval from zero to the corresponding box-size value.
Follow-up: How can periodicity change a nearest-neighbor result? A point near one boundary can be close to a point near the opposite boundary through wraparound.
Related
scipy.spatial.cKDTreequeryquery_ball_pointquery_ball_treequery_pairscount_neighborssparse_distance_matrix