minhashlsh

README

Minhash LSH in Golang

Documentation

Install: go get github.com/omorillo/minhash-lsh

Run Benchmark

Set file format

1. One set per line

2. Each set, all items are separated by whitespaces

3. If the parameter firstItemIsID is set to true, the first itme is the unique ID of the set.

4. The rest of the items with the following format: <value>____<frequency>

   • value is an unique element of the set
   • frequency is an integer count of the occurance of value
   • ____ (4 underscores) is the separator

All Pair Benchmark

minhash-lsh-all-pair -input <set file name>

Documentation

Index

• Variables
• type Minhash
  • func NewMinhash(seed int64, numHash int) *Minhash
  • func (m *Minhash) Merge(o *Minhash)
  • func (m *Minhash) Push(b []byte)
  • func (m *Minhash) Signature() []uint64
• type MinhashLSH
  • func Load(filename string) (*MinhashLSH, error)
  • func NewMinhashLSH16(numHash int, threshold float64, initSize int) *MinhashLSH
  • func NewMinhashLSH32(numHash int, threshold float64, initSize int) *MinhashLSH
  • func NewMinhashLSH64(numHash int, threshold float64, initSize int) *MinhashLSH
  • func (f *MinhashLSH) Add(key interface{}, sig []uint64)
  • func (f *MinhashLSH) Index()
  • func (f *MinhashLSH) Params() (k, l int)
  • func (f *MinhashLSH) Query(sig []uint64) []interface{}
  • func (minhashLsh *MinhashLSH) Save(filename string) error

Variables

var NewMinhashLSH = NewMinhashLSH32

NewMinhashLSH is the default constructor uses 32 bit hash value with pre-allocation of hash tables.

Types

type Minhash

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

Minhash represents a MinHash object

func NewMinhash

func NewMinhash(seed int64, numHash int) *Minhash

NewMinhash initialize a MinHash object with a seed and the number of hash functions.

func (*Minhash) Merge

func (m *Minhash) Merge(o *Minhash)

Merge combines the signature of the other Minhash with this one, making this one carry the signature of the union.

func (*Minhash) Push

func (m *Minhash) Push(b []byte)

Push a new value to the MinHash object. The value should be serialized to byte slice.

func (*Minhash) Signature

func (m *Minhash) Signature() []uint64

Signature exports the MinHash as a list of hash values.

type MinhashLSH

type MinhashLSH struct {
	K              int
	L              int
	HashTables     []hashTable
	HashKeyFunc    hashKeyFunc
	HashValueSize  int
	NumIndexedKeys int
}

MinhashLSH represents a MinHash LSH implemented using LSH Forest (http://ilpubs.stanford.edu:8090/678/1/2005-14.pdf). It supports query-time setting of the MinHash LSH parameters L (number of bands) and K (number of hash functions per band).

func Load

func Load(filename string) (*MinhashLSH, error)

Load MinHash LSH index

func NewMinhashLSH16

func NewMinhashLSH16(numHash int, threshold float64, initSize int) *MinhashLSH

NewMinhashLSH16 uses 16-bit hash values and pre-allocation of hash tables. MinHash signatures with 64 or 32 bit hash values will have their hash values trimed.

func NewMinhashLSH32

func NewMinhashLSH32(numHash int, threshold float64, initSize int) *MinhashLSH

NewMinhashLSH32 uses 32-bit hash values and pre-allocation of hash tables. MinHash signatures with 64 bit hash values will have their hash values trimed.

func NewMinhashLSH64

func NewMinhashLSH64(numHash int, threshold float64, initSize int) *MinhashLSH

NewMinhashLSH64 uses 64-bit hash values and pre-allocation of hash tables.

func (*MinhashLSH) Add

func (f *MinhashLSH) Add(key interface{}, sig []uint64)

Add a Key with MinHash signature into the index. The Key won't be searchable until Index() is called.

func (*MinhashLSH) Index

func (f *MinhashLSH) Index()

Index makes all the keys added searchable.

func (*MinhashLSH) Params

func (f *MinhashLSH) Params() (k, l int)

Params returns the LSH parameters K and L

func (*MinhashLSH) Query

func (f *MinhashLSH) Query(sig []uint64) []interface{}

Query returns candidate keys given the query signature.

func (*MinhashLSH) Save

func (minhashLsh *MinhashLSH) Save(filename string) error

Save MinHash LSH index