Skip to main content

Crate iqdb_ivf

Crate iqdb_ivf 

Source
Expand description

§iqdb-ivf

Inverted-file (IVF) approximate nearest-neighbour index for the iQDB vector database. IvfIndex partitions the vector space with deterministic k-means and answers queries by exhaustively scanning only the IvfConfig::n_probes clusters whose centroids are nearest to the query. It is the complement to a graph index: more memory-efficient at very large scale and with more predictable latency, because every query probes the same fixed number of clusters.

Two variants share one surface. IVF-Flat (the default) stores vectors verbatim and scores probed clusters exactly. IVF-PQ (use_pq = true) compresses each vector to a Product-Quantization code and scores by asymmetric distance (ADC), optionally exact-reranking a shortlist against the retained vectors. Both honour metadata filters and the same smaller-is-nearer ordering contract as every other iQDB index.

§Tiered API

§Design

  • Storage is n_clusters inverted lists, each owning the (VectorId, Arc<[f32]>, Option<Metadata>, seq) tuples for the vectors assigned to its centroid. The payload is wrapped in Arc<[f32]> so the engine shares one allocation between this index and its record store — the same zero-copy contract iqdb-flat and iqdb-hnsw use.
  • Training is mandatory. IvfIndex::new returns an untrained index; the four entry points that depend on centroids (insert, insert_batch, search, and search_batch) short-circuit with iqdb_types::IqdbError::InvalidConfig until the caller invokes IvfIndex::train. This UX cliff is intentional and documented loudly.
  • K-means runs through a seeded SplitMix64 PRNG, accumulating centroid sums in f64 and reducing in fixed order, so identical seed plus identical sample produce byte-identical centroids on every platform.
  • All distance math is delegated to iqdb_distance::compute_batch; IVF never reimplements a metric. For iqdb_types::DistanceMetric::DotProduct the raw inner product is negated at the boundary so iqdb_types::Hit::distance is always smaller-is-nearer, identical across all five metrics.
  • Top-k selection uses a bounded max-heap keyed on (distance, seq) via f32::total_cmp — O(n log k), NaN-safe, and deterministic: ties break on insertion order (lower sequence number wins).
  • Metadata filtering goes through iqdb_filter::FilterEvaluator; pathological filters surface as iqdb_types::IqdbError::InvalidFilter at query time, before any cluster data is touched.

§Example

use std::sync::Arc;

use iqdb_index::{Index, IndexCore};
use iqdb_ivf::{IvfConfig, IvfIndex};
use iqdb_types::{DistanceMetric, SearchParams, VectorId};

let cfg = IvfConfig::default()
    .with_n_clusters(2)
    .with_n_probes(2)
    .with_training_sample_size(16)
    .with_seed(7);
let mut idx = IvfIndex::new(2, DistanceMetric::Euclidean, cfg)?;

// Train on a representative sample before any insert / search.
let sample: Vec<Vec<f32>> = vec![
    vec![0.0, 0.0], vec![0.1, -0.1], vec![-0.1, 0.1],
    vec![10.0, 10.0], vec![10.1, 9.9], vec![9.9, 10.1],
];
let sample_refs: Vec<&[f32]> = sample.iter().map(|v| v.as_slice()).collect();
idx.train(&sample_refs)?;

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

let hits = idx.search(&[0.0, 0.0], &SearchParams::new(1, DistanceMetric::Euclidean))?;
assert_eq!(hits.len(), 1);
assert_eq!(hits[0].id, VectorId::U64(1));

Structs§

Hit
One result of a similarity search: a matched record and its distance.
IvfClusterStats
Diagnostic snapshot of inverted-list occupancy.
IvfConfig
Configuration for crate::IvfIndex construction (see iqdb_index::Index::new).
IvfIndex
IVF-Flat approximate nearest-neighbour index.

Constants§

VERSION
The version of this crate, taken from Cargo.toml at compile time.