hnsw-rs

此crate提供了Yu.A. Malkov和D.A Yashunin论文的Rust实现

"使用分层可导航小世界图进行高效且鲁棒的近似最近邻搜索" (2016,2018) arxiv

功能

此crate基于anndists构建，可以使用以下距离

• 标准数值类型向量的常规距离，如L1、L2、余弦、Jaccard、Hamming，以及u16上的Levenshtein距离。

• 概率分布（f32和f64）之间的Hellinger距离和Jeffreys距离。需要注意的是，Jeffreys距离（对称化的Kullback-Leibler距离）不满足三角不等式。（余弦距离也不例外）。

• 概率分布（f32和f64）之间的Jensen-Shannon距离。它定义为Jensen-Shannon距离的平方根，是一个有界度量。参见Nielsen F. in Entropy 2019, 21(5), 485。

• 一个Trait，允许用户实现自己的距离。它接受满足T:Serialize+Clone+Send+Sync的类型T的数据切片。也可以使用C外部函数或闭包。

• 一个面向C和更具体地说面向Julia语言的接口。有关Julia用户的帮助，请参阅配套的Julia包HnswAnn.jl和构建段落。

hnsw实现提供

• 多线程插入和搜索请求。

• 导出和重新加载函数（请参阅hnswio模块），在构建完成后存储数据和图。这些功能部分依赖于Serde，因此T需要实现Serialize和Deserialized作为Serde的派生。还可以仅重新加载图而不重新加载数据本身。特定的类型（struct NoData，与NoDist距离相关联）用于此功能。

• 将Hnsw结构扁平化的转换，以保持点之间的邻域关系（而不包含它们的内部数据）在Hnsw结构内部（请参阅flatten.rs模块，FlatPoint和FlatNeighborhood）。因此，可以在低内存使用的情况下保留一些拓扑信息。

• 过滤：可以添加过滤器，以便只将满足过滤器条件的结果包含在结果集中。过滤是在搜索过程中进行的，因此它不是后过滤。目前有两种使用过滤器的方法，一种是将允许的ID添加到有序向量中并发送作为参数，或者可以定义一个函数，该函数在ID添加到结果集之前将被调用。
  这两种策略的示例在示例或测试目录中。如果想要将过滤器保存在位向量中，例如，可以为新类型实现可过滤特质。

• 支持在转储数据上使用mmap（不在图部分），这对于大型数据向量很有用。这使核心集和聚类计算能够在流式传输中进行，请参阅coreset和crates.io上的内容。

实现

图构建和搜索使用 crate进行多线程（请参阅和函数以及示例文件）。距离由anndists crate提供，请参阅构建部分。

构建

Simd

anndists crate中激活simd的两个功能

• 功能"simdeez_f"为x86_64处理器提供simd。使用进行编译，或在Cargo.toml中更改默认功能。要在M1芯片上编译此crate，只需不激活此功能即可。

• 功能"stdsimd"通过std::simd提供可移植的simd，但需要rust nightly

  。
  将此功能设置在features默认（或通过cargo命令）将激活rust nightly上的portable_simd功能。尚不支持所有（距离，类型）配对。（请参阅anndists crate）

Julia接口

默认情况下，crate是一个独立项目，构建静态库和可执行文件。要与配套的Julia包一起使用，需要构建动态库。这可以通过在Cargo.toml文件中取消注释（即删除#）来实现，即

#crate-type = ["cdylib"]

然后重新运行命令：cargo build --release。

这将在目标/release目录中生成.so文件。

算法和输入参数

该算法将点存储在层（最多16层），并构建图以从较稀疏的层搜索到最密集的层，通过从较稀疏层到最密集层（层0）构建链接来实现。

算法大致按以下步骤进行

在插入时，使用指数法则对新的点的层l进行采样，限制层数为16，因此层0是最密集的层，上层数据随着层的增加以指数方式减少。
在从上级到其层（l）的上层查找表中搜索该点的最近邻，因此我们应以相对较低的成本到达其层附近的新点。然后，在邻居的邻居表中搜索max_nb_connection最近邻（通过反向更新表）递归地从其层l向下到最密集的层0。

指数法则的尺度参数取决于一个点与其他点可能的最大连接数（参数max_nb_connection）。
具体来说，尺度参数选择如下：scale=1/ln(max_nb_connection)。

在构建图或搜索中出现的参数主要有

• max_nb_connection（在hnsw初始化中）从一个点到其他点的最大链接数。标准初始化值范围从16到64，值越高，耗时长。

• ef_construction（在hnsw初始化中）
  此参数控制插入时搜索邻居的宽度。标准初始化值从200到800，值越高，耗时长。

• max_layer（在hnsw初始化中）
  图中最大层数。必须小于或等于16。

• ef_arg（在搜索方法中）
  此参数控制最低层搜索的宽度，它必须大于请求的邻居数，但可以小于ef_construction。作为经验法则，它可以在请求的邻居数（搜索方法中的knbn arg）和max_nb_connection之间。

• keep_pruned和extend_candidates。
  这些参数在Malkov和Yashunin的论文中有描述，可以用于修改搜索策略。感兴趣的用户应查看论文以了解影响。默认值如论文中推荐。

基准和示例 (示例)

一些示例取自ann-benchmarks网站，召回率和请求/s在示例文件中的注释中给出。annhdf5模块实现了读取ann-benchmarks网站的标准化数据文件，只需下载必要的基准数据文件，并相应地修改源中的路径。然后运行：cargo build --release --features="simdeez_f" --examples .
在这些示例中，可以更改从并行搜索到串行搜索，以检查速度或修改参数以查看对性能的影响。

使用i9-13900HX 24核笔记本电脑，我们得到以下结果

1. fashion-mnist-784-euclidean：以0.977的召回率，每秒运行62000次搜索请求
2. ann-glove-25-angular：以0.979的召回率，以12000次/秒的速度搜索前100个邻居
3. sift1m基准测试：（128维度的100万个点）对前10个邻居的搜索请求以15000次/秒的速度运行，召回率为0.9907，或以8300次/秒的速度运行，召回率为0.9959，具体取决于参数。

此外，一个微小的crate bigann为BIGANN基准测试的前1000万个点提供结果，并可用于在此数据上调整参数。结果给出0.92到0.99之间的召回率，具体取决于请求数和参数。

从这个Mnist基准测试中提取的一些行显示了它对于f32和L2范数的工作方式

    //  reading data
    let anndata = AnnBenchmarkData::new(fname).unwrap();
    let nb_elem = anndata.train_data.len();
    let max_nb_connection = 24;
    let nb_layer = 16.min((nb_elem as f32).ln().trunc() as usize);
    let ef_c = 400;
    // allocating network
    let mut hnsw =  Hnsw::<f32, DistL2>::new(max_nb_connection, nb_elem, nb_layer, ef_c, DistL2{});
    hnsw.set_extend_candidates(false);
    // parallel insertion of train data
    let data_for_par_insertion = anndata.train_data.iter().map( |x| (&x.0, x.1)).collect();
    hnsw.parallel_insert(&data_for_par_insertion);
    //
    hnsw.dump_layer_info();
    //  Now the bench with 10 neighbours
    let mut knn_neighbours_for_tests = Vec::<Vec<Neighbour>>::with_capacity(nb_elem);
    hnsw.set_searching_mode(true);
    let knbn = 10;
    let ef_c = max_nb_connection;
    // search 10 nearest neighbours for test data
    knn_neighbours_for_tests = hnsw.parallel_search(&anndata.test_data, knbn, ef_c);
    ....

贡献

Sannsyn为Drop实现和FilterT trait做出了贡献。Petter Egesund添加了DistLevenshtein距离。

演变描述在这里

许可

根据您的要求，许可方式为以下之一

• Apache License，版本2.0，LICENSE-APACHE或https://apache.ac.cn/licenses/LICENSE-2.0
• MIT许可LICENSE-MIT或http://opensource.org/licenses/MIT

。