矢音：快速Vamana索引

矢音是一个轻量级向量数据库，具有增量索引，基于FreshVamana。该项目得到了KinicDAO的支持，并为KinicVectorDB的向量索引后端提供动力。

入门指南

通过指定特性中的进度条，可以检查索引进度。

[dependencies]
vectune = {version = "0.1.0", features = ["progress-bar"]}

要快速使用SIMD执行欧几里得距离计算，需要在示例中指定nightly。如果VSCode中的rust-analyzer对#![feature(portable_simd)]出错，请设置您的.vscode/settings.json。

{
  "rust-analyzer.server.extraEnv": {
      "RUSTUP_TOOLCHAIN": "nightly"
  },
}

示例

设置和运行

要使用SIFT1M数据集进行测试，请执行以下命令。SIFT1M是一个包含100万个数据点、每个数据点具有128个维度的数据集。

curl ftp://ftp.irisa.fr/local/texmex/corpus/sift.tar.gz -o examples/test_data/sift.tar.gz
tar -xzvf examples/test_data/sift.tar.gz -C examples/test_data

cargo +nightly run --release --features progress-bar --example sift1m

工作原理

使用Builder对数据进行索引，并在图上执行搜索和插入操作。

use vectune::{Builder, GraphInterface, PointInterface};

let points = Vec::new();
for vec in base_vectors {
    points.push(Point(vec.to_vec()));
}

let (nodes, centroid) = Builder::default()
    .progress(ProgressBar::new(1000))
    .build(points);

let mut graph = Graph::new(nodes, centroid);

let k = 50;

let (top_k_results, _visited) = vectune::search(&mut graph, &Point(query.to_vec()), k);

PointInterface 特性

您需要定义所使用的向量的维度和数据类型，以及计算距离的方法。

请实现以下四个方法

• distance(&self,other: &Self) -> f32
• fn dim() -> u32
• fn add(&self, other: &Self) -> Self
• fn div(&self, divisor: &usize) -> Self

distance()可以使用SIMD进行优化。请参阅./examples/src/bin/sift1m.rs。

以下示例提供了一个简单的实现。

use vectune::PointInterface;

#[derive(Serialize, Deserialize, Clone, Debug)]
struct Point(Vec<f32>);
impl Point {
    fn to_f32_vec(&self) -> Vec<f32> {
        self.0.iter().copied().collect()
    }
    fn from_f32_vec(a: Vec<f32>) -> Self {
        Point(a.into_iter().collect())
    }
}
impl PointInterface for Point {
    fn distance(&self, other: &Self) -> f32 {
        self.0
            .iter()
            .zip(other.0.iter())
            .map(|(a, b)| {
                let c = a - b;
                c * c
            })
            .sum::<f32>()
            .sqrt()
    }
    fn dim() -> u32 {
        384
    }
    fn add(&self, other: &Self) -> Self {
        Point::from_f32_vec(
            self.to_f32_vec()
                .into_iter()
                .zip(other.to_f32_vec().into_iter())
                .map(|(x, y)| x + y)
                .collect(),
        )
    }
    fn div(&self, divisor: &usize) -> Self {
        Point::from_f32_vec(
            self.to_f32_vec()
                .into_iter()
                .map(|v| v / *divisor as f32)
                .collect(),
        )
    }
}

GraphInterface 特性

为了将整个图适应于除了SSD或其他内存类型之外的其他存储解决方案，您需要实现GraphInterface。

请实现以下十一个方法

• fn alloc(&mut self, point:P) -> usize
• fn free(&mut self, id: &usize)
• fn cemetery(&self) -> Vec<usize>
• fn clear_cemetery(&mut self)
• fn 反向链接(&self, id: &usize) -> Vec<usize>
• fn 获取(&mut self, id: &usize) -> (P,Vec<usize>)
• fn size_l(&self) -> usize
• fn size_r(&self) -> usize
• fn size_a(&self) -> f32
• fn start_id(&self) -> usize
• fn 覆盖输出边(&mut self, id: &usize, edges: Vec<usize>)

self.get()定义为&mut self，因为它处理来自SSD和其他存储设备的缓存。

在vectune::search()中，self.cemetery()返回的节点被标记为墓碑，并从搜索结果中排除。此外，它们在vectune::delete()中永久删除。

在添加或删除节点时需要管理反向链接。这在vectune::delete()中得到了应用。

以下示例提供了一个简单的内存实现。

use vectune::GraphInterface;
use itertools::Itertools;

struct Graph<P>
where
    P: VPoint,
{
    nodes: Vec<(P, Vec<u32>)>,
    backlinks: Vec<Vec<u32>>,
    cemetery: Vec<u32>,
    centroid: u32,
}

impl<P> VGraph<P> for Graph<P>
where
    P: VPoint,
{
    fn alloc(&mut self, point: P) -> u32 {
        self.nodes.push((point, vec![]));
        self.backlinks.push(vec![]);
        (self.nodes.len() - 1) as u32
    }

    fn free(&mut self, _id: &u32) {
        // todo!()
    }

    fn cemetery(&self) -> Vec<u32> {
        self.cemetery.clone()
    }

    fn clear_cemetery(&mut self) {
        self.cemetery = Vec::new();
    }

    fn backlink(&self, id: &u32) -> Vec<u32> {
        self.backlinks[*id as usize].clone()
    }

    fn get(&mut self, id: &u32) -> (P, Vec<u32>) {
        let node = &self.nodes[*id as usize];
        node.clone()
    }

    fn size_l(&self) -> usize {
        125
    }

    fn size_r(&self) -> usize {
        70
    }

    fn size_a(&self) -> f32 {
        2.0
    }

    fn start_id(&self) -> u32 {
        self.centroid
    }

    fn overwirte_out_edges(&mut self, id: &u32, edges: Vec<u32>) {
        for out_i in &self.nodes[*id as usize].1 {
            let backlinks = &mut self.backlink(out_i);
            backlinks.retain(|out_i| out_i != id)
        }

        for out_i in &edges {
            let backlinks = &mut self.backlink(out_i);
            backlinks.push(*id);
            backlinks.sort();
            backlinks.dedup();
        }

        self.nodes[*id as usize].1 = edges;
    }
}

索引

• a是RobustPrune的阈值；增加它会导致更多长距离边和更少近邻边。
• r表示边的数量；增加它会增加图的复杂性，但会减少孤立节点的数量。
• l是贪婪搜索的保留列表的大小；增加它允许构建更精确的图，但计算成本呈指数增长。
• seed用于初始化随机图；它允许固定随机图，这在调试中可能很有用。

let (nodes, centroid) = Builder::default()
    .set_a(2.0)
    .set_r(70)
    .set_l(125)
    .set_seed(11677721592066047712)
    .progress(ProgressBar::new(1000))
    .build(points);

搜索

k表示top-k结果的数量。需要满足k <= l。

vectune::search(&mut graph, &point, k);

插入

vectune::insert(&mut graph, point);

删除

从图中完全删除由graph.cemetery()返回的节点。

vectune::delete(&mut graph);