@saehrimnir/druidjs / BallTree

Class: BallTree<T>

Defined in: knn/BallTree.js:33

Ball Tree for efficient nearest neighbor search.

A Ball Tree is a metric tree that partitions points into a nested set of hyperspheres (balls). It is particularly effective for high-dimensional data and supports any valid metric.

Every ball stores a center and the distance from it to its furthest member, which bounds the subtree from below by d(t, center) - radius. That bound holds for any metric by the triangle inequality, so the center does not need to be one of the indexed points — it is the centroid, which keeps radii tighter than an arbitrary member would.

Template

T

Extends

• KNN

Type Parameters

Type Parameter	Description
T extends number[] | Float64Array

Constructors

Constructor

new BallTree<T>(elements: T[], parameters?: Partial<ParametersBallTree>): BallTree<T>;

Defined in: knn/BallTree.js:43

Generates a BallTree with given elements.

Parameters

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

Returns

BallTree<T>

See

• https://en.wikipedia.org/wiki/Ball_tree
• https://github.com/invisal/noobjs/blob/master/src/tree/BallTree.js

Overrides

KNN.constructor

Properties

Property	Type	Description	Inherited from	Defined in
_elements	T[]	-	KNN._elements	knn/KNN.js:16
_parameters	ParametersBallTree	-	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/BallTree.js:53

Returns

Metric

Methods

search()

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

Defined in: knn/BallTree.js:134

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