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::deletemarks 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§
- Hnsw
Index - An HNSW index for approximate nearest neighbor search.
- Search
Result - A search result: (id, distance).