@saehrimnir/druidjs / KDTree

Class: KDTree<T>

Defined in: knn/KDTree.js:36

KD-Tree (K-dimensional Tree) for efficient nearest neighbor search.

KD-Trees partition k-dimensional space by recursively splitting along coordinate axes. At each level, the tree splits points based on the median of the coordinate with the largest spread. This creates a balanced binary tree structure that enables efficient O(log n) search on average.

Best suited for:

• Low to moderate dimensional data (d < 20-30)
• When exact nearest neighbors are needed
• When dimensionality is not too high

Performance degrades in high dimensions (curse of dimensionality) where approximate methods like HNSW or LSH become more effective.

Template

See

https://en.wikipedia.org/wiki/K-d_tree

Extends

• KNN

Type Parameters

Type Parameter	Description
T extends number[] | Float64Array

Constructors

Constructor

new KDTree<T>(elements: T[], parameters?: ParametersKDTree): KDTree<T>;

Defined in: knn/KDTree.js:43

Generates a KD-Tree with given elements.

Parameters

Parameter	Type	Description
elements	T[]	Elements which should be added to the KD-Tree
parameters?	ParametersKDTree	Default is {metric: euclidean}

Returns

KDTree<T>

Overrides

KNN.constructor

Properties

Property	Type	Inherited from	Defined in
_elements	T[]	KNN._elements	knn/KNN.js:14
_parameters	ParametersKDTree	KNN._parameters	knn/KNN.js:16
_type	"array" | "typed"	KNN._type	knn/KNN.js:18

Accessors

_metric

Get Signature

get _metric(): Metric;

Defined in: knn/KDTree.js:56

Returns

Metric

Methods

search()

search(t: T, k?: number): {
  distance: number;
  element: T;
  index: number;
}[];

Defined in: knn/KDTree.js:106

Parameters

Parameter	Type	Default value	Description
t	T	undefined	Query element.
k?	number	5	Number of nearest neighbors to return. Default is 5

Returns

{ distance: number; element: T; index: number; }[]

• List consists of the k nearest neighbors.

Overrides

KNN.search

---

search_by_index()

search_by_index(i: number, k?: number): {
  distance: number;
  element: T;
  index: number;
}[];

Defined in: knn/KDTree.js:97

Parameters

Parameter	Type	Default value	Description
i	number	undefined	-
k	number	5	-

Returns

{ distance: number; element: T; index: number; }[]

Overrides

KNN.search_by_index