Skip to content

fastspatial.kdtree.KDTree

Exact k-nearest-neighbor index for fixed-dimensional points.

KDTree stores a finite float64 point matrix shaped (n_points, n_dims) and answers exact Euclidean nearest-neighbor queries. Returned indices always refer to rows in the original input array.

Parameters:

Name Type Description Default
data NDArray[float64]

Finite float64 array shaped (n_points, n_dims).

 required
leafsize int

Number of points at which the tree switches to scanning a leaf directly. Must be positive.

 16

Raises:

Type Description
ValueError

If data is empty, has zero dimensions, contains non-finite values, or if leafsize is not positive.

leafsize property

Leaf size used when the tree was built.

n_dims property

Dimensionality of each stored point.

n_points property

Number of points stored in the tree.

__init__(data, leafsize=16)

Build a tree over data.

knn(query, k)

Return exact nearest neighbors for one query point.

Parameters:

Name Type Description Default
query NDArray[float64]

Finite float64 query point shaped (n_dims,).

 required
k int

Number of neighbors to return. Values larger than n_points are capped to the number of stored points.

 required

Returns:

Type Description
list[int]

A pair (indices, distances). indices is a list of source row
list[float]

indices and distances is a list of Euclidean distances. Both
tuple[list[int], list[float]]

lists are sorted nearest-first.

Raises:

Type Description
ValueError

If the query dimensionality does not match the tree or if the query contains non-finite values.

knn_many(queries, k)

Return exact nearest neighbors for a batch of query points.

Use this method for throughput-oriented workloads. It runs the native batch query path and returns row-major result arrays.

Parameters:

Name Type Description Default
queries NDArray[float64]

Finite float64 array shaped (n_queries, n_dims).

 required
k int

Number of neighbors to return for each query. Values larger than n_points are capped to the number of stored points.

 required

Returns:

Type Description
NDArray[int64]

A pair (indices, distances). Each array is shaped
NDArray[float64]

(n_queries, effective_k) and sorted nearest-first within each
tuple[NDArray[int64], NDArray[float64]]

row.

Raises:

Type Description
ValueError

If query dimensionality does not match the tree or if any query value is non-finite.

knn_profile(query, k)

Return nearest neighbors plus internal traversal counters.

This diagnostic method is intended for benchmark analysis and query tuning. The neighbor results match knn(query, k).

Parameters:

Name Type Description Default
query NDArray[float64]

Finite float64 query point shaped (n_dims,).

 required
k int

Number of neighbors to return.

 required

Returns:

Type Description
list[int]

(indices, distances, stats) where stats exposes internal
list[float]

traversal counters such as visited leaves, scanned points, and
KNNQueryStats

bounding-box evaluations.