simhashlsh

README

simhash-lsh

Cosine/Simhash locality sensitive hashing (LSH) in Golang with Euclidean distance sort

Implements Random projection LSH https://en.wikipedia.org/wiki/Locality-sensitive_hashing#Random_projection

Usage

Use go tool to install the package in your packages tree:

go get github.com/cogile/simhash-lsh

Import package as:

import "github.com/cogile/simhash-lsh"

Basic example

func main() {
	lsh := simhashlsh.NewCosineLsh(8, 1, 6)
	lsh.Insert([]float64{1, 2, 3, 4, 5, 6, 7, 8}, "1")
	lsh.Insert([]float64{2, 3, 4, 5, 6, 7, 8, 9}, "2")
	lsh.Insert([]float64{10, 12, 99, 1, 5, 31, 2, 3}, "3")
	fmt.Println(lsh.Query([]float64{1, 2, 3, 4, 5, 6, 7, 7}))
	// [{[1 2 3 4 5 6 7 8] 1} {[2 3 4 5 6 7 8 9] 2}]
}

Documentation

Index

• type CosineLsh
  • func NewCosineLsh(dim, l, m int) *CosineLsh
  • func (index *CosineLsh) Insert(point []float64, extraData string)
  • func (index *CosineLsh) Query(q []float64, maxResult int) []QueryResult
• type DistanceFunc
• type Point
• type QueryResult

Types

type CosineLsh

type CosineLsh struct {
	// contains filtered or unexported fields
}

CosineLsh is an implementation of Random projection LSH https://en.wikipedia.org/wiki/Locality-sensitive_hashing#Random_projection

func NewCosineLsh

func NewCosineLsh(dim, l, m int) *CosineLsh

NewCosineLsh created an instance of Cosine LSH. dim is the number of dimensions of the input points (also the number of dimensions of each hyperplane) l is the number of hash tables, m is the number of hash values in each hash table.

func (*CosineLsh) Insert

func (index *CosineLsh) Insert(point []float64, extraData string)

Insert adds a new data point to the Cosine LSH. point is a data point being inserted into the index and id is the unique identifier for the data point.

func (*CosineLsh) Query

func (index *CosineLsh) Query(q []float64, maxResult int) []QueryResult

Query finds the ids of approximate nearest neighbour candidates, in un-sorted order, given the query point.

type DistanceFunc

type DistanceFunc func(p1 []float64, p2 []float64) float64

DistanceFunc is a function for calculate distance between two vectors

type Point

type Point struct {
	Vector    []float64
	ExtraData string
	ID        uint64
}

Point represents an abstract point in n-dimensional space

type QueryResult

type QueryResult struct {
	Point
	Distance float64
}

QueryResult represent query result with distance to query point