@saehrimnir/druidjs / HNSW

Class: HNSW<T>

Defined in: knn/HNSW.js:65

Hierarchical Navigable Small World (HNSW) graph for approximate nearest neighbor search.

HNSW builds a multi-layer graph structure where each layer is a navigable small world graph. The top layers serve as "highways" for fast traversal, while lower layers provide accuracy. Each element is assigned to a random level, allowing logarithmic search complexity.

Key parameters:

• m: Controls the number of connections per element (affects accuracy/memory)
• ef_construction: Controls the quality of the graph during construction (higher = better but slower)
• ef: Controls the quality of search (higher = better recall but slower)

This is an approximate index. Recall above 95% is expected for any m; raise ef or ef_construction if a dataset needs more. Queries overtake the exact KDTree at around 10 000 points, so below a few thousand prefer spatial_tree, which is exact and quicker.

Based on:

• "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs" by Malkov & Yashunin (2016)
• "Approximate Nearest Neighbor Search on High Dimensional Data" by Li et al. (2019)

Template

T

Example

import * as druid from "@saehrimnir/druidjs";

const points = [[1, 2], [3, 4], [5, 6], [7, 8]];
const hnsw = new druid.HNSW(points, {
    metric: druid.euclidean,
    m: 16,
    ef_construction: 200
});

const query = [2, 3];
const neighbors = hnsw.search(query, 2);
// [{ element: [1, 2], index: 0, distance: 1.41 }, ...]

Extends

• KNN

Type Parameters

Type Parameter	Description
T extends number[] | Float64Array

Constructors

Constructor

new HNSW<T>(points: T[], parameters?: Partial<ParametersHNSW>): HNSW<T>;

Defined in: knn/HNSW.js:73

Creates a new HNSW index.

Parameters

Parameter	Type	Description
points	T[]	Initial points to add to the index
parameters?	Partial<ParametersHNSW>	Anything left out falls back to the documented default.

Returns

HNSW<T>

Overrides

KNN.constructor

Properties

Property	Type	Description	Inherited from	Defined in
_ef	number	-	-	knn/HNSW.js:152
_ef_construction	number	-	-	knn/HNSW.js:145
_elements	T[]	-	KNN._elements	knn/KNN.js:16
_ep	number[] | null	-	-	knn/HNSW.js:171
_L	number	-	-	knn/HNSW.js:168
_m	number	-	-	knn/HNSW.js:138
_m0	number	-	-	knn/HNSW.js:159
_metric	Metric	-	-	knn/HNSW.js:118
_mL	number	-	-	knn/HNSW.js:162
_next_index	number	-	-	knn/HNSW.js:130
_parameters	ParametersHNSW	-	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
_select	Function	-	-	knn/HNSW.js:121
_type	"array" | "typed"	-	KNN._type	knn/KNN.js:20

Accessors

num_layers

Get Signature

get num_layers(): number;

Defined in: knn/HNSW.js:688

Get the number of layers in the graph.

Returns

number

Number of layers

---

size

Get Signature

get size(): number;

Defined in: knn/HNSW.js:679

Get the number of elements in the index.

Returns

number

Number of elements

Methods

add()

add(new_elements: T[]): HNSW<T>;

Defined in: knn/HNSW.js:201

Add multiple elements to the index.

Parameters

Parameter	Type	Description
new_elements	T[]	Elements to add

Returns

HNSW<T>

This instance for chaining

---

addOne()

addOne(element: T): HNSW<T>;

Defined in: knn/HNSW.js:191

Add a single element to the index.

Parameters

Parameter	Type	Description
element	T	Element to add

Returns

HNSW<T>

This instance for chaining

---

get_element()

get_element(index: number): T;

Defined in: knn/HNSW.js:698

Get an element by its index.

Parameters

Parameter	Type	Description
index	number	Element index

Returns

T

The element at the given index

---

search()

search(q: T, K: number): Candidate<T>[];

Defined in: knn/HNSW.js:556

Searches for the K nearest neighbors to a query element in the HNSW graph.

Performs a multi-layer search starting from the entry point and traversing each layer as entry points for the next.

Parameters

Parameter	Type	Description
q	T	Query element
K	number	Number of nearest neighbors to return

Returns

Candidate<T>[]

K nearest neighbors with their distances

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

---

search_iter()

search_iter(
   q: T, 
   K: number, 
   ef?: number | null): Generator<{
  candidates: {
     distance: number;
     element: T;
     index: number;
  }[];
  layer: number;
}, void, unknown>;

Defined in: knn/HNSW.js:638

Iterator for searching the HNSW graph layer by layer.

Yields intermediate results at each layer for debugging or visualization.

Parameters

Parameter	Type	Default value	Description
q	T	undefined	Query element
K	number	undefined	Number of nearest neighbors to return
ef?	number | null	null	Size of dynamic candidate list

Returns

Generator<{ candidates: { distance: number; element: T; index: number; }[]; layer: number; }, void, unknown>

Yields