HNSW (Hierarchical Navigable Small World) Implementation in Go

High-performance HNSW implementation with AVX2 optimizations and parallel search.

Installation

go get github.com/BryceWayne/hnsw
go get golang.org/x/sys/cpu  # Required for AVX2 detection

Build with AVX2 support:

GOAMD64=v3 go build

Quick Start

import (
    "github.com/BryceWayne/hnsw"
    "golang.org/x/sys/cpu"
)

func main() {
    if cpu.X86.HasAVX2 {
        println("Using AVX2 optimizations")
    }

    // Create index
    index := hnsw.New(
        128,    // dimension
        16,     // M (max connections per layer)
        32,     // Mmax (max connections at layer 0)
        100,    // efConstruction
        hnsw.Euclidean,  // AVX2-optimized distance function
    )

    // Batch insert with parallel processing
    vectors := make(map[int]hnsw.Vector, 1000)
    for i := 0; i < 1000; i++ {
        vectors[i] = generateRandomVector(128)
    }
    index.BatchInsert(vectors, 100) // batch size 100

    // Parallel search
    results := index.Search(queryVector, 10) // ~9µs per search
}

Full Example

package main

import (
    "flag"
    "fmt"
    "math/rand"
    "sync"
    "time"
    "github.com/BryceWayne/hnsw"
    // Uncomment for AVX2 optimizations
    // "golang.org/x/sys/cpu"
)

var (
    dimension      = flag.Int("d", 128, "Vector dimension")
    numVectors     = flag.Int("n", 1000, "Number of vectors")
    connections    = flag.Int("m", 16, "Max connections per layer")
    maxConnections = flag.Int("mmax", 32, "Max connections at layer 0")
    efConstruction = flag.Int("ef", 100, "EF construction parameter")
    searchK        = flag.Int("k", 10, "Number of nearest neighbors")
    batchSize      = flag.Int("batch", 25, "Batch size for parallel insertions")
    parallel       = flag.Bool("parallel", true, "Enable parallel search")
    workerCount    = flag.Int("workers", runtime.GOMAXPROCS(0), "Number of worker threads") // Default is runtime.NumCPU()
)

func main() {
    flag.Parse()
    rand.Seed(time.Now().UnixNano())

    // Initialize index
    index := hnsw.New(
        *dimension,
        *connections,
        *maxConnections,
        *efConstruction,
        hnsw.Euclidean,
    )

    // Generate and insert vectors in batches
    vectors := make([]hnsw.Vector, *numVectors)
    for i := range vectors {
        vectors[i] = generateRandomVector(*dimension)
    }

    numBatches := (*numVectors + *batchSize - 1) / *batchSize
    for b := 0; b < numBatches; b++ {
        start := b * *batchSize
        end := min(start+*batchSize, *numVectors)

        var wg sync.WaitGroup
        for i := start; i < end; i++ {
            wg.Add(1)
            go func(id int, vec hnsw.Vector) {
                defer wg.Done()
                index.Insert(id, vec)
            }(i, vectors[i])
        }
        wg.Wait()
    }

    // Search
    queryVector := generateRandomVector(*dimension)

    // Default parallel search
    results := index.Search(query, 10)

    // Custom config for sequential search
    config := hnsw.SearchConfig{
        UseParallel: *useParallel,
        WorkerCount: *workerCount,
    }
    results := index.SearchWithConfig(query, 10, config)

    fmt.Printf("Found neighbors: %v\n", results)
}

Run with:

go run main.go -d 256 -n 10000 -m 32 -ef 100 -k 20 -batch 25

Run with custom parameters:

go run main.go \
  -d 256 \           # dimension
  -n 10000 \         # number of vectors
  -m 32 \            # max connections
  -ef 100 \          # ef construction
  -k 20 \            # k nearest neighbors
  -batch 25 \        # batch size
  -parallel=true \   # use parallel search
  -workers 16        # worker threads

Flag descriptions:

  -d int
        Vector dimension (default 128)
  -n int
        Number of vectors (default 1000)
  -m int
        Max connections per layer (default 16)
  -mmax int
        Max connections at layer 0 (default 32)
  -ef int
        EF construction parameter (default 100)
  -k int
        Number of nearest neighbors (default 10)
  -batch int
        Batch size for parallel insertions (default 25)
  -parallel
        Use parallel search (default true)
  -workers int
        Number of worker threads (default: CPU cores)

Performance impact:

• Parallel search (-parallel=true): ~20x speedup
• Worker count (-workers): Scale with available CPU cores
• Batch size (-batch): Memory vs speed tradeoff

API Reference

Types

type Vector []float64
type DistanceFunc func(Vector, Vector) float64

Functions

New

func New(dim, m, mmax, efConstruction int, distanceFunc DistanceFunc) *HNSW

Creates new HNSW index:

• dim: Vector dimension
• m: Max connections per layer
• mmax: Max connections at layer 0
• efConstruction: Search quality during construction (recommend 100-200)
• distanceFunc: Distance metric function (Euclidean or Cosine provided)

Insert

func (h *HNSW) Insert(id int, vec Vector)

Inserts vector with given ID. Thread-safe.

Search

func (h *HNSW) Search(vec Vector, k int) []int

Returns IDs of k nearest neighbors. Thread-safe.

Delete

func (h *HNSW) Delete(id int)

Removes vector from index. Thread-safe.

Save/Load

func (h *HNSW) Save(filename string) error
func Load(filename string, distanceFunc DistanceFunc) (*HNSW, error)

Persistence functions.

Distance Functions

• Euclidean: Standard Euclidean distance
• Cosine: Cosine similarity as distance

Performance

Sample benchmark (256d vectors, 10k points):

{
  "dimension": 256,
  "num_vectors": 10000,
  "connections": 32,
  "max_connections": 32,
  "ef_construction": 100,
  "distance_metric": "euclidean",
  "build_time": 556174141967,
  "search_time": 376427279,
  "memory_usage": 33609840
}

Project Structure

hnsw/
├── examples/      # Example usage
├── distance.go    # Distance metrics
├── hnsw.go       # Main HNSW implementation
├── node.go       # Node implementation
├── serialize.go  # Serialization logic
└── types.go      # Core data types

Algorithm Overview

HNSW (Hierarchical Navigable Small World) is an algorithm for approximate nearest neighbor search that creates a layered graph structure. Each layer is a "small world" graph, with the number of connections between nodes decreasing as you go up the layers.

HNSW Structure

graph TD
    subgraph L3 [Layer 3]
        Entry[Entry Point]
    end
    subgraph L2 [Layer 2]
        N2_1(( )) --- N2_2(( ))
    end
    subgraph L1 [Layer 1]
        N1_1(( )) --- N1_2(( )) --- N1_3(( ))
    end
    subgraph L0 [Layer 0 - Ground]
        N0_1(( )) --- N0_2(( )) --- N0_3(( )) --- N0_4(( ))
    end

    Entry -.-> N2_1
    N2_2 -.-> N1_2
    N1_3 -.-> N0_3

Loading

The hierarchical structure consists of layers:

• L0 (ground layer): Most connections, finest-grained search
• L1-L2: Balanced layers for navigation
• L3+: Skip-list layers for fast traversal

Key properties:

• Entry point at top layer
• Increasing connectivity at lower layers
• Skip-list organization for efficient search
• Layer count scales logarithmically with data size

Search Process

flowchart TD
    Start([Start]) --> Entry[Enter at Layer 3]
    Entry --> TraverseL3[Traverse L3]
    TraverseL3 --> DescendL2{Descend}
    DescendL2 --> TraverseL2[Traverse L2]
    TraverseL2 --> DescendL1{Descend}
    DescendL1 --> TraverseL1[Traverse L1]
    TraverseL1 --> DescendL0{Descend}
    DescendL0 --> SearchL0[Search Layer 0]
    SearchL0 --> Result([Found Nearest Neighbors])

Loading

1. Begin at entry point in highest layer
2. Explore current layer to find closest node
3. Descend to next layer and repeat
4. Final search in bottom layer (Layer 0)

Insertion Process

flowchart TD
    Start([New Node]) --> MaxLevel{Select Max Level}
    MaxLevel --> Find[Find Neighbors at Level]
    Find --> Connect[Create Connections]
    Connect --> Prune{Connections > M?}
    Prune -- Yes --> Remove[Prune Weakest]
    Prune -- No --> NextLevel
    Remove --> NextLevel
    NextLevel{More Levels?} -- Yes --> Descend[Descend Level]
    Descend --> Find
    NextLevel -- No --> Done([Inserted])

Loading

1. Randomly select maximum level for new node
2. Find nearest neighbors at each level
3. Create bidirectional connections
4. Maintain connection limits through pruning

Deletion Process

flowchart TD
    Start([Delete Node]) --> Locate[Locate Node]
    Locate --> Neighbors[Identify Neighbors]
    Neighbors --> Remove[Remove Incoming Edges]
    Remove --> Reconnect[Reconnect Neighbors]
    Reconnect --> CheckM{Connections < M_min}
    CheckM -- Yes --> Repair[Repair Connectivity]
    CheckM -- No --> Done
    Repair --> Done([Deleted])

Loading

The deletion process involves:

1. Locate target node and connections
2. Remove incoming connections from neighbors
3. Reconnect affected neighbors to maintain graph connectivity
4. Update layer structures as needed
5. Thread-safe concurrent deletions

Key aspects:

• Maintains graph connectivity after node removal
• Updates neighbor connections optimally
• Handles edge cases (entry point deletion)
• M/Mmax limits preserved

Network Properties

graph TD
    Top((Entry)) --> Mid1(( ))
    Top --> Mid2(( ))
    Mid1 --> Bot1(( ))
    Mid1 --> Bot2(( ))
    Mid2 --> Bot3(( ))
    Mid2 --> Bot4(( ))
    Bot1 --- Bot2
    Bot2 --- Bot3
    Bot3 --- Bot4

Loading

The network maintains efficiency through:

• Balance of short/long-range connections
• Limited connections per node (M/Mmax)
• Hierarchical navigation structure

EF Parameter Impact

flowchart LR
    EF[EF Parameter] --> Low[Low Value]
    EF --> High[High Value]
    Low --> Fast[Faster Search]
    Low --> LowAcc[Lower Accuracy]
    High --> Slow[Slower Search]
    High --> HighAcc[Higher Accuracy]

Loading

EF (Exploration Factor) controls:

• Lower EF: Faster search, less accurate
• Higher EF: Slower search, more accurate

Batch Operations

sequenceDiagram
    participant Main
    participant W1 as Worker 1
    participant W2 as Worker 2
    participant Index

    Main->>W1: Batch 1 (25 items)
    Main->>W2: Batch 2 (25 items)

    par Parallel Insert
        W1->>Index: Insert Nodes
        W2->>Index: Insert Nodes
    end

    W1-->>Main: Done
    W2-->>Main: Done

Loading

The index supports efficient batch operations:

1. Data is split into configurable batch sizes (default 25 vectors)
2. Worker threads process batches in parallel
3. Each worker handles node insertion and connection formation
4. Concurrent operations maintain thread safety
5. Progress tracking for large batches

Recommended batch sizes:

• Small datasets (<10K): 25-50 vectors
• Large datasets: 100-200 vectors
• Memory constrained: Reduce to 10-25

Parameter Tuning

1. M/Mmax (Connection Limits):

   • M: 12-16 for high-dimensional data
   • Mmax: Usually 2*M for ground layer

2. EF (Search Quality):

   • Lower values (64): Faster, less accurate
   • Higher values (128+): Slower, more accurate
   • Construction: 100-200 recommended

3. Distance Metrics:

   • Cosine: Best for text/embedding vectors
   • Euclidean: Better for coordinate-based data

Testing

Run the test suite:

go test -v ./...

Run benchmarks:

go test -bench=. ./...

Performance

Current test results:

go test -v ./...
?       github.com/BryceWayne/hnsw/examples     [no test files]
=== RUN   TestBatchOperations
--- PASS: TestBatchOperations (0.01s)
=== RUN   TestEuclidean
--- PASS: TestEuclidean (0.00s)
=== RUN   TestCosine
--- PASS: TestCosine (0.00s)
=== RUN   TestNew
--- PASS: TestNew (0.00s)
=== RUN   TestInsertAndSearch
--- PASS: TestInsertAndSearch (0.00s)
=== RUN   TestSearch
=== RUN   TestSearch/Find_nearest_to_origin
=== RUN   TestSearch/Find_two_nearest
--- PASS: TestSearch (0.00s)
    --- PASS: TestSearch/Find_nearest_to_origin (0.00s)
    --- PASS: TestSearch/Find_two_nearest (0.00s)
=== RUN   TestParallelSearch
--- PASS: TestParallelSearch (0.00s)
=== RUN   TestConcurrentSearches
--- PASS: TestConcurrentSearches (0.01s)
=== RUN   TestDelete
--- PASS: TestDelete (0.00s)
=== RUN   TestSaveLoad
--- PASS: TestSaveLoad (0.00s)
=== RUN   TestConcurrentInserts
--- PASS: TestConcurrentInserts (0.00s)
PASS
ok      github.com/BryceWayne/hnsw      0.022s

Benchmark results (Intel i9-12900K):

Operation                            Time/op
Sequential Insert                    ~269µs
Sequential Search                    ~146µs
Parallel Search                      ~ 29µs
Batch Insert                         ~262µs
Batch Search                         ~170ns

Dimension Scaling (ns/op):
Size      Dim    Time
1K        32     32,611
1K        128    29,973
1K        512    18,247
10K       32     20,716
10K       128    18,288
10K       512    13,414
100K      32     24,083
100K      128    16,302
100K      512    13,650

Key Features:

• 5x speedup with parallel search
• Sub-microsecond batch search
• Better performance with higher dimensions
• Optimal for large datasets (100K+ vectors)

Hardware Requirements

• AVX2 support for SIMD optimizations
• Multiple CPU cores for parallel search
• Recommended: 16GB+ RAM for 100K+ vectors

Tuning Guidelines

1. Batch Size:

   • Small datasets (<10K): 25-50
   • Large datasets: 100-200

2. Worker Count:

   • Default: Number of CPU cores
   • High load: 2x CPU cores

3. Memory vs Speed:

   • Lower M (8-12): Less memory, slower search
   • Higher M (16-32): Faster search, more memory

Performance Tips

1. Index Construction:

   • Use batch insertions (25-50 vectors per batch)
   • Pre-generate vectors before insertion
   • Lower efConstruction (100) for faster builds

2. Search Optimization:

   • Adjust EF based on accuracy needs
   • Use appropriate distance metric

3. Memory Management:

   • Monitor node count vs. available RAM
   • Consider saving/loading for large datasets

License

MIT License

Copyright (c) 2024 Bryce Wayne