跳到主要内容

二进制哈希索引基准测试

本研究比较了Faiss中的三种非穷尽（Non-exhaustive）二进制索引方式：

  • IndexBinaryIVF：通过k-means聚类算法获得一组中心点（centroid），将空间进行划分。在查询时，会访问nprobe个聚类中心（即访问指定数量的聚类）。
  • IndexBinaryHash：使用二进制向量的前b位作为哈希表的键，将向量存储到对应的哈希桶中。查询时，会访问与查询向量哈希值汉明距离（Hamming distance）小于nflip的所有桶。
  • IndexBinaryMultiHash：相当于构建了nhash个类似的哈希表。查询时，所有哈希表中返回结果的集合被统一考虑。这种方式是Norouzi等人在CVPR'12中提出的“多索引哈希快速汉明空间搜索（Fast Search in Hamming Space with Multi-Index Hashing）”。

所有方法的“真实结果”（ground truth）由IndexBinaryFlat索引给出。本文关注的主要是范围检索（range search），即找到汉明距离在给定半径内的所有向量。

实验设置

测试环境​

输入包含50,000,000 + 10,000个256比特二进制哈希向量。这些向量是通过卷积神经网络（CNN）处理图片后得到并二值化的。前5000万条向量作为数据库，其余1万条用作查询。这些数据均为随机抽样。

精度与效率衡量标准​

由于每个索引算法都会返回查询向量与数据库向量的精确距离，我们主要关注召回率（recall），即能否检索到所有符合要求的向量。因此，精度评价指标是“范围检索召回率”。

查询效率可通过以下方式衡量：

  • 实际耗时（Wall clock time）
    • 利用多线程搜索所得真实耗时。
    • 优点：具体直观。缺点：受多种参数影响。
    • 本次实验索引均在内存（RAM）中进行搜索。
  • 距离计算次数（Number of distance computations）
    • 直接反映需被扫描的内存数据量（通常是瓶颈）。
  • 随机访问次数（Number of random accesses）
    • 对所有类型的索引来说，通常是在一次随机访问之后进行多次连续（顺序）扫描。
    • 当数据存储在数据库等外部媒介中时，随机访问开销尤其值得注意。

匹配和距离的统计信息​

在实际分布下，很多向量间的汉明距离很小：

距离分布直方图

这是图片特征描述子的分布特性造成的。如果是随机均匀分布的256位描述子，距离低至15或20几乎不可能（因为二项分布特性）。

每个查询的结果数量（按每个查询返回结果的数量降序排列，在500万样本上统计）如下所示：

每个查询结果数量分布

可以看到呈Zipf分布（少数查询有大量命中，多数查询只有很少结果），但有一些特殊性：

  • 查询结果数量有一个上限，且跨越多个半径范围。这有可能和某些“病毒内容”有关，可能也解释了前一张图中的突变。
  • 在较小半径下，非常多的查询没有任何结果。

实验结果

首先对比IndexBinaryHash和IndexBinaryIVF的检测效率。

固定半径下：哈希 vs. IVF​

下方结果以半径15为例，通过调整检索参数获得不同效率点：

  • 对IndexBinaryIVF，检索参数为nprobe（即搜索时访问的聚类中心数），通常设为2的幂次。
  • 对IndexBinaryHash，检索参数为nflip（即搜索时允许的汉明距离，或允许多少比特不同）。
距离比较

从距离计算数来看，哈希索引明显优于IVF。对比随机访问次数：

随机访问数对比

IVF在4096个中心点时表现有一些优势，但此时倒排表（inverted lists）过长，现实意义不大。

半径影响分析​

将目标召回率固定为99%，选取实现该召回率所需最低代价（最小nprobe/nhash）的参数组合，比对不同半径的性能：

距离计算随半径变化

几点观察：

  • 可实现的检索效率点是离散的，因为其受IndexBinaryHash允许的比特翻转数（bit flips），或IndexBinaryIVF的nprobe（这里两者均为2的幂次）限制。
  • 在较小半径下，哈希索引的距离计算次数较少，效率明显更高。
  • 半径增大（大于32）时，IVF反而更优。注意b=32情况下，所需位翻转数极高，导致搜索极慢（图像随着半径截断）。
  • b=32时，哈希表中桶数为3900万，绝大多数桶内只存1个值。这时，随机访问数变成了更为合理的效率度量。

以搜索时间为指标，结果如下：

搜索时间对比

同样，在半径30左右，IVF和哈希的效率分界明显。

位顺序洗牌的影响​

目前我们直接用二进制哈希的前几位作为哈希表键值。那么，如果随机打乱位顺序，会对性能有何影响？我们在b=24、半径=15的设定下，多次随机洗牌后得到以下结果：

位顺序洗牌影响

从结果看，位的顺序确实影响过大。例如在召回率0.95时，最差的洗牌比正常顺序的开销高2-3倍。

备注

位顺序对IVF没有影响，因IVF使用的是k-means聚类。

多索引哈希（Multi-Index Hashing）对比单索引哈希​

我们将半径设为15，比较单哈希表和多哈希表的效果。这里同时考察了在不同哈希表数量和bit数下，第一个达到0.99召回率的检索点。

多索引哈希效果对比

观察与结论：

  • 当nhash=0时即为单表（sanity check），结果与nhash=1的IndexBinaryMultiHash完全一致。
  • 增加哈希表数量可略微减少需要计算的距离数。
  • 但哈希表越多，随机访问次数也按比例增加（未画出），且每一次距离计算都需要访问一次内存。因此，MultiHash需更多内存和随机访问，未必优于单哈希。

总结

  • 在小半径情况下，二进制哈希索引与IVF效果持平甚至更优。
  • 多索引哈希在一些场景下是个有趣的选择，但需要更大的内存和更多的随机访问，需视实际需求权衡。