hnsw

README

Hierarchical Navigable Small World Graphs

The module implement Hierarchical Navigable Small World (HNSW) algorithms to approximate nearest-neighbour. The algorithm is depicted in the article https://arxiv.org/pdf/1603.09320.pdf

Use http://corpus-texmex.irisa.fr for testing.

Documentation

Index

• type Config
• type FMap
• type HNSW
  • func FromNodes[Vector any](surface vector.Surface[Vector], nodes Nodes[Vector], opts ...Option) *HNSW[Vector]
  • func New[Vector any](surface vector.Surface[Vector], zero Vector, opts ...Option) *HNSW[Vector]
  • func (h *HNSW[Vector]) Distance(a, b Vector) float32
  • func (h *HNSW[Vector]) Dump(sb *strings.Builder)
  • func (h *HNSW[Vector]) FMap(level int, fmap FMap[Vector]) error
  • func (h *HNSW[Vector]) Insert(v Vector)
  • func (h *HNSW[Vector]) Level() int
  • func (h *HNSW[Vector]) Nodes() Nodes[Vector]
  • func (h *HNSW[Vector]) Pipe(workers int) chan<- Vector
  • func (h *HNSW[Vector]) Read(r Reader) error
  • func (h *HNSW[Vector]) Search(q Vector, K int, efSearch int) []Vector
  • func (h *HNSW[Vector]) SearchLayer(level int, addr Pointer, q Vector, ef int) pq.Queue[Vertex]
  • func (h *HNSW[Vector]) Write(w Writer) error
• type Node
• type Nodes
• type Option
  • func With(opts ...Option) Option
  • func WithEfConstruction(ef int) Option
  • func WithM(m int) Option
  • func WithRandomSource(random rand.Source) Option
• type Pointer
• type Reader
• type Vertex
• type Writer

Types

type Config

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

Config of the HNSW

type FMap

type FMap[Vector any] func(level int, vector Vector, vertex []Vector) error

type HNSW

type HNSW[Vector any] struct {
	// contains filtered or unexported fields
}

HNSW data type

func FromNodes

func FromNodes[Vector any](
	surface vector.Surface[Vector],
	nodes Nodes[Vector],
	opts ...Option,
) *HNSW[Vector]

Create data structure FromNodes

func New

func New[Vector any](
	surface vector.Surface[Vector],
	zero Vector,
	opts ...Option,
) *HNSW[Vector]

Creates new instance of data structure

func (*HNSW[Vector]) Distance

func (h *HNSW[Vector]) Distance(a, b Vector) float32

func (*HNSW[Vector]) Dump

func (h *HNSW[Vector]) Dump(sb *strings.Builder)

func (*HNSW[Vector]) FMap

func (h *HNSW[Vector]) FMap(level int, fmap FMap[Vector]) error

func (*HNSW[Vector]) Insert

func (h *HNSW[Vector]) Insert(v Vector)

Insert new vector

func (*HNSW[Vector]) Level

func (h *HNSW[Vector]) Level() int

func (*HNSW[Vector]) Nodes

func (h *HNSW[Vector]) Nodes() Nodes[Vector]

func (*HNSW[Vector]) Pipe

func (h *HNSW[Vector]) Pipe(workers int) chan<- Vector

func (*HNSW[Vector]) Read

func (h *HNSW[Vector]) Read(r Reader) error

func (*HNSW[Vector]) Search

func (h *HNSW[Vector]) Search(q Vector, K int, efSearch int) []Vector

Search K-nearest vectors from the graph

func (*HNSW[Vector]) SearchLayer

func (h *HNSW[Vector]) SearchLayer(level int, addr Pointer, q Vector, ef int) pq.Queue[Vertex]

Search "nearest" vectors on the layer

func (*HNSW[Vector]) Write

func (h *HNSW[Vector]) Write(w Writer) error

Write index to storage

type Node

type Node[Vector any] struct {
	Vector      Vector
	Connections [][]Pointer
}

Graph Node

type Nodes

type Nodes[Vector any] struct {
	Rank int
	Head Pointer
	Heap []Node[Vector]
}

Graph Nodes

type Option

type Option func(*Config)

Config Options

func With

func With(opts ...Option) Option

func WithEfConstruction

func WithEfConstruction(ef int) Option

Configure size of dynamic candidate list

func WithM

func WithM(m int) Option

Configures number of established connections from each node. M in [5 to 48] is recommended range. Small M gives better result for low dimensional data. Big M is better for high dimensional data. High M impacts on memory consumption

func WithRandomSource

func WithRandomSource(random rand.Source) Option

Configure Random Source

type Pointer

type Pointer = uint32

Pointer to Node

type Reader

type Reader interface{ Get([]byte) ([]byte, error) }

Getter interface abstract storage

type Vertex

type Vertex struct {
	Distance float32
	Addr     Pointer
}

Vertex to graph node

type Writer

type Writer interface{ Put([]byte, []byte) error }

Setter interface abstract storage