@saehrimnir/druidjs / LSH

Class: LSH<T>

Defined in: knn/LSH.js:34

Locality Sensitive Hashing (LSH) for approximate nearest neighbor search.

LSH uses hash functions that map similar items to the same buckets with high probability. This implementation uses the p-stable scheme of Datar et al. for Euclidean distance: each hash projects onto a Gaussian random vector and quantizes the result into buckets of width w.

Key concepts:

• Multiple hash tables increase recall probability
• Each hash function projects data onto a random Gaussian direction
• Points landing in the same quantization bucket are hashed together
• Combines results from all tables for better accuracy

Best suited for:

• High-dimensional data where exact methods fail
• Approximate nearest neighbor needs
• Large datasets where linear scan is too slow
• When some false positives/negatives are acceptable

Template

T

See

https://en.wikipedia.org/wiki/Locality-sensitive_hashing

Extends

• KNN

Type Parameters

Type Parameter	Description
T extends number[] | Float64Array

Constructors

Constructor

new LSH<T>(elements: T[], parameters?: Partial<ParametersLSH>): LSH<T>;

Defined in: knn/LSH.js:42

Creates a new LSH index.

Parameters

Parameter	Type	Description
elements	T[]	Elements to index
parameters?	Partial<ParametersLSH>	Anything left out falls back to the documented default.

Returns

LSH<T>

Overrides

KNN.constructor

Properties

Property	Type	Inherited from	Defined in
_bucketWidth	number	-	knn/LSH.js:82
_dim	number	-	knn/LSH.js:78
_elements	T[]	KNN._elements	knn/KNN.js:16
_hashTables	Map<string, number[]>[]	-	knn/LSH.js:66
_metric	Metric	-	knn/LSH.js:58
_numHashFunctions	number	-	knn/LSH.js:60
_numHashTables	number	-	knn/LSH.js:59
_offsets	number[][]	-	knn/LSH.js:74
_parameters	ParametersLSH	KNN._parameters	knn/KNN.js:18
_projections	Float64Array<ArrayBufferLike>[][]	-	knn/LSH.js:70
_randomizer	Randomizer	KNN._randomizer	knn/LSH.js:62
_seed	number	-	knn/LSH.js:61
_type	"array" | "typed"	KNN._type	knn/KNN.js:20

Methods

add()

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

Defined in: knn/LSH.js:207

Add elements to the LSH index.

Parameters

Parameter	Type	Description
elements	T[]	-

Returns

LSH<T>

---

search()

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

Defined in: knn/LSH.js:255

Search for k approximate nearest neighbors.

Parameters

Parameter	Type	Default value	Description
query	T	undefined	-
k?	number	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