iqdb-hnsw 1.0.0

HNSW approximate nearest-neighbor graph index for fast vector search - part of the iQDB family.
Documentation
  • HNSW graph — hierarchical navigable small-world graph per Malkov & Yashunin (2016), built incrementally at insert time
  • Standard knobs — m, ef_construction, ef_search, filter_widen, and a fixed seed for reproducibility
  • Insert / search / delete — beam-search top-k; tombstone deletion (graph-repair compaction is a tracked post-freeze optimisation)
  • Deterministic — a seeded SplitMix64 (no rand dep); same insert order + seed ⇒ byte-identical graph and identical results
  • Filtered traversal — metadata filtering via iqdb-filter, with the beam widened by filter_widen to mitigate post-filter under-return
  • One ordering invariant — all metric math via iqdb-distance; DotProduct negated so Hit.distance is smaller-is-nearer across all five metrics

Installation

[dependencies]
iqdb-hnsw = "1.0"

Quick start

use std::sync::Arc;

use iqdb_hnsw::{HnswConfig, HnswIndex};
use iqdb_index::{Index, IndexCore};
use iqdb_types::{DistanceMetric, SearchParams, VectorId};

// Default operating point (m=16, ef_construction=200, ef_search=64), or tune it:
let cfg = HnswConfig::default().with_ef_search(128);
let mut idx = HnswIndex::new(2, DistanceMetric::Euclidean, cfg)?;

idx.insert(VectorId::from(1u64), Arc::<[f32]>::from(&[0.0, 0.0][..]), None)?;
idx.insert(VectorId::from(2u64), Arc::<[f32]>::from(&[3.0, 4.0][..]), None)?;
idx.insert(VectorId::from(3u64), Arc::<[f32]>::from(&[1.0, 0.0][..]), None)?;

let hits = idx.search(&[0.0, 0.0], &SearchParams::new(2, DistanceMetric::Euclidean))?;
assert_eq!(hits[0].id, VectorId::U64(1)); // nearest to the origin

Filtered search

Attach an iqdb-filter predicate to the query. Only records whose metadata satisfies it are returned — evaluated during traversal, with the beam widened by filter_widen so a selective filter still fills k:

use std::sync::Arc;

use iqdb_hnsw::{HnswConfig, HnswIndex};
use iqdb_index::{Index, IndexCore};
use iqdb_types::{DistanceMetric, Filter, Metadata, SearchParams, Value, VectorId};

let mut idx = HnswIndex::new(2, DistanceMetric::Euclidean, HnswConfig::default())?;

let red: Metadata = [("color".to_string(), Value::String("red".to_string()))]
    .into_iter().collect();
let blue: Metadata = [("color".to_string(), Value::String("blue".to_string()))]
    .into_iter().collect();

idx.insert(VectorId::from(1u64), Arc::<[f32]>::from(&[0.0, 0.0][..]), Some(red))?;
idx.insert(VectorId::from(2u64), Arc::<[f32]>::from(&[0.1, 0.0][..]), Some(blue))?;

let params = SearchParams {
    filter: Some(Filter::eq("color", Value::String("red".to_string()))),
    ..SearchParams::new(5, DistanceMetric::Euclidean)
};
let hits = idx.search(&[0.0, 0.0], &params)?;
assert!(hits.iter().all(|h| h.id == VectorId::U64(1))); // id 2 is nearer, but blue

Tuning

The defaults (m = 16, ef_construction = 200, ef_search = 64) are the SIFT-calibrated operating point. Override any field with the with_* builders; larger m / ef_construction raise recall and build cost, larger ef_search raises recall and per-query cost:

use iqdb_hnsw::HnswConfig;

let cfg = HnswConfig::default()
    .with_m(32)            // denser graph: higher recall, more memory
    .with_ef_construction(400) // more thorough build
    .with_ef_search(128);  // wider query beam: higher recall, slower search

Status

v1.0.0 is stable: the multi-layer graph, insert with the Alg 4 neighbour heuristic, beam search, tombstone delete, and iqdb-filter traversal all ship, wired to the stable (1.0) iQDB spine. Correctness is pinned by a headline recall@10 ≥ 0.95 gate across all five metrics, measured against the exact iqdb-flat ground truth, plus determinism, contract, edge, layer-distribution, and tombstone suites. Zero unsafe (#![forbid(unsafe_code)]). The public API is frozen until 2.0 — only additive, non-breaking changes from here. A real-data SIFT/GIST recall diagnostic (tests/sift_recall.rs) and a criterion latency/recall bench ship alongside. See the API reference and the ROADMAP.

Where It Fits

iqdb-hnsw is the flagship Phase-3 index. It builds on:

  • iqdb-types — core types
  • iqdb-distance — distance kernels
  • iqdb-index — implements the trait
  • iqdb-filter — filter during graph traversal

and is consumed by iqdb for approximate search and by iqdb-build for bulk graph construction. Persistence is the separate iqdb-persist crate's job.

Standards

Built to the iQDB Rust standard. See REPS.md (Rust Efficiency & Performance Standards) and dev/DIRECTIVES.md for the engineering law and the definition of done. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.