mih-rs

Rust实现的多索引哈希（MIH），用于在汉明空间中对二进制码进行邻域搜索，如论文所述

Norouzi, Punjani, and Fleet, Fast exact search in Hamming space with multi-index hashing, IEEE TPAMI, 36(6):1107– 1119, 2014.

根据基准测试结果，在1000万个64位码中，mih-rs在k = 1..100的情况下，比线性搜索快19−94倍。

特性

• 两种邻域搜索类型： mih-rs提供了两种搜索操作

  • 范围搜索 找到与给定码的汉明距离在某个范围内的邻域码。
  • Top-K搜索 找到最接近给定码的前K个码。

• 快速且内存高效实现： 数据结构基于稀疏哈希表构建，遵循原始实现。

• 参数自动设置： mih-rs会根据给定的数据库自动设置MIH的最佳参数（尽管你也可以手动设置）。

• 序列化： mih-rs支持序列化和反序列化索引。

示例

use mih_rs::Index;

// Database of codes
let codes: Vec<u64> = vec![
    0b1111111111111111111111011111111111111111111111111011101111111111, // #zeros = 3
    0b1111111111111111111111111111111101111111111011111111111111111111, // #zeros = 2
    0b1111111011011101111111111111111101111111111111111111111111111111, // #zeros = 4
    0b1111111111111101111111111111111111111000111111111110001111111110, // #zeros = 8
    0b1101111111111111111111111111111111111111111111111111111111111111, // #zeros = 1
    0b1111111111111111101111111011111111111111111101001110111111111111, // #zeros = 6
    0b1111111111111111111111111111111111101111111111111111011111111111, // #zeros = 2
    0b1110110101011011011111111111111101111111111111111000011111111111, // #zeros = 11
];

// Query code
let qcode: u64 = 0b1111111111111111111111111111111111111111111111111111111111111111; // #zeros = 0

// Construct the index
let index = Index::new(codes).unwrap();

// Find the ids of neighbor codes whose Hamming distances are within 2
let mut searcher = index.range_searcher();
let answers = searcher.run(qcode, 2);
assert_eq!(answers, vec![1, 4, 6]);

// Find the ids of the top-4 nearest neighbor codes
let mut searcher = index.topk_searcher();
let answers = searcher.run(qcode, 4);
assert_eq!(answers, vec![4, 1, 6, 0]);

// Serialization/Deserialization
let mut data = vec![];
index.serialize_into(&mut data).unwrap();
let other = Index::<u64>::deserialize_from(&data[..]).unwrap();
assert_eq!(index, other);

二进制码类型

mih_rs::Index可以从类型为mih_rs::CodeInt的向量构建，该类型是一个支持popcount操作的原始整数特性。目前，此库为mih_rs::CodeInt定义了u8、u16、u32和u64。

基准测试

timeperf_topk.rs提供了在二进制码类型u32和u64上对MIH和LinearSearch算法进行Top-K搜索的基准测试。

以下表格显示了在以下设置下每查询平均搜索时间（毫秒）的结果

• 数据库：来自均匀分布的N个随机码。
• 查询集：来自均匀分布的100个随机码。
• 机器：2019年款四核英特尔酷睿i5 @2.4 GHz，16 GB RAM的MacBook Pro。
• 库版本：v0.2.0

对于 u32 的结果

对于 u64 的结果

许可

此库是MIT许可下的免费软件。