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 的组合。HM-ANN 实现了低搜寻提早和高搜寻精度，特地是在数据集无奈装入单机无限 DRAM 的状况下。与最先进的近似近邻（ANN）搜寻计划相比，该算法具备显著的劣势。
动机
因为 DRAM 容量无限，ANN 搜索算法在查问精度和查问提早之间进行了根本的衡量。为了在 DRAM 中存储索引以实现疾速查问，有必要限度数据点的数量或存储压缩的向量，这两者都会侵害搜寻的准确性。基于图形的索引（如 HNSW）具备优越的查问运行工夫性能和查问精度。然而，当在十亿规模的数据集上操作时，这些索引也会耗费 TiB 等级的 DRAM。
还有其余的变通方法来防止让 DRAM 以原始格局存储十亿规模的数据集。当一个数据集太大，无奈装入单台机器的 DRAM 时，就会应用数据压缩的办法，如对数据集的点进行乘积量化。然而，因为量化过程中精度的损失，这些索引在压缩数据集上的召回率通常很低。Subramanya 等人 [1] 摸索了利用固态硬盘 SSD 实现十亿级 ANN 搜寻的办法，该办法称为 Disk-ANN，其中原始数据集存储在 SSD 上，压缩后的示意办法存储在 DRAM 上。
Heterogeneous Memory 的介绍
内存 / 存储的层次结构与 HM
图片起源: http://nvmw.ucsd.edu/nvmw2021…
Heterogeneous memory (HM) 代表了疾速但小的 DRAM 和慢速但大的 PMem 的组合。DRAM 是每个古代服务器中都能找到的硬件，其访问速度绝对较快。新的 PMem 技术，如英特尔® Optane™DC Persistent Memory Modules，补救了基于 NAND-based flash（SSD）和 DRAM 之间的差距，打消了 I / O 瓶颈。PMem 像 SSD 一样能够在断电状况下长久化数据，又像 DRAM 一样可由 CPU 间接对每一个 Byte 寻址。Renen 等人 [2] 发现，在配置的试验环境中，PMem 的读取带宽比 DRAM 低 2.6 倍，而写入带宽低 7.5 倍。
HM-ANN 的设计
HM-ANN 是一种精确而疾速的十亿级 ANN 搜索算法，在单机上运行时无需压缩。HM-ANN 的设计概括了 HNSW 的思维，其分层构造天然适宜 HM。HNSW 由多层组成: 只有第 0 层蕴含整个数据集，其余每一层都蕴含其正下方那一层的一个子集。
一个 3 层 HNSW 的例子
图片起源: https://arxiv.org/pdf/1603.09…
下层的元素，只包含数据集的子集，耗费了整个存储耗费的一小部分。这一景象使它们十分适合去被搁置在 DRAM 中。这样一来，HM-ANN 上的大部分搜寻都会产生在下层，这就最大限度地利用了 DRAM 的快速访问个性。然而，在 HNSW 中大多数搜寻产生在底层。
最底层承载着整个数据集，这使得它适宜被放在 PMem 中。因为拜访第 0 层的速度较慢，最好是每个查问只拜访一小部分，并升高拜访频率。
图构建算法
HM-ANN 的索引结构例子
图片起源: http://nvmw.ucsd.edu/nvmw2021…
HM-ANN 结构的要害思维是构建高质量的下层，以便为第 0 层的搜寻提供更好的导航领导能力。因而，大多数内存拜访产生在 DRAM 中，所以 PMem 中的拜访则被缩小。为了实现这一点，HM-ANN 的构建算法有一个自上而下的 selection 阶段和一个自下而上的 promotion 阶段。
自上而下的插入阶段建设了一个 navigable small-world graph，因为最底层是放在 PMem 上的。
自下而上的促成阶段从底层 promote pivot 点，以造成搁置在 DRAM 上的下层，而不会失去很多准确性。如果在第 1 层创立了第 0 层元素的高质量投影，那么第 0 层的搜寻只需几跳就能找到查问的精确近邻。
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 的索引搜寻例子
图片起源: http://nvmw.ucsd.edu/nvmw2021…
该搜索算法由两个阶段组成: fast memory search 与 parallel layer-0 search with prefetching.
Fast memory search
与 HNSW 雷同，DRAM 中的搜寻从最顶层的入口点开始，而后从顶层到第 2 层执行 1 -greedy search。为了放大第 0 层的搜寻空间，HM-ANN 在第 1 层进行搜寻，搜寻估算为 efSearchL1，这限度了第 1 层的 candidate list 的大小。HNSW 只应用一个 entry point，但在 HM-ANN 中，第 0 层和第 1 层之间的关系比任何其余两层之间解决得更加特地。
Parallel layer-0 search with prefetching
在底层，HM-ANN 将上述来自搜寻第 1 层的 candidates 平均离开，并将其视为 entry points，以执行 parallel multi-start 1-greedy search with threads。每次搜寻进去的 top candidates 被收集起来，以找到 best candidates。家喻户晓，从第 1 层下到第 0 层正好是进入 PMem。并行搜寻暗藏了 PMem 的提早，并充分利用内存带宽，在不减少搜寻工夫的状况下进步搜寻品质。
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）。
十亿规模的算法比拟
在 Table 1 中，比拟了不同的基于图的索引的索引工夫和内存耗费。HNSW 在建设索引时速度最快，HM-ANN 比 HNSW 多须要 8% 的工夫。在总体存储应用方面，HM-ANN 索引比 HSNW 大 5 -13%，因为它将更多的节点从第 0 层推广到第 1 层。
在 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 的成果
在 Figure 3 中，random promotion 和 high-degree promotion strategies 在同一配置下进行了比拟。high-degree promotion strategies 的成果优于 baseline。在达到 95%、99% 和 99.5% 的召回率指标时，high-degree promotion strategies 的体现比 random promotion 快 1.8 倍、4.3 倍和 3.9 倍。
内存治理技术的性能
Figure 5 蕴含了 HNSW 和 HM-ANN 之间的一系列步骤，以显示 HM-ANN 的每项优化对其改良的奉献。BP 代表索引构建中自下而上的 promotion，PL0 代表 Parallel layer-0 search，DP 代表从 PMem 到 DRAM 的数据 prefetching。每走一步，HM-ANN 的搜寻性能都会被进一步推高。
论断
一种新的基于图的索引和搜索算法，称为 HM-ANN，将基于图的 ANN 搜索算法的分层设计与 HM 中的快慢内存异质性进行了映射。评估表明，HM-ANN 是一种新的最先进的实用于十亿数据集的索引。
在学术界和工业界中，在 PMem 上建设索引正变得越来越风行。为了加重 DRAM 的压力，Disk-ANN[1]是一个建设在 SSD 上的索引，然而 SSD 吞吐量显著低于 PMem。然而，建设 HM-ANN 依然须要几天工夫，这与 Disk-ANN 的构建工夫没有数量级的区别。咱们置信，通过更认真地利用 PMem 的个性（例如，意识到 PMem 的粒度为 256 字节），以及应用指令 bypass cache lines，是能够优化 HM-ANN 的索引工夫。咱们还预计，未来会提出更多的长久存储设备的办法。
参考资料
[1] Suhas Jayaram Subramanya and Devvrit and Rohan Kadekodi and Ravishankar Krishaswamy and Ravishankar Krishaswamy: DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, NIPS, 2019
（https://www.microsoft.com/en-…）
（https://papers.nips.cc/paper/…）
[2] Alexander van Renen and Lukas Vogel and Viktor Leis and Thomas Neumann and Alfons Kemper: Persistent Memory I/O Primitives, CoRR & DaMoN, 2019
（https://dl.acm.org/doi/abs/10…）
（https://arxiv.org/abs/1904.01614）
作者：罗济高，Zilliz 实习研究员，本科毕业于慕尼黑工业大学，目前是该校数据工程与剖析业余研究生在读。趣味畛域蕴含关系数据库与性能剖析，喜爱钻研关系数据库內核，对数据库各个子畛域的停顿领有高度好奇心。他的 Github 账号是 https://github.com/cakebytheo…，博客地址是 https://cakebytheoceanluo.git…