HNSW (Go)

Category: SDKs & Libraries
Technology: Go, Approximate Nearest Neighbor (ANN), Vector Search
Source: https://github.com/coder/hnsw

Overview

HNSW (Go) is a Go implementation of Hierarchical Navigable Small World (HNSW) graphs for fast approximate nearest neighbor (ANN) search over high-dimensional vectors. It can serve as an in-memory alternative to a vector database, suitable for embedding vector similarity search directly into Go applications and custom vector databases.

Features

Core Functionality

• In-memory HNSW graph implementation in pure Go.
• Approximate nearest neighbor search for high-dimensional vector data.
• Designed as an in-memory alternative to vector databases (e.g., Pinecone, Weaviate) with essential operations.

Data Model & Operations

• Insert
  • Operation: Insert a vector into the graph.
  • Complexity: ~O(log n).
• Delete
  • Operation: Delete a vector from the graph.
  • Complexity: ~O(M² · log n), where M is the maximum number of neighbors per node.
• Search
  • Operation: Search for nearest neighbors of a query vector.
  • Complexity: ~O(log n).
• Lookup
  • Operation: Retrieve a vector by ID.
  • Complexity: O(1).
• Configurable construction parameters (e.g., M, mL/Graph.Ml) to trade off speed, recall, and memory usage, following the original HNSW paper.

Go API & Usage

• Simple Go module import:

  go get github.com/coder/hnsw@main
  

• Graph creation via hnsw.NewGraph[IDType](), where the ID is generic (e.g., int).
• Node creation with hnsw.MakeNode(id, []float32{...}).
• Vector addition using Graph.Add(...).
• Nearest neighbor search using Graph.Search(queryVector, k).

Persistence & Serialization

• In-memory graph operations with optional persistent storage support.
• Import/Export via streams:
  • Graph.Export(io.Writer) — write graph to an io.Writer.
  • Graph.Import(io.Reader) — load graph from an io.Reader.