weavatrix-search-vector 0.3.1

Persistent, mutable, bounded vector candidate search for Rust and Weavatrix
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

use super::RoutingIndex;
use crate::error::SearchError;
use crate::vector::VectorStore;

impl RoutingIndex {
    pub(super) fn build(vectors: &VectorStore) -> Result<Self, SearchError> {
        let mut entries = Vec::new();
        entries
            .try_reserve_exact(vectors.len())
            .map_err(|_| SearchError::AllocationFailed)?;
        entries.extend((0..vectors.len()).map(|index| {
            (
                vectors.stored_routing_code(index),
                u32::try_from(index).expect("vector count is bounded by u32::MAX"),
            )
        }));
        entries.sort_unstable();
        Ok(Self { entries })
    }

    pub(super) fn estimated_bytes(&self) -> usize {
        self.entries
            .capacity()
            .saturating_mul(std::mem::size_of::<(u16, u32)>())
    }

    pub(super) fn append_candidates(&self, codes: &[u16], output: &mut Vec<u32>) {
        for code in codes {
            self.append_bucket(*code, output);
        }
    }

    fn append_bucket(&self, code: u16, output: &mut Vec<u32>) {
        let start = self.entries.partition_point(|entry| entry.0 < code);
        let end = self.entries.partition_point(|entry| entry.0 <= code);
        output.extend(self.entries[start..end].iter().map(|entry| entry.1));
    }
}