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.

Contents

• Installation
• Usage
• API
• License

Installation

$ npm install --save hamming-lsh

Usage

import {Vector, Table} from 'hamming-lsh';

const t = new Table(4, 2, 3);

t.add(new Vector([1, 0, 1, 1]));
t.add(new Vector([0, 1, 0, 0]));
t.add(new Vector([0, 1, 1, 0]));

t.query(new Vector([1, 0, 0, 1]));
// => Vector [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 = new Table(d, k, l);

add

Add a vector v to the lookup table.

Parameters

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

Examples

const v = new Vector([1, 0, 1, 0]);
t.add(v);

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 = new 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(new 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 = new 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 = new 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 = new Vector([1, 0, 0, 1]);
v.size();
// => 4

Returns number The number of components in the vector.

License

Copyright © 2016-2018 Kasper Kronborg Isager. Licensed under the terms of the MIT license.