lsh: github.com/ekzhu/lsh Index | Files

package lsh

import "github.com/ekzhu/lsh"

Index

Package Files

basic.go forest.go lsh.go metric.go multiprobe.go

type BasicLsh Uses

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

BasicLsh implements the original LSH algorithm for L2 distance.

func NewBasicLsh Uses

func NewBasicLsh(dim, l, m int, w float64) *BasicLsh

NewBasicLsh creates a basic LSH for L2 distance. dim is the diminsionality of the data, l is the number of hash tables to use, m is the number of hash values to concatenate to form the key to the hash tables, w is the slot size for the family of LSH functions.

func (*BasicLsh) Delete Uses

func (index *BasicLsh) Delete(id string)

Delete removes a new data point to the LSH. id is the unique identifier for the data point.

func (*BasicLsh) Insert Uses

func (index *BasicLsh) Insert(point Point, id string)

Insert adds a new data point to the LSH. id is the unique identifier for the data point.

func (*BasicLsh) Query Uses

func (index *BasicLsh) Query(q Point) []string

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

type LshForest Uses

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

LshForest implements the LSH Forest algorithm by Mayank Bawa et.al. It supports both nearest neighbour candidate query and k-NN query.

func NewLshForest Uses

func NewLshForest(dim, l, m int, w float64) *LshForest

NewLshForest creates a new LSH Forest for L2 distance. dim is the diminsionality of the data, l is the number of hash tables to use, m is the number of hash values to concatenate to form the key to the hash tables, w is the slot size for the family of LSH functions.

func (*LshForest) Delete Uses

func (index *LshForest) Delete()

Delete releases the memory used by this index.

func (*LshForest) Insert Uses

func (index *LshForest) Insert(point Point, id string)

Insert adds a new data point to the LSH Forest. id is the unique identifier for the data point.

func (*LshForest) Query Uses

func (index *LshForest) Query(q Point, k int) []string

Query finds at top-k ids of approximate nearest neighbour candidates, in unsorted order, given the query point.

type MultiprobeLsh Uses

type MultiprobeLsh struct {
    *BasicLsh
    // contains filtered or unexported fields
}

MultiprobeLsh implements the Multi-probe LSH algorithm by Qin Lv et.al. The Multi-probe LSH does not support k-NN query directly.

func NewMultiprobeLsh Uses

func NewMultiprobeLsh(dim, l, m int, w float64, t int) *MultiprobeLsh

NewMultiprobeLsh creates a new Multi-probe LSH for L2 distance. dim is the diminsionality of the data, l is the number of hash tables to use, m is the number of hash values to concatenate to form the key to the hash tables, and w is the slot size for the family of LSH functions. t is the number of perturbation vectors that will be applied to each query. Increasing t increases the running time of the Query function.

func (*MultiprobeLsh) Query Uses

func (index *MultiprobeLsh) Query(q Point) []string

Query finds the ids of nearest neighbour candidates, given the query point

type Point Uses

type Point []float64

Point is a vector in the L2 metric space.

func (Point) Dot Uses

func (p Point) Dot(q Point) float64

Dot returns the dot product of two points.

func (Point) L2 Uses

func (p Point) L2(q Point) float64

L2 returns the L2 distance of two points.

Package lsh imports 5 packages (graph). Updated 2020-03-11. Refresh now. Tools for package owners.