lsh

README

Locality-Sensing Hashing (LSH)

• Introduction
• Installation
• Usage
  • Importing package
  • Creating an LSH Instance
  • Adding Vectors
  • Querying by Vector ID
  • Querying by Vector

Introduction

At its core, Locality-Sensitive Hashing is a technique that allows for the efficient approximate nearest neighbor search in high-dimensional spaces. Unlike traditional methods that require exhaustive comparisons, LSH employs hashing functions to map similar items to the same bucket with high probability, thereby dramatically reducing the search space.

LSH operates under the premise of locality sensitivity, which implies that similar items are likely to remain close to each other in the hashed space. By exploiting this property, LSH enables rapid retrieval of approximate nearest neighbors, making it an invaluable tool in scenarios where exact matches are not necessary.

Installation

To use this library, you need to have Go installed. You can install the library using the following command:

go get github.com/agtabesh/lsh

Usage

Importing package

Import the library in your Go code:

import (
    "context"
    "fmt"

    "github.com/agtabesh/lsh"
    "github.com/agtabesh/lsh/types"
)

To create an instance of LSH, you need to specify the configuration parameters using the LSHConfig struct and call the NewLSH function:

Creating an LSH Instance

config := lsh.LSHConfig{
    SignatureSize:     128, // It is better to be a power of 2
}

hashFamily := lsh.NewXXHASH64HashFamily(config.SignatureSize)
similarityMeasure := lsh.NewHammingSimilarity()
store := lsh.NewInMemoryStore()

instance, err := lsh.NewLSH(config, hashFamily, similarityMeasure, store)
if err != nil {
    // Handle error
}

Adding Vectors

You can add vectors to the LSH service using the Add method:

ctx := context.Background()
vectors := []types.Vector{
    {"feat1": 1, "feat2": 1, "feat3": 1},
    {"feat1": 1, "feat4": 1, "feat5": 1},
    {"feat1": 1, "feat2": 1, "feat6": 1, "feat7": 1},
}
for i, vector := range vectors {
    vectorID := types.VectorID(fmt.Sprint(i))
    err := instance.Add(ctx, vectorID, vector)
    if err != nil {
        // Handle error
    }
}

[!NOTE]
Vectors can be in any dimension or length.

Querying by Vector ID

You can perform a query using a vector ID using the QueryByVectorID method:

ctx := context.Background()
vectorID := types.VectorID("0")
count := 5
similarVectorsID, err := instance.QueryByVectorID(ctx, vectorID, count)
if err != nil {
    // Handle error
}
fmt.Println("similarVectors", similarVectorsID)

Querying by Vector

You can perform a query using a vector using the QueryByVector method:

ctx := context.Background()
vector := types.Vector{"feat1": 1, "feat2": 1, "feat3": 1}
count := 5
similarVectorsID, err := instance.QueryByVector(ctx, vector, count)
if err != nil {
    // Handle error
}
fmt.Println("similarVectors", similarVectorsID)

Documentation

Index

• func NewHammingSimilarity() interfaces.SimilarityMeasure
• func NewInMemoryStore() interfaces.Store
• func NewXXHASH64HashFamily(count int) interfaces.HashFamily
• type LSH
  • func NewLSH(config LSHConfig, hashFamily interfaces.HashFamily, ...) (*LSH, error)
  • func (s *LSH) Add(ctx context.Context, vectorID types.VectorID, vector types.Vector) error
  • func (s *LSH) QueryByVector(ctx context.Context, vector types.Vector, count int) ([]types.VectorID, error)
  • func (s *LSH) QueryByVectorID(ctx context.Context, vectorID types.VectorID, count int) ([]types.VectorID, error)
• type LSHConfig

Functions

func NewHammingSimilarity

func NewHammingSimilarity() interfaces.SimilarityMeasure

func NewInMemoryStore

func NewInMemoryStore() interfaces.Store

func NewXXHASH64HashFamily

func NewXXHASH64HashFamily(count int) interfaces.HashFamily

Types

type LSH

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

LSH represents the Locality Sensitive Hashing service.

func NewLSH

func NewLSH(
	config LSHConfig,
	hashFamily interfaces.HashFamily,
	similarityMeasure interfaces.SimilarityMeasure,
	store interfaces.Store,
) (*LSH, error)

NewLSH creates a new instance of LSH.

func (*LSH) Add

func (s *LSH) Add(ctx context.Context, vectorID types.VectorID, vector types.Vector) error

Add adds a vector to the LSH service.

func (*LSH) QueryByVector

func (s *LSH) QueryByVector(ctx context.Context, vector types.Vector, count int) ([]types.VectorID, error)

QueryByVector performs a query using a vector.

func (*LSH) QueryByVectorID

func (s *LSH) QueryByVectorID(ctx context.Context, vectorID types.VectorID, count int) ([]types.VectorID, error)

QueryByVectorID performs a query using a vectorID.

type LSHConfig

type LSHConfig struct {
	SignatureSize int // SignatureSize is the size of the signature.
}

LSHConfig holds configuration parameters for LSH.