Skip to main content

Module hnsw

Module hnsw 

Source
Expand description

HNSW (Hierarchical Navigable Small World) graph index.

Implements the algorithm from Malkov & Yashunin (2018) for approximate nearest neighbor search with logarithmic query time and high recall.

Key design decisions:

  • Single-owner, no locking. The index is meant to live inside one Kōra shard worker and is accessed through &mut self / &self. No interior mutability or atomics are needed.
  • Lazy deletion. HnswIndex::delete marks nodes as deleted without removing them from the graph, keeping neighbour connectivity intact and avoiding expensive edge repair.
  • Deterministic level generation. A simple xorshift64 PRNG seeded at construction produces reproducible layer assignments, which simplifies testing and benchmarking.

Structs§

HnswIndex
An HNSW index for approximate nearest neighbor search.
SearchResult
A search result: (id, distance).