KDTree<T>

Models & Types · AiDotNet.Clustering.SpatialIndex

K-dimensional tree for efficient nearest neighbor queries.

For Beginners

A KD-Tree is like a special way of organizing data points so you can quickly find nearby points.

Imagine organizing a phone book not just by last name, but alternating between first name and last name at each level. This lets you narrow down your search very quickly.

KD-Trees are used in:

  • DBSCAN clustering (to find points within epsilon radius)
  • K-Nearest Neighbors (KNN) classification
  • Range searches (find all points in a region)

How It Works

KD-Tree is a space-partitioning data structure for organizing points in k-dimensional space. It enables efficient nearest neighbor searches in O(log n) average case, compared to O(n) for brute-force search.

Constructors

Constructor Summary
KDTree(IDistanceMetric<T> distanceMetric, int leafSize) Initializes a new KD-Tree instance.

Properties

Property Summary
int Count { get; } Gets the number of points in the tree.
int Dimensions { get; } Gets the number of dimensions.

Methods

Method Summary
ValueTuple<int, T>[] QueryKNearest(Vector<T> query, int k) Finds the k nearest neighbors to the query point.
ValueTuple<int, T>[] QueryRadius(Vector<T> query, T radius) Finds all points within the given radius of the query point.
int[] QueryRadiusIndices(Vector<T> query, T squaredRadius) Finds all points within the given squared radius of the query point.
void Build(Matrix<T> data) Builds the KD-Tree from the given data.