Categories &

Functions List

Class Definition: hnswSearcher

statistics: hnswSearcher

Hierarchical Navigable Small World (HNSW) nearest neighbor searcher class.

The hnswSearcher class implements the HNSW algorithm for efficient nearest neighbor queries. It stores training data and supports various distance metrics for performing searches. The HNSW algorithm builds a multilayer graph structure that enables fast approximate nearest neighbor searches by navigating through the graph. It facilitates nearest neighbor queries search using knnsearch.

You can either use the hnswSearcher class constructor or the createns function to create an hnswSearcher object.

See also: createns, ExhaustiveSearcher, KDTreeSearcher, knnsearch

Source Code: hnswSearcher

The hnswSearcher class contains the following properties:

Distance metric used for searches, specified as a character vector (e.g., 'euclidean', 'minkowski', 'cityblock'). Default is 'euclidean'. Supported metrics align with those in pdist2. This property is private and cannot be modified after object creation.

Create an hnswSearcher with Euclidean distance

 X = [1, 2; 3, 4; 5, 6];
 obj = hnswSearcher (X);

Find the nearest neighbor to [2, 3]

 Y = [2, 3];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
1.4142

Create an hnswSearcher with Minkowski distance (P=3)

 X = [0, 0; 1, 0; 2, 0];
 obj = hnswSearcher (X, 'Distance', 'minkowski', 'P', 3);

Find the nearest neighbor to [1, 0]

 Y = [1, 0];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
0

The type and value of the distance parameter depends on the selected Distance metric and can be any of the following:

  • For 'minkowski', a positive scalar exponent (default 2).
  • For 'seuclidean', a nonnegative vector of scaling factors matching the number of columns in X (default is standard deviation of X).
  • For 'mahalanobis', a positive definite covariance matrix matching the dimensions of X (default is cov (X)).
  • Empty for other metrics.

This property is private and cannot be modified after object creation.

Create an hnswSearcher with Euclidean distance

 X = [1, 2; 3, 4; 5, 6];
 obj = hnswSearcher (X);

Find the nearest neighbor to [2, 3]

 Y = [2, 3];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
1.4142

Create an hnswSearcher with Minkowski distance (P=3)

 X = [0, 0; 1, 0; 2, 0];
 obj = hnswSearcher (X, 'Distance', 'minkowski', 'P', 3);

Find the nearest neighbor to [1, 0]

 Y = [1, 0];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
0

Maximum number of neighbors per node in the HNSW graph. Affects graph connectivity and search accuracy. Default value is 16. This property is private and cannot be modified after object creation.

Create an hnswSearcher with Euclidean distance

 X = [1, 2; 3, 4; 5, 6];
 obj = hnswSearcher (X);

Find the nearest neighbor to [2, 3]

 Y = [2, 3];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
1.4142

Create an hnswSearcher with Minkowski distance (P=3)

 X = [0, 0; 1, 0; 2, 0];
 obj = hnswSearcher (X, 'Distance', 'minkowski', 'P', 3);

Find the nearest neighbor to [1, 0]

 Y = [1, 0];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
0

Size of the dynamic candidate list during graph construction. Higher values improve accuracy at the cost of construction time. Default value is 200. This property is private and cannot be modified after object creation.

Create an hnswSearcher with Euclidean distance

 X = [1, 2; 3, 4; 5, 6];
 obj = hnswSearcher (X);

Find the nearest neighbor to [2, 3]

 Y = [2, 3];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
1.4142

Create an hnswSearcher with Minkowski distance (P=3)

 X = [0, 0; 1, 0; 2, 0];
 obj = hnswSearcher (X, 'Distance', 'minkowski', 'P', 3);

Find the nearest neighbor to [1, 0]

 Y = [1, 0];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
0

Point data, specified as an N×P numeric matrix where each row is an observation and each column is a feature. This property is private and cannot be modified after object creation.

Data of class single is stored and searched in single precision, any other numeric class is converted to double.

Create an hnswSearcher with Euclidean distance

 X = [1, 2; 3, 4; 5, 6];
 obj = hnswSearcher (X);

Find the nearest neighbor to [2, 3]

 Y = [2, 3];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
1.4142

Create an hnswSearcher with Minkowski distance (P=3)

 X = [0, 0; 1, 0; 2, 0];
 obj = hnswSearcher (X, 'Distance', 'minkowski', 'P', 3);

Find the nearest neighbor to [1, 0]

 Y = [1, 0];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
0

The hnswSearcher class offers the following public methods:

hnswSearcher: obj = hnswSearcher (X)
hnswSearcher: obj = hnswSearcher (X, name, value)

obj = hnswSearcher (X) constructs an hnswSearcher object with training data X using the default 'euclidean' distance metric. X must be an N×P numeric matrix, where rows represent observations and columns represent features.

obj = hnswSearcher (X, name, value) allows customization through name-value pairs:

NameValue
'Distance'Distance metric, specified as a character vector (e.g., 'euclidean', 'minkowski', 'cityblock'). Default is 'euclidean'. See pdist2 for supported metrics.
'P'Minkowski distance exponent, a positive scalar. Valid only when 'Distance' is 'minkowski'. Default is 2.
'Scale'Nonnegative vector of scaling factors matching the number of columns in X. Valid only when 'Distance' is 'seuclidean'. Default is std (X).
'Cov'Positive definite covariance matrix matching the number of columns in X. Valid only when 'Distance' is 'mahalanobis'. Default is cov (X).
'MaxNumLinksPerNode'Maximum number of neighbors per node in the HNSW graph, a positive integer. Default is 16.
'TrainSetSize'Size of the dynamic candidate list during graph construction, a positive integer. Default is 200.

See also: hnswSearcher, knnsearch, createns, pdist2

Create an hnswSearcher with Euclidean distance

 X = [1, 2; 3, 4; 5, 6];
 obj = hnswSearcher (X);

Find the nearest neighbor to [2, 3]

 Y = [2, 3];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
1.4142

Create an hnswSearcher with Minkowski distance (P=3)

 X = [0, 0; 1, 0; 2, 0];
 obj = hnswSearcher (X, 'Distance', 'minkowski', 'P', 3);

Find the nearest neighbor to [1, 0]

 Y = [1, 0];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
0
hnswSearcher: [idx, D] = knnsearch (obj, Y)
hnswSearcher: [idx, D] = knnsearch (obj, Y, name, value)

[idx, D] = knnsearch (obj, Y) returns the indices idx and distances D of the nearest neighbor in obj.X to each point in Y, using the distance metric specified in obj.Distance.

  • obj is an hnswSearcher object.
  • Y is an M×P numeric matrix of query points, where P must match the number of columns in obj.X.
  • idx contains the indices of the nearest neighbors in obj.X.
  • D contains the corresponding distances.

idx is always of class double. D is of class single when either obj.X or Y is single, in which case the distances are computed in single precision, and of class double otherwise.

[idx, D] = knnsearch (obj, Y, name, value) allows additional options via name-value pairs:

NameValue
'K'A positive integer specifying the number of nearest neighbors to find. Default is 1. A value larger than the number of observations in the training data is answered with all of them, since there are no more neighbors to return.
'SearchSetSize'A positive integer specifying the size of the candidate list of nearest neighbors for a single query point during the search process. Default is max (10, C), where C is the number of columns in obj.X. 'SearchSetSize' must be at least C and no more than the number of rows in training data obj.X.

See also: hnswSearcher, pdist2

Create an hnswSearcher with Euclidean distance

 X = [1, 2; 3, 4; 5, 6];
 obj = hnswSearcher (X);

Find the nearest neighbor to [2, 3]

 Y = [2, 3];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
1.4142

Create an hnswSearcher with Minkowski distance (P=3)

 X = [0, 0; 1, 0; 2, 0];
 obj = hnswSearcher (X, 'Distance', 'minkowski', 'P', 3);

Find the nearest neighbor to [1, 0]

 Y = [1, 0];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
0

Examples 

 X = [1, 2; 3, 4; 5, 6];
 obj = hnswSearcher (X);

Find the nearest neighbor to [2, 3]

 Y = [2, 3];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
1.4142
 X = [0, 0; 1, 0; 2, 0];
 obj = hnswSearcher (X, 'Distance', 'minkowski', 'P', 3);

Find the nearest neighbor to [1, 0]

 Y = [1, 0];
 [idx, D] = knnsearch (obj, Y, 'K', 1);
 disp ('Nearest neighbor index:');
Nearest neighbor index:
 disp (idx);
2
 disp ('Distance:');
Distance:
 disp (D);
0