# hamming-lsh

An implementation of locality-sensitive hashing for Hamming space

## Usage no npm install needed!

``````<script type="module">
import hammingLsh from 'https://cdn.skypack.dev/hamming-lsh';
</script>``````

# Hamming LSH

An implementation of locality-sensitive hashing for Hamming space

Locality-sensitive hashing (abbreviated LSH) is a method often used for answering approximate nearest neighbour queries in high-dimensional data sets. This library implements a version of LSH for solving the approximate nearest neighbour problem for binary vectors in Hamming space.

## Installation

``````\$ npm install --save hamming-lsh
``````

## Usage

``````import {Vector as V, Table as T} from 'hamming-lsh';

const t = T(4, 2, 3);

t.query(V([1, 0, 0, 1]));
// => V([1, 0, 1, 1]) with high probability
``````

## API

### Table

Construct a lookup table for vectors of dimensionality `d` where vectors are hashed using `k`-width hash values (random vector projections) into `l` sets of hashes.

Parameters

• `d` number The number of dimensions of vectors in the table.
• `k` number The width of each vector hash.
• `l` number The number of hash sets to use.

Examples

``````const d = 4;
const k = 2;
const l = 2;
const t = Table(d, k, l);
``````

Add a vector `v` to the lookup table.

Parameters

• `v` Vector The vector to add to the lookup table.

Examples

``````const v = Vector([1, 0, 1, 0]);
``````

#### query

Query the lookup table for the nearest neighbour of a query vector `q`.

Parameters

• `q` Vector The query vector to look up the nearest neighbour of.

Examples

``````const q = Vector([0, 1, 0, 1]);
t.query(q);
// => Vector(...)
``````

Returns Vector The nearest neighbouring vector if found.

#### size

Get the number of vectors in the lookup table.

Examples

``````t.add(Vector(...));
t.size();
// => 1
``````

Returns number The number of vectors in the lookup table.

### contains

Check if the lookup table contains a specific vector.

Parameters

• `v` Vector The vector to check for.

Returns boolean `true` if the table contains the vector, otherwise `false`.

### Vector

Construct a vector consisting of binary components where truthy values represent 1 and falsy values represent 0.

Parameters

• `cs` Array.<number>= The components of the vector. (optional, default `[]`)

Examples

``````const v = Vector([1, 0, 1]);
``````

#### get

Get the component at the specified index of the vector.

Parameters

• `i` number The index of the component to get.

Examples

``````const v = Vector([1, 0, 1, 1]);
v.get(0);
// => 1
``````

Returns number The component at the index if found.

#### size

Get the number of components in the vector.

Examples

``````const v = Vector([1, 0, 0, 1]);
v.size();
// => 4
``````

Returns number The number of components in the vector.