K-d Tree#

A multi-dimensional binary search tree for fast nearest neighbor queries. The K-d tree construction algorithm separates data points into bounded hypercubes or bounding boxes that are used to prune off nodes during nearest neighbor and range searches.

Interfaces: Tree, Binary Tree, BST, Spatial

Data Type Compatibility: Continuous


# Param Default Type Description
1 max leaf size 30 int The maximum number of samples that each leaf node can contain.
2 kernel Euclidean object The distance kernel used to compute the distance between sample points.

Additional Methods#

Return the path of a sample taken from the root node to a leaf node in an array.

public path(array $sample) : array


use Rubix\ML\Graph\Trees\KDTree;
use Rubix\ML\Kernels\Distance\Euclidean;

$tree = new KDTree(30, new Euclidean());


  • J. L. Bentley. (1975). Multidimensional Binary Seach Trees Used for Associative Searching.