Documentation
¶
Overview ¶
Package lsh provides locality-sensitive hashing for approximate nearest neighbor search.
Index ¶
- func GenerateHyperplanes(seed int64, numBits, dimension int) [][]float64
- func GenerateHyperplanesFromBytes(seed []byte, numBits, dimension int) [][]float64
- func GenerateSessionKey(numBytes int) []byte
- func HammingDistance(a, b []byte) int
- func HashToIndex(hash []byte, numBuckets int) int
- func MaskHash(hash []byte, sessionKey []byte) []byte
- func UnmaskHash(maskedHash []byte, sessionKey []byte) []byte
- type Candidate
- type Config
- type EnterpriseHasher
- type Index
- func (idx *Index) Add(ids []string, vectors [][]float64) error
- func (idx *Index) AddOne(id string, vector []float64) error
- func (idx *Index) BucketCount() int
- func (idx *Index) Count() int
- func (idx *Index) GetPlanes() [][]float64
- func (idx *Index) GetVector(id string) ([]float64, bool)
- func (idx *Index) GetVectors(ids []string) [][]float64
- func (idx *Index) HashBytes(vector []float64) []byte
- func (idx *Index) HashToIndexFromVector(vector []float64, numBuckets int) int
- func (idx *Index) MultiProbeSearch(queryHash []byte, k int, numProbes int) ([]Candidate, error)
- func (idx *Index) Remove(ids []string)
- func (idx *Index) Save(w io.Writer) error
- func (idx *Index) SaveToFile(path string) error
- func (idx *Index) Search(queryHash []byte, k int) ([]Candidate, error)
- func (idx *Index) SearchVector(query []float64, k int) ([]Candidate, error)
- func (idx *Index) TwoStageSearch(query []float64, initialCandidates, topN int) ([]Candidate, error)
- type TwoStageConfig
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func GenerateHyperplanes ¶
GenerateHyperplanes generates random normalized hyperplanes from a seed. This should only be called by the enterprise admin during setup, NOT by clients during search.
The hyperplanes are normalized to unit length to ensure consistent hashing behavior.
func GenerateHyperplanesFromBytes ¶
GenerateHyperplanesFromBytes generates hyperplanes from a byte seed. Useful when the seed comes from a cryptographically random source.
func GenerateSessionKey ¶
GenerateSessionKey generates a random session key for hash masking.
func HammingDistance ¶
HammingDistance computes the Hamming distance between two byte slices.
func HashToIndex ¶
HashToIndex converts a hash to a bucket index in range [0, numBuckets). Uses the hash bytes directly to compute a bucket index. This is useful for hierarchical indexing where we need to map vectors to a fixed number of buckets.
func MaskHash ¶
MaskHash XORs the hash with a session key for privacy. This prevents the server from correlating queries across sessions.
func UnmaskHash ¶
UnmaskHash reverses the masking operation.
Types ¶
type Config ¶
type Config struct {
Dimension int // Vector dimension
NumBits int // Number of hash bits (64, 128, 256, etc.)
Seed int64 // Random seed for reproducibility
}
Config holds configuration for creating a new index
type EnterpriseHasher ¶
type EnterpriseHasher struct {
// contains filtered or unexported fields
}
EnterpriseHasher provides LSH hashing using pre-distributed hyperplanes. This is used by clients who receive hyperplanes from the auth service instead of generating them from a seed.
Key security property: The auth service distributes pre-computed hyperplanes instead of seeds. This provides an additional layer of security - even if hyperplanes leak, the original seed remains secret.
func NewEnterpriseHasher ¶
func NewEnterpriseHasher(planes [][]float64) *EnterpriseHasher
NewEnterpriseHasher creates a hasher from pre-generated hyperplanes.
func (*EnterpriseHasher) Dimension ¶
func (h *EnterpriseHasher) Dimension() int
Dimension returns the expected vector dimension.
func (*EnterpriseHasher) GetPlanes ¶
func (h *EnterpriseHasher) GetPlanes() [][]float64
GetPlanes returns the hyperplanes (for serialization).
func (*EnterpriseHasher) Hash ¶
func (h *EnterpriseHasher) Hash(vector []float64) []byte
Hash computes the LSH hash for a vector.
func (*EnterpriseHasher) HashToIndex ¶
func (h *EnterpriseHasher) HashToIndex(vector []float64, numBuckets int) int
HashToIndex computes a bucket index in range [0, numBuckets).
func (*EnterpriseHasher) NumBits ¶
func (h *EnterpriseHasher) NumBits() int
NumBits returns the number of hash bits (hyperplanes).
type Index ¶
type Index struct {
// contains filtered or unexported fields
}
Index is a locality-sensitive hash index using random hyperplanes.
func LoadFromFile ¶
LoadFromFile loads an index from a file.
func (*Index) BucketCount ¶
BucketCount returns the number of buckets.
func (*Index) GetVectors ¶
GetVectors retrieves multiple vectors by ID.
func (*Index) HashToIndexFromVector ¶
HashToIndexFromVector computes hash and returns bucket index.
func (*Index) MultiProbeSearch ¶
MultiProbeSearch searches with multi-probe LSH (checks neighboring buckets). This is essentially the same as regular search but with a relaxed distance threshold that increases recall at the cost of precision. The numProbes parameter controls the maximum Hamming distance to include.
func (*Index) SaveToFile ¶
SaveToFile saves the index to a file.
func (*Index) SearchVector ¶
SearchVector computes hash and searches in one call.
func (*Index) TwoStageSearch ¶
TwoStageSearch performs optimized two-stage retrieval: Stage 1: Get many candidates from LSH (cheap) Stage 2: Rank by Hamming distance, return top N for expensive HE scoring This improves both accuracy (more initial candidates) and speed (fewer HE ops).
type TwoStageConfig ¶
type TwoStageConfig struct {
InitialCandidates int // Number of candidates from LSH (default: 200)
TopN int // Number to return for HE scoring (default: 10)
}
TwoStageConfig holds configuration for two-stage search
func DefaultTwoStageConfig ¶
func DefaultTwoStageConfig() TwoStageConfig
DefaultTwoStageConfig returns sensible defaults
Source Files