@saehrimnir/druidjs / NaiveKNN

Class: NaiveKNN<T>

Defined in: knn/NaiveKNN.js:29

Naive KNN implementation performing an exhaustive scan.

Every query measures the distance to all N elements and then selects the k smallest with quickselect, which is O(N) on average — cheaper than sorting all N and far cheaper than the N heaps of N entries this class used to build up front.

The N x N distance matrix is only materialized when it actually pays off: a "precomputed" index is handed one directly, and NaiveKNN#search_by_index builds one lazily on first use so that building a whole kNN graph costs a single pass over the pairs instead of one per query. Callers that only ever use NaiveKNN#search never allocate it.

Best suited for small datasets, or when a distance matrix is already available. For larger N prefer an approximate index such as HNSW, Annoy, or NNDescent.

Template

T

Extends

• KNN

Type Parameters

Type Parameter	Description
T extends number[] | Float64Array

Constructors

Constructor

new NaiveKNN<T>(elements: T[], parameters?: Partial<ParametersNaiveKNN>): NaiveKNN<T>;

Defined in: knn/NaiveKNN.js:51

Generates a KNN list with given elements.

Parameters

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

Returns

NaiveKNN<T>

Overrides

KNN.constructor

Properties

Property	Type	Description	Inherited from	Defined in
_D	Matrix | null	Pairwise distances. Supplied by the caller when metric is "precomputed", built on demand by NaiveKNN#search_by_index otherwise, and null until then.	-	knn/NaiveKNN.js:42
_elements	T[]	-	KNN._elements	knn/KNN.js:16
_N	number	Number of indexed elements.	-	knn/NaiveKNN.js:35
_parameters	ParametersNaiveKNN	-	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

Methods

search()

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

Defined in: knn/NaiveKNN.js:149

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/NaiveKNN.js:139

Overrides the base search_by_index, which reaches the elements through NaiveKNN#search. That is not available on a "precomputed" index, and it would also throw away the distance matrix this class already holds. The self-exclusion contract is identical.

Parameters

Parameter	Type	Default value	Description
i	number	undefined	Index of the query element.
k?	number	5	Number of nearest 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.

Overrides

KNN.search_by_index