<br>

HM-ANN: Efficient Billion-Point Nearest Neighbor Search on Heterogenous Memory 是一篇被 2020 年 Conference on Neural Information Processing Systems (NeurIPS 2020). 本文提出了一种基于图的相似性搜索的新型算法，称为 HM-ANN。

该算法在现代硬件设置中同时考虑了内存异质性和数据异质性。HM-ANN 可以在单台机器上实现十亿级的相似性搜索，同时没有采用任何数据压缩技术。异质存储器（HM）代表了快速但小的 DRAM 和缓慢但大的 PMem 的组合。

  动机

还有其他的变通方法来避免让 DRAM 以原始格式存储十亿规模的数据集。当一个数据集太大，无法装入单台机器的 DRAM 时，就会使用数据压缩的方法，如对数据集的点进行乘积量化。但是，由于量化过程中精度的损失，这些索引在压缩数据集上的召回率通常很低。Subramanya 等人[1]探索了利用固态硬盘 SSD 实现十亿级 ANN 搜索的方法，该方法称为 Disk-ANN ，其中原始数据集存储在 SSD 上，压缩后的表示方法存储在 DRAM 上。

  Heterogeneous Memory 的介绍

内存/存储的层次结构与HM

图片来源: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-presentation_slides.pdf

PMem 像 SSD 一样可以在断电情况下持久化数据，又像 DRAM 一样可由 CPU 直接对每一个 Byte 寻址。Renen 等人 [2] 发现，在配置的实验环境中，PMem 的读取带宽比 DRAM 低 2.6 倍，而写入带宽低 7.5 倍。

  HM-ANN 的设计

图片来源: https://arxiv.org/pdf/1603.09320.pdf

• 上层的元素，只包括数据集的子集，消耗了整个存储消耗的一小部分。这一现象使它们非常合适去被放置在 DRAM 中。这样一来，HM-ANN 上的大部分搜索都会发生在上层，这就最大限度地利用了 DRAM 的快速访问特性。然而，在 HNSW 中大多数搜索发生在底层。

图构建算法

• HM-ANN 没有使用 HNSW 的 random selection for promotion，而是使用高度推广策略 high-degree promotion strategy，将第 0 层中度数最高的元素推广到第1层。对于更高的层，HM-ANN 根据 promotion rate 将高度数节点推广到上层。

• HM-ANN 将更多的节点从第 0 层 promote 到第 1 层，并为第 1 层的每个元素设置更大的最大邻居数。上层节点的数量是由可用的 DRAM 空间决定的。由于第 0 层不存储在 DRAM 中，因此使存储在 DRAM 中的每一层更密集，可以提高搜索质量。

图搜索算法

HM-ANN的索引搜索例子

HM-ANN 在 DRAM 中实现了一个 software-managed buffer，在 DRAM 访问发生之前从 PMem 中 prefetch 数据。当搜索第 1 层时，HM-ANN 异步地将 efSearchL1中的那些 candidates 的邻居元素及其在第 1 层的连接从 PMem 复制到 buffer。当第 0 层的搜索发生时，一部分数据已经在 DRAM 中被 prefetched 了，这就隐藏了访问 PMem 的延迟，导致了更短的查询时间。这与 HM-ANN 的设计目标相吻合，即大部分内存访问发生在 DRAM 中，而 PMem 中的内存访问被减少。

  性能测试

在 HM-ANN 这个论文中，对这个新索引算法进行了广泛的评估。所有的实验都是在一台装有 Intel Xeon Gold 6252 CPU@2.3GHz 的机器上进行的。它使用DDR4（96GB）作为快速内存，Optane DC PMM（1.5TB）作为慢速内存。对五个数据集进行了评估。BIGANN、DEEP1B、SIFT1M、DEEP1M 和 GIST1M。对于十亿规模的测试，包括以下方案：基于十亿规模量化的方法（IMI+OPQ 和 L&C），以及非压缩的方法（HNSW 和 NSG）。

十亿规模的算法比较

在 Figure 1 中，对不同索引的查询性能进行了分析。图1（a）和（b）显示，HM-ANN 在 1 毫秒内取得了 >95% 的 top-1 召回率。图1（c）和（d）显示， HM-ANN 在 4 毫秒内获得了 >90% 的 top-100 召回率。与其他所有方法相比，HM-ANN 提供了更好的 latency-recall 性能。

百万规模的算法比较

在 Figure 2 中，不同索引的查询性能在纯 DRAM 环境下进行了分析。HNSW、NSG 和 HM-ANN 是用一个适合 DRAM 容量的 300 万规模的数据集进行评估的。HM-ANN 仍然取得了比 HNSW 更好的查询性能。原因是，当它们都旨在实现 99% 的召回率目标时，HM-ANN 的距离计算总数（平均 850 次/查询）要少于 HNSW（平均 900 次/查询）。

High-degree promotion的效果

内存管理技术的性能

  结论

一种新的基于图的索引和搜索算法，称为 HM-ANN，将基于图的 ANN 搜索算法的分层设计与 HM 中的快慢内存异质性进行了映射。评估表明，HM-ANN 是一种新的最先进的适用于十亿数据集的索引。

Github @Milvus-io|CSDN @Zilliz Planet|Bilibili @Zilliz-Planet

本文分享自微信公众号 - ZILLIZ（Zilliztech）。
如有侵权，请联系 [e-mail] 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。