Module nsg 

NSG (Navigable Small World Graph) index

NSG is a graph-based approximate nearest neighbor search algorithm that builds a monotonic navigable graph structure. It provides:

• Monotonic Search Path: Guarantees that search always moves closer to query
• Memory Efficiency: Controlled out-degree for compact graph structure
• High Accuracy: Better recall than NSW with similar or better performance
• Fast Search: O(log n) expected search complexity

Algorithm Overview

NSG construction has two stages:

1. Build initial kNN graph using any ANN algorithm
2. Refine graph to ensure navigability and monotonicity

The key innovation is the monotonic search property: each hop in the search path gets closer to the query point, preventing cycles and dead-ends.

References

• Fu, Cong, et al. “Fast approximate nearest neighbor search with the navigable small world graph.” arXiv preprint arXiv:1707.00143 (2017).

Example

use oxirs_vec::{Vector, VectorIndex};
use oxirs_vec::nsg::{NsgConfig, NsgIndex};

let config = NsgConfig {
    out_degree: 32,
    candidate_pool_size: 100,
    search_length: 50,
    ..Default::default()
};

let mut index = NsgIndex::new(config).unwrap();

// Add vectors
for i in 0..1000 {
    let vector = Vector::new(vec![i as f32, (i * 2) as f32, (i * 3) as f32]);
    index.insert(format!("vec_{}", i), vector).unwrap();
}

// Build the NSG structure
index.build().unwrap();

// Search
let query = Vector::new(vec![100.0, 200.0, 300.0]);
let results = index.search_knn(&query, 10).unwrap();

Structs

NsgConfig

Configuration for NSG index

NsgIndex

NSG index structure

NsgStats

NSG index statistics

Enums

DistanceMetric

Distance metrics supported by NSG