Module hnsw

Hierarchical Navigable Small World (HNSW) graph index.

A multi-layer graph structure for approximate nearest neighbor search. Based on Malkov & Yashunin (2018) with single-threaded insert/search.

This is a vanilla HNSW — no temporal filtering, decay, or timestamp graph. Those are added in Layer 4+.

Algorithm Overview

• Insert: assign random level, greedily descend from top to target level, then do beam search at each level to find neighbors
• Search: greedy descend from top to level 0, then beam search on level 0
• Levels: higher levels are sparser (fewer nodes), lower levels are denser

Example

use cvx_index::hnsw::{HnswGraph, HnswConfig};
use cvx_index::metrics::CosineDistance;

let config = HnswConfig { m: 16, ef_construction: 200, ef_search: 50, ..Default::default() };
let mut graph = HnswGraph::new(config, CosineDistance);

// Insert vectors
graph.insert(0, &[1.0, 0.0, 0.0]);
graph.insert(1, &[0.9, 0.1, 0.0]);
graph.insert(2, &[0.0, 1.0, 0.0]);

// Search
let results = graph.search(&[1.0, 0.0, 0.0], 2);
assert_eq!(results[0].0, 0); // closest is itself
assert_eq!(results[1].0, 1); // second closest

Re-exports

pub use bayesian_scorer::CandidateFeatures;

pub use bayesian_scorer::ScoringWeights;

pub use bayesian_scorer::WeightLearner;

pub use concurrent::ConcurrentTemporalHnsw;

pub use region_mdp::RegionMdp;

pub use temporal::TemporalHnsw;

pub use temporal_edges::TemporalEdgeLayer;

pub use temporal_graph::CausalSearchResult;

pub use temporal_graph::TemporalGraphIndex;

pub use typed_edges::EdgeType;

pub use typed_edges::TypedEdgeStore;

Modules

bayesian_scorer

Bayesian retrieval scoring for multi-factor candidate ranking (RFC-013 Part C).

concurrent

Thread-safe concurrent HNSW index.

metadata_store

In-memory metadata store for HNSW nodes.

optimized

Advanced HNSW optimizations.

partitioned

Time-partitioned temporal HNSW index (RFC-008).

region_mdp

Region MDP: Markov Decision Process over HNSW semantic regions (RFC-013 Part A).

streaming

Streaming Window Index — RFC-008 Phase 3.

temporal

Spatiotemporal HNSW index (ST-HNSW).

temporal_edges

Temporal edge layer — successor/predecessor links between entity time points.

temporal_graph

Temporal Graph Index — HNSW extended with temporal successor edges (RFC-010).

temporal_lsh

Temporal Locality-Sensitive Hashing (T-LSH) — RFC-008 Phase 2.

typed_edges

Typed edge layer for relational structure over HNSW nodes (RFC-013 Part B).

Structs

HnswConfig

HNSW index configuration.

HnswGraph

HNSW graph index for approximate nearest neighbor search.

HnswNode 🔒

A node in the HNSW graph.

HnswSnapshot 🔒

Serializable snapshot of an HNSW graph (excludes metric + RNG).

OrdF32Entry 🔒

Wrapper for f32 ordering in BinaryHeap (total order via bit comparison).

Functions

recall_at_k

Compute recall@k: fraction of true kNN found by approximate search.

Type Aliases

NeighborList 🔒

Neighbor list: inline up to M entries (no heap allocation).