Skip to main content

spacedb_vector/
index.rs

1//! The on-node vector index — *query embedding in, top-k out, corpus stays*.
2//!
3//! The index holds the corpus: `(id, embedding)` entries that **never leave the
4//! node**. A [`search`](VectorIndex::search) takes a query embedding and returns
5//! only the top-k [`Match`]es — ids and similarity scores. The return type makes
6//! the privacy property structural: there is no way to read a stored vector back
7//! out of a search; the most an authorized caller learns is *which* items are
8//! near their query and *how* near.
9//!
10//! ## Algorithm
11//!
12//! S3 ships an **exact flat k-NN** search (scan every entry, rank, truncate). For
13//! a home-scale corpus that is correct and fast, and — unlike an approximate
14//! index — has perfect recall. Sub-linear ANN (HNSW / IVF-flat) is an optimization
15//! for very large corpora behind the same [`VectorIndex`] surface, deferred until
16//! corpus size demands it.
17
18use std::cmp::Ordering;
19
20use crate::error::{VectorError, VectorResult};
21
22/// How similarity is measured. `search` always returns the highest-scoring
23/// entries, so every metric is oriented "higher = more similar".
24#[derive(Clone, Copy, Debug, PartialEq, Eq)]
25pub enum Metric {
26    /// Cosine similarity in `[-1, 1]` (1 = identical direction). Magnitude-invariant.
27    Cosine,
28    /// Raw dot product (higher = more aligned and larger).
29    Dot,
30    /// Negative Euclidean distance (0 = identical, more negative = farther).
31    Euclidean,
32}
33
34impl Metric {
35    fn score(&self, a: &[f32], b: &[f32]) -> f32 {
36        match self {
37            Metric::Cosine => {
38                let (na, nb) = (norm(a), norm(b));
39                if na == 0.0 || nb == 0.0 {
40                    0.0
41                } else {
42                    dot(a, b) / (na * nb)
43                }
44            }
45            Metric::Dot => dot(a, b),
46            Metric::Euclidean => -l2(a, b),
47        }
48    }
49}
50
51/// A search hit: which entry, and how similar. **No vector is returned** — the
52/// corpus stays on the node.
53#[derive(Clone, Debug, PartialEq)]
54pub struct Match {
55    pub id: String,
56    pub score: f32,
57}
58
59struct Entry {
60    id: String,
61    vector: Vec<f32>,
62}
63
64/// An on-node embedding index.
65pub struct VectorIndex {
66    dim: usize,
67    metric: Metric,
68    entries: Vec<Entry>,
69}
70
71impl VectorIndex {
72    /// A new `dim`-dimensional index ranked by `metric`.
73    pub fn new(dim: usize, metric: Metric) -> Self {
74        Self {
75            dim,
76            metric,
77            entries: Vec::new(),
78        }
79    }
80
81    pub fn dim(&self) -> usize {
82        self.dim
83    }
84
85    pub fn len(&self) -> usize {
86        self.entries.len()
87    }
88
89    pub fn is_empty(&self) -> bool {
90        self.entries.is_empty()
91    }
92
93    /// Insert (or replace) the embedding for `id`. Errors on a dimension mismatch.
94    pub fn insert(&mut self, id: impl Into<String>, vector: Vec<f32>) -> VectorResult<()> {
95        if vector.len() != self.dim {
96            return Err(VectorError::DimMismatch {
97                expected: self.dim,
98                got: vector.len(),
99            });
100        }
101        let id = id.into();
102        if let Some(existing) = self.entries.iter_mut().find(|e| e.id == id) {
103            existing.vector = vector;
104        } else {
105            self.entries.push(Entry { id, vector });
106        }
107        Ok(())
108    }
109
110    /// Remove `id`. Returns whether it was present.
111    pub fn remove(&mut self, id: &str) -> bool {
112        let before = self.entries.len();
113        self.entries.retain(|e| e.id != id);
114        self.entries.len() != before
115    }
116
117    /// Return the top-`k` entries nearest to `query`, highest score first. Ties
118    /// break by id for deterministic (corroboratable) results. Errors on a
119    /// dimension mismatch.
120    pub fn search(&self, query: &[f32], k: usize) -> VectorResult<Vec<Match>> {
121        if query.len() != self.dim {
122            return Err(VectorError::DimMismatch {
123                expected: self.dim,
124                got: query.len(),
125            });
126        }
127        let mut scored: Vec<Match> = self
128            .entries
129            .iter()
130            .map(|e| Match {
131                id: e.id.clone(),
132                score: self.metric.score(query, &e.vector),
133            })
134            .collect();
135        scored.sort_by(|a, b| {
136            b.score
137                .partial_cmp(&a.score)
138                .unwrap_or(Ordering::Equal)
139                .then_with(|| a.id.cmp(&b.id))
140        });
141        scored.truncate(k);
142        Ok(scored)
143    }
144}
145
146fn dot(a: &[f32], b: &[f32]) -> f32 {
147    a.iter().zip(b).map(|(x, y)| x * y).sum()
148}
149
150fn norm(a: &[f32]) -> f32 {
151    dot(a, a).sqrt()
152}
153
154fn l2(a: &[f32], b: &[f32]) -> f32 {
155    a.iter()
156        .zip(b)
157        .map(|(x, y)| {
158            let d = x - y;
159            d * d
160        })
161        .sum::<f32>()
162        .sqrt()
163}