hnsw

package
v0.1.5 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 11, 2026 License: Apache-2.0 Imports: 14 Imported by: 0

Documentation

Overview

adaptive_config.go - Adaptive parameter configuration

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrDimensionMismatch is returned when vector dimensions do not match
	ErrDimensionMismatch = errors.New("vector dimension mismatch")

	// ErrEmptyIndex is returned when the index is empty
	ErrEmptyIndex = errors.New("index is empty")

	// ErrInvalidParameter is returned when a parameter is invalid
	ErrInvalidParameter = errors.New("invalid parameter")
)

Functions

func CosineDistance 

func CosineDistance(a, b []float32) float32

CosineDistance computes the cosine distance between two vectors. Distance = 1 - CosineSimilarity

func FileExists 

func FileExists(path string) bool

FileExists checks if a deletion vector file exists at the given path.

func GetDeletionVectorInfo 

func GetDeletionVectorInfo(path string) (numDeleted uint64, fileSize int64, err error)

GetDeletionVectorInfo returns information about a deletion vector file without loading it. Returns the number of deleted rows and the file size.

func GetDeletionVectorPath 

func GetDeletionVectorPath(dataFilePath string) string

GetDeletionVectorPath returns the DV file path for a data file. The DV file is named by appending ".del" to the data file path.

Example: 

dataFile = "/path/to/vectors.lance"
dvFile   = "/path/to/vectors.lance.del"

func InnerProductDistance 

func InnerProductDistance(a, b []float32) float32

InnerProductDistance computes the inner product distance between two vectors. Note: Inner product is not a true distance metric, but is often used in similarity search. Distance = 1 - InnerProduct

func L2Distance 

func L2Distance(a, b []float32) float32

L2Distance computes the L2 (Euclidean) distance between two vectors.

func L2DistanceSqrt 

func L2DistanceSqrt(a, b []float32) float32

L2DistanceSqrt computes the square root of the L2 distance between two vectors.

func RegisterDistanceFunc added in v0.1.5 

func RegisterDistanceFunc(name string, df DistanceFunc)

RegisterDistanceFunc registers a custom distance function so it can be serialized and deserialized correctly. Built-in functions are pre-registered. Unregistered functions will silently fallback to L2Distance during Marshal.

func SchemaForConnections 

func SchemaForConnections() *core.Schema

SchemaForConnections creates schema for connection storage.

func SchemaForMetadata 

func SchemaForMetadata() *core.Schema

SchemaForMetadata creates schema for metadata storage.

func SchemaForNodes 

func SchemaForNodes(dimension int) *core.Schema

SchemaForNodes creates schema for node storage.

Types

type Config 

type Config struct {
	M              int          // Maximum number of connections per level, default 16.
	EfConstruction int          // default 200.
	Dimension      int          // Vector dimensionality.
	DistanceFunc   DistanceFunc // default L2Distance.
	Seed           int64        // Seed for random level generation.
	Adaptive       bool         // If true, automatically calculate M and EfConstruction based on Dimension and ExpectedSize
	ExpectedSize   int          // Expected dataset size for adaptive parameter calculation (default: 10000)
}

Config holds the configuration parameters for the HNSW index.

func AdaptiveConfig 

func AdaptiveConfig(dimension, expectedDatasetSize int) Config

AdaptiveConfig generates optimal HNSW parameters based on data characteristics

type DeletionVector 

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

DeletionVector marks deleted rows using a bitmap. It provides O(1) deletion checking and memory-efficient storage for sparse deletion patterns using RoaringBitmap.

func Deserialize 

func Deserialize(path string) (*DeletionVector, error)

Deserialize reads a DeletionVector from a file. Returns an error if the file is corrupted or has an unsupported version. If the file doesn't exist, returns (nil, error).

func DeserializeOrEmpty 

func DeserializeOrEmpty(path string) *DeletionVector

DeserializeOrEmpty attempts to deserialize a DeletionVector from a file. If the file doesn't exist or is corrupted, returns an empty DeletionVector instead of an error. This is useful for backward compatibility where old data may not have a .del file.

func NewDeletionVector 

func NewDeletionVector() *DeletionVector

NewDeletionVector creates a new empty DeletionVector.

func NewDeletionVectorFromBitmap 

func NewDeletionVectorFromBitmap(bitmap *roaring.Bitmap) *DeletionVector

NewDeletionVectorFromBitmap creates a DeletionVector from an existing bitmap. The bitmap is cloned to avoid shared state.

func (*DeletionVector) AndNot 

func (dv *DeletionVector) AndNot(other *DeletionVector)

AndNot removes all deletions that are present in other (set subtraction). This is useful for clearing deletions after compaction.

func (*DeletionVector) Clear 

func (dv *DeletionVector) Clear()

Clear removes all deletion marks.

func (*DeletionVector) Clone 

func (dv *DeletionVector) Clone() *DeletionVector

Clone creates a deep copy of the DeletionVector.

func (*DeletionVector) Count 

func (dv *DeletionVector) Count() int

Count returns the number of deleted rows.

func (*DeletionVector) CountUint64 

func (dv *DeletionVector) CountUint64() uint64

CountUint64 returns the number of deleted rows as uint64.

func (*DeletionVector) DeletedRows 

func (dv *DeletionVector) DeletedRows() *roaring.Bitmap

DeletedRows returns a clone of the internal bitmap containing all deleted row IDs. The returned bitmap is safe to modify without affecting the DeletionVector.

func (*DeletionVector) GetDeletedRows 

func (dv *DeletionVector) GetDeletedRows() []uint32

GetDeletedRows returns a slice of all deleted row IDs. Note: This may allocate significant memory for large deletion sets. Consider using IterDeletedRows for large datasets.

func (*DeletionVector) GetMaxRowID 

func (dv *DeletionVector) GetMaxRowID() (uint32, bool)

GetMaxRowID returns the maximum row ID that has been marked as deleted. Returns 0 and false if no rows are deleted.

func (*DeletionVector) IsDeleted 

func (dv *DeletionVector) IsDeleted(rowID uint32) bool

IsDeleted checks if a row is deleted. This operation is thread-safe and O(1).

func (*DeletionVector) IsEmpty 

func (dv *DeletionVector) IsEmpty() bool

IsEmpty returns true if no rows are marked as deleted.

func (*DeletionVector) IterDeletedRows 

func (dv *DeletionVector) IterDeletedRows(fn func(rowID uint32) bool)

IterDeletedRows provides an iterator callback for all deleted rows. More memory-efficient than GetDeletedRows for large datasets.

func (*DeletionVector) MarkDeleted 

func (dv *DeletionVector) MarkDeleted(rowID uint32)

MarkDeleted marks a row ID as deleted. This operation is thread-safe and O(1).

func (*DeletionVector) Merge 

func (dv *DeletionVector) Merge(other *DeletionVector)

Merge combines another DeletionVector into this one. After merge, this DeletionVector contains all deletions from both.

func (*DeletionVector) Serialize 

func (dv *DeletionVector) Serialize(path string) error

Serialize writes the DeletionVector to a file. The file format is:

  • Header (16 bytes):
  • Magic: "DEL1" (4 bytes)
  • Version: uint32 (4 bytes)
  • NumDeleted: uint64 (8 bytes)
  • Bitmap Data: RoaringBitmap serialization

func (*DeletionVector) UnmarkDeleted 

func (dv *DeletionVector) UnmarkDeleted(rowID uint32) bool

UnmarkDeleted unmarks a row ID (for rollback/undelete scenarios). Returns true if the row was previously marked as deleted.

type DistanceFunc 

type DistanceFunc func(a, b []float32) float32

type HNSWIndex 

type HNSWIndex struct {
	// Core params
	M     int // Maximum number of connections per level.
	Mmax  int // The real value of the M.
	Mmax0 int // Maximum number of connections at level 0.(2*M).
	// contains filtered or unexported fields
}

The main structure of the HNSW index.

func NewHNSW 

func NewHNSW(config Config) *HNSWIndex

func (*HNSWIndex) Add 

func (h *HNSWIndex) Add(vector []float32) (int, error)

Add inserts a new vector into the HNSW index and returns its assigned node ID.

func (*HNSWIndex) Len 

func (h *HNSWIndex) Len() int

Len returns the number of nodes in the HNSW index.

func (*HNSWIndex) MarshalConnections added in v0.1.5 

func (h *HNSWIndex) MarshalConnections() (*core.RecordBatch, error)

MarshalConnections serializes all graph edges into a core.RecordBatch. Returns nil, nil when there are no connections.

TODO: For million-scale datasets, switch to streaming callbacks (batchSize int, emit func(*core.RecordBatch) error) to avoid multi-GB single-batch allocation.

func (*HNSWIndex) MarshalMetadata added in v0.1.5 

func (h *HNSWIndex) MarshalMetadata() (*core.RecordBatch, error)

MarshalMetadata serializes index configuration into a single-row RecordBatch.

func (*HNSWIndex) MarshalNodes added in v0.1.5 

func (h *HNSWIndex) MarshalNodes() (*core.RecordBatch, error)

MarshalNodes serializes all nodes in the index into a core.RecordBatch. Returns an error if the index contains no nodes.

TODO: For million-scale datasets, switch to streaming callbacks (batchSize int, emit func(*core.RecordBatch) error) to avoid multi-GB single-batch allocation.

func (*HNSWIndex) Search 

func (h *HNSWIndex) Search(query []float32, k int, ef int) ([]SearchResult, error)

func (*HNSWIndex) SearchWithAdaptiveEf 

func (h *HNSWIndex) SearchWithAdaptiveEf(query []float32, k int) ([]SearchResult, error)

SearchWithAdaptiveEf - Search using adaptive ef

func (*HNSWIndex) SearchWithDV 

func (h *HNSWIndex) SearchWithDV(query []float32, k int, ef int, isDeleted func(int) bool) ([]SearchResult, error)

SearchWithDV searches for k nearest neighbors with deletion vector filtering. It searches exactly k candidates then post-filters via the isDeleted callback. Callers that expect a high deletion rate should multiply k before calling — e.g. SearchContext passes k*2, SearchWithFilterContext passes k*OverFetch.

The isDeleted callback receives a node ID and should return true if the node is considered deleted and should be filtered out.

func (*HNSWIndex) SetEntryPoint added in v0.1.5 

func (h *HNSWIndex) SetEntryPoint(ep int32)

SetEntryPoint sets the entry point for a loaded index. Must be called before UnmarshalNodes when restoring from disk.

func (*HNSWIndex) SetMaxLevel added in v0.1.5 

func (h *HNSWIndex) SetMaxLevel(ml int32)

SetMaxLevel sets the maximum level for a loaded index. Must be called before UnmarshalNodes when restoring from disk.

func (*HNSWIndex) UnmarshalConnections added in v0.1.5 

func (h *HNSWIndex) UnmarshalConnections(batch *core.RecordBatch) error

UnmarshalConnections rebuilds graph edges from a RecordBatch.

func (*HNSWIndex) UnmarshalNodes added in v0.1.5 

func (h *HNSWIndex) UnmarshalNodes(batch *core.RecordBatch) error

UnmarshalNodes reconstructs nodes from a RecordBatch. The index must already have the correct dimension configured.

type Item 

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

type MaxHeap 

type MaxHeap []*Item

MaxHeap (used to maintain result set)

func (MaxHeap) Len 

func (h MaxHeap) Len() int

func (MaxHeap) Less 

func (h MaxHeap) Less(i, j int) bool

func (*MaxHeap) Peek 

func (h *MaxHeap) Peek() interface{}

func (*MaxHeap) Pop 

func (h *MaxHeap) Pop() interface{}

func (*MaxHeap) Push 

func (h *MaxHeap) Push(x interface{})

func (MaxHeap) Swap 

func (h MaxHeap) Swap(i, j int)

type MetadataResult added in v0.1.5 

type MetadataResult struct {
	M              int
	Mmax           int
	Mmax0          int
	EfConstruction int
	Dimension      int
	EntryPoint     int32
	MaxLevel       int32
	NumNodes       int
	DistanceFunc   DistanceFunc
}

MetadataResult holds the unmarshaled index configuration.

func UnmarshalMetadata added in v0.1.5 

func UnmarshalMetadata(batch *core.RecordBatch) (*MetadataResult, error)

UnmarshalMetadata extracts index configuration from a single-row RecordBatch. It is backward-compatible with legacy metadata that lacks the distanceFunc column.

type Node 

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

Node represents a single node in the HNSW graph.

func NewNode 

func NewNode(id int, vector []float32, level int) *Node

func (*Node) AddConnection 

func (n *Node) AddConnection(level int, neighborID int)

AddConnection adds a connection to another node at the specified level.

func (*Node) ConnectionCount 

func (n *Node) ConnectionCount(level int) int

ConnectionCount returns the number of connections at the specified level.

func (*Node) GetConnections 

func (n *Node) GetConnections(level int) []int

GetConnections returns the connections of the node at the specified level.

func (*Node) ID 

func (n *Node) ID() int

func (*Node) Level 

func (n *Node) Level() int

func (*Node) SetConnections 

func (n *Node) SetConnections(level int, neighbors []int)

SetConnections sets the connections of the node at the specified level.

func (*Node) Vector 

func (n *Node) Vector() []float32

type PriorityQueue 

type PriorityQueue []*Item

PriorityQueue implements a min-heap

func (PriorityQueue) Len 

func (pq PriorityQueue) Len() int

func (PriorityQueue) Less 

func (pq PriorityQueue) Less(i, j int) bool

func (*PriorityQueue) Pop 

func (pq *PriorityQueue) Pop() interface{}

func (*PriorityQueue) Push 

func (pq *PriorityQueue) Push(x interface{})

func (PriorityQueue) Swap 

func (pq PriorityQueue) Swap(i, j int)

type SearchResult 

type SearchResult struct {
	ID       int
	Distance float32
}

SearchResult represents a single search result with its ID and distance.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.
⌂ 换网址