hnsw-rs

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

"使用分层可导航小世界图进行高效且鲁棒的近似最近邻"（2016，2018） arxiv

许可证

根据以下任一许可证授权

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

由您选择。

此软件是在我在CEA工作时编写的。

功能

此crate提供

• 标准数值类型的向量通常距离，如L1、L2、余弦、Jaccard、Hamming。

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

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

• u16上的Levenshtein距离。

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

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

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

• 导出和重新加载功能（见模块hnswio），用于在构建完成后存储数据和图。这些设施部分依赖于Serde，因此T需要实现由Serde派生的Serialize和Deserialized。还可以只重新加载图而不是数据本身。为此，专门设计了一个特定类型（struct NoData），与NoDist距离相关联。用于此功能。

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

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

实现

图构建和搜索使用 crate进行多线程（见和函数，以及示例文件）。
提供基于

crate的Simd Avx2实现，目前用于大多数在

中大量使用的距离以及

的Hamming距离。参见构建。

构建

Simd

• 由

  crate提供的simd可以通过“simdeez_f”功能访问，适用于x86_64处理器。使用

  进行编译……要在M1芯片上编译此crate，只需不激活此功能。当std::simd进入rust稳定版时，它将成为默认。

• 尽管如此，仍然可以使用std::simd进行实验。使用带有功能stdsimd（

  ）进行编译，激活临时的crate packed_simd_2。这需要rust nightly，并取消注释文件

  的第一行。不建议这样做，因为（现在）只提供了u32x16和u64x8类型的Hamming距离。

Julia接口

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

文件中的行

#crate-type = ["cdylib"]

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

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

算法和输入参数

算法按层存储点（最多16层），并构建一个图，以便通过从较稀疏的层到最密集的层（层0）构建链接来从较稀疏的层搜索到最密集的层。

算法大致按以下顺序进行

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

指数法的尺度参数取决于一个点与其他点可能的最大连接数（参数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参数）和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：搜索请求以每秒59900次的速度运行，召回率为0.977
2. ann-glove-25-angular：搜索前100个邻居，以召回率0.979和每秒12640次的速度运行
3. sift1m基准：（128维度的1百万个点）搜索前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 特性做出了贡献。Petter Egesund 添加了 DistLevenshtein 距离。

注意

1. 许多依赖项的升级。从 simple_logger 更改为 env_logger。日志记录器在文件 src/lib.rs 中初始化一次，不能重复初始化。日志级别可以通过 RUST_LOG 环境变量按模块进行调节或关闭。请参阅 env_logger crate 文档。
2. 一个名为 edlib_rs 的 rust crate 提供了对 excellent edlib C++ 库的接口 （参照 edlib），可以在 edlib_rs 或 crate.io 上找到。它可以用于在 &[u8] 上定义用户自定义距离，具有普通、前缀或后缀模式（这在基因组对齐中很有用）。
3. 该库不再依赖于 hdf5 和 ndarray。它们是用于示例的开发依赖项，这简化了兼容性问题。
4. 为切片添加了插入方法，以便更容易与 ndarray crate 一起使用。
5. simd/avx2 现在需要功能 "simdeez_f"。因此，默认情况下，crate 可以在 M1 芯片上编译，并过渡到 std::simd。
6. 添加了 DistPtr 和使用此距离类型进行转储/重新加载的可能性。（请参阅 load_hnsw_with_dist 函数）
7. 在 crate probminhash 中实现了仅适用于 f64 的 Hamming。