README
¶
LSH for Go
Install: go get github.com/ekzhu/lsh
This library includes various Locality Sensitive Hashing (LSH) algorithms for the approximate nearest neighbour search problem in L2 metric space. The family of LSH functions for L2 is the work of Mayur Datar et.al.
Currently includes:
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BasicLsh ¶
type BasicLsh struct {
// contains filtered or unexported fields
}
BasicLsh implements the original LSH algorithm for L2 distance.
func NewBasicLsh ¶
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.
type LshForest ¶
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 ¶
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.
type MultiprobeLsh ¶
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 ¶
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 ¶
func (index *MultiprobeLsh) Query(q Point) []string
Query finds the ids of nearest neighbour candidates, given the query point
Source Files