@saehrimnir/druidjs / HNSW

Class: HNSW<T>

Defined in: knn/HNSW.js:61

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)

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

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?: ParametersHNSW): HNSW<T>;

Defined in: knn/HNSW.js:68

Creates a new HNSW index.

Parameters

Parameter	Type	Description
points	T[]	Initial points to add to the index
parameters?	ParametersHNSW	Configuration parameters

Returns

HNSW<T>

Overrides

KNN.constructor

Properties

Property	Type	Inherited from	Defined in
_ef	number	-	knn/HNSW.js:142
_ef_construction	number	-	knn/HNSW.js:135
_elements	T[]	KNN._elements	knn/KNN.js:14
_ep	number[] | null	-	knn/HNSW.js:161
_L	number	-	knn/HNSW.js:158
_m	number	-	knn/HNSW.js:128
_m0	number	-	knn/HNSW.js:149
_metric	Metric	-	knn/HNSW.js:108
_mL	number	-	knn/HNSW.js:152
_next_index	number	-	knn/HNSW.js:120
_parameters	ParametersHNSW	KNN._parameters	knn/KNN.js:16
_randomizer	Randomizer	-	knn/HNSW.js:155
_select	Function	-	knn/HNSW.js:111
_type	"array" | "typed"	KNN._type	knn/KNN.js:18

Accessors

num_layers

Get Signature

get num_layers(): number;

Defined in: knn/HNSW.js:710

Get the number of layers in the graph.

Returns

number

Number of layers

---

size

Get Signature

get size(): number;

Defined in: knn/HNSW.js:701

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:185

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:175

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:720

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:578

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): Candidate<T>[];

Defined in: knn/HNSW.js:731

Search for nearest neighbors using an element index as the query.

Parameters

Parameter	Type	Default value	Description
i	number	undefined	Index of the query element
K?	number	5	Number of nearest neighbors to return

Returns

Candidate<T>[]

K nearest neighbors

Overrides

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:660

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