@saehrimnir/druidjs / KDTree

Class: KDTree<T>

Defined in: knn/KDTree.js:37

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

T

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?: Partial<ParametersKDTree>): KDTree<T>;

Defined in: knn/KDTree.js:45

Generates a KD-Tree with given elements.

Parameters

Parameter	Type	Description
elements	T[]	Elements which should be added to the KD-Tree
parameters?	Partial<ParametersKDTree>	Anything left out falls back to the documented default.

Returns

KDTree<T>

Overrides

KNN.constructor

Properties

Property	Type	Description	Inherited from	Defined in
_elements	T[]	-	KNN._elements	knn/KNN.js:16
_parameters	ParametersKDTree	-	KNN._parameters	knn/KNN.js:18
_randomizer	Randomizer	Seeded source of randomness shared by every index. Construction is randomized — the trees pick quickselect pivots from it — so the seed parameter is what makes a built index, and therefore its query results, reproducible.	KNN._randomizer	knn/KNN.js:28
_type	"array" | "typed"	-	KNN._type	knn/KNN.js:20

Accessors

_metric

Get Signature

get _metric(): Metric;

Defined in: knn/KDTree.js:58

Returns

Metric

Methods

search()

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

Defined in: knn/KDTree.js:100

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/KNN.js:77

Searches the k nearest neighbors of the element stored at index i.

The queried element is never part of the result. It is trivially its own closest neighbor at distance 0, which is never what a caller asking "what is this point near?" wants, so every caller used to strip it back out — each in its own, subtly different way. Note the asymmetry with search: an arbitrary query point has no "self" to exclude, so there k means "k results", while here it means "k neighbors".

The self match is removed by index — not by position, and not by looking for a zero distance. Position is wrong because an approximate index may order ties differently or miss the element altogether (one extra candidate is requested to cover that), and a zero distance is wrong because genuine duplicate points share it and must survive.

Parameters

Parameter	Type	Default value	Description
i	number	undefined	Index of the query element.
k?	number	5	Number of neighbors to return. Default is 5

Returns

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

The k nearest other elements, closest first. Empty when i is out of range.

Inherited from

KNN.search_by_index