@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 Random Projection hashing (SimHash-style) which works well for cosine similarity and Euclidean distance.

Key concepts:

• Multiple hash tables increase recall probability
• Each hash function projects data onto random hyperplanes
• Points on the same side of hyperplanes 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

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?: ParametersLSH): LSH<T>;

Defined in: knn/LSH.js:41

Creates a new LSH index.

Parameters

Parameter	Type	Description
elements	T[]	Elements to index
parameters?	ParametersLSH	Configuration parameters

Returns

LSH<T>

Overrides

KNN.constructor

Properties

Property	Type	Inherited from	Defined in
_dim	number	-	knn/LSH.js:76
_elements	T[]	KNN._elements	knn/KNN.js:14
_hashTables	Map<string, number[]>[]	-	knn/LSH.js:64
_metric	Metric	-	knn/LSH.js:56
_numHashFunctions	number	-	knn/LSH.js:58
_numHashTables	number	-	knn/LSH.js:57
_offsets	number[][]	-	knn/LSH.js:72
_parameters	ParametersLSH	KNN._parameters	knn/KNN.js:16
_projections	Float64Array<ArrayBufferLike>[][]	-	knn/LSH.js:68
_randomizer	Randomizer	-	knn/LSH.js:60
_seed	number	-	knn/LSH.js:59
_type	"array" | "typed"	KNN._type	knn/KNN.js:18

Methods

add()

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

Defined in: knn/LSH.js:169

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

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/LSH.js:288

Parameters

Parameter	Type	Default value	Description
i	number	undefined	-
k?	number	5	-

Returns

{ distance: number; element: T; index: number; }[]

Overrides

KNN.search_by_index