@saehrimnir/druidjs / NNDescent

Class: NNDescent<T>

Defined in: knn/NNDescent.js:38

NN-Descent

An efficient graph-based approximate nearest neighbor search algorithm. It works by iteratively improving a neighbor graph using the fact that "neighbors of neighbors are likely to be neighbors".

Template

T

See

Paper

Extends

• KNN

Type Parameters

Type Parameter	Description
T extends number[] | Float64Array

Constructors

Constructor

new NNDescent<T>(elements: T[], parameters?: Partial<ParametersNNDescent>): NNDescent<T>;

Defined in: knn/NNDescent.js:56

Parameters

Parameter	Type	Description
elements	T[]	Called V in paper.
parameters?	Partial<ParametersNNDescent>	Anything left out falls back to the documented default.

Returns

NNDescent<T>

See

http://www.cs.princeton.edu/cass/papers/www11.pdf

Overrides

KNN.constructor

Properties

Property	Type	Inherited from	Defined in
_elements	T[]	KNN._elements	knn/KNN.js:16
_N	number	-	knn/NNDescent.js:65
_nndescent_elements	{ flag: boolean; index: number; value: T; }[]	-	knn/NNDescent.js:69
_parameters	ParametersNNDescent	KNN._parameters	knn/KNN.js:18
_randomizer	Randomizer	KNN._randomizer	knn/NNDescent.js:66
_sample_size	number	-	knn/NNDescent.js:67
_type	"array" | "typed"	KNN._type	knn/KNN.js:20

Methods

add()

add(elements: T[]): NNDescent<T>;

Defined in: knn/NNDescent.js:177

Parameters

Parameter	Type	Description
elements	T[]	-

Returns

NNDescent<T>

---

search()

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

Defined in: knn/NNDescent.js:252

Parameters

Parameter	Type	Default value	Description
x	T	undefined	-
k?	number	5	Default is 5

Returns

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

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