Skip to content
This repository has been archived by the owner on Jun 30, 2018. It is now read-only.
/ hamming-lsh Public archive

An implementation of locality-sensitive hashing for Hamming space

License

Notifications You must be signed in to change notification settings

kasperisager/hamming-lsh

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

44 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Hamming LSH

An implementation of locality-sensitive hashing for Hamming space

Build Status Inline docs

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

$ 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.

About

An implementation of locality-sensitive hashing for Hamming space

Resources

License

Stars

Watchers

Forks

Packages

No packages published