编者按：

以图搜图、商品举荐、社交举荐等社会场景中潜藏了大量非结构化数据，这些数据被工程师们表白为具备隐式语义的高维向量。为了更好应答高维向量检索这一关键问题，杭州电子科技大学计算机专业硕士王梦召等人摸索并实现了「效率和精度最优衡量的近邻图索引」，并在数据库顶会 VLDB 2021 上发表成绩。

作为连贯生产和科研的桥梁，Zilliz 钻研团队始终与学界放弃交换、洞察畛域前沿。此次，王梦召来到 Z 星，从钻研动机、算法剖析、试验观测和优化探讨等维度开展讲讲最新的科研成果。

以下是他的干货分享，点击这里可取得论文全文。

高维数据检索：基于近邻图的近似最近邻搜索算法试验综述

导言

向量检索是很多 AI 利用必不可少的根底模块。近年来，学术界和工业界提出了很多优良的基于近邻图的 ANNS 算法以及相干优化，以应答高维向量的检索问题。然而针对这些算法，目前不足对立的试验评估和比拟剖析。

为了优化算法设计、进一步落地工业利用，咱们实现了论文《A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search》。该论文聚焦实现了效率和精度最优衡量的近邻图索引，综述了 13 种具备代表性相干算法，试验在丰盛的真实世界数据集上执行。咱们的奉献可总结如下：

依据图索引的特色，咱们将基于近邻图的 ANNS 算法划分为四类，这给了解现存算法提供了一个新的视角。在此基础上，咱们论述了算法间的继承和倒退关系，从而梳理出算法的倒退脉络；

咱们合成所有算法为 7 个对立的细粒度组件，它们形成一个残缺的算法执行流程，从而实现了算法的原子级剖析。咱们能够偏心评估当前工作在某一组件的优化通过管制其它组件统一；

咱们采纳多样的数据集（包含 8 个真实世界数据集，它们包含视频、语音、文本和图像生成的高维向量）和指标评估以后算法的全面性能；

咱们提供了不同场景下最优算法举荐、算法优化领导、算法改良示例、钻研趋势和挑战的剖析探讨。

钻研动机

依据以下观测，咱们对 13 种基于近邻图的 ANNS 算法进行了比拟剖析和试验综述：

目前，学术界和工业界提出 10 余种常见的近邻图算法，但对于这些算法的正当分类和比拟剖析较为不足。依据咱们的钻研，这些算法的索引构造可归结为 4 种根底的图构造，但这些图存在着十分多的问题，如复杂度太低等。所以，在这 4 种图构造根底上有多种优化，如对绝对邻域图（RNG）优化就蕴含 HNSW、DPG、NGT、NSG、SPTAG 等算法。

很多现有的论文从“分子”角度评估基于近邻图的 ANNS 算法（宏观角度）。然而，咱们发现，这些算法有一个对立的“化学表达式”，它们还可再向下细分为“原子”（宏观角度），从“原子”角度剖析能够产生一些新发现，比方很多算法都会用到某一“原子”（HNSW，NSG，KGraph，DPG 的路由是雷同的）。

除了搜寻效率和精度的衡量之外，基于近邻图的 ANNS 算法的其它特色（蕴含在索引构建和搜寻中）也间接影响了最终的搜寻性能。在搜寻性能逐步达到瓶颈的状况下，咱们对于索引构建效率、内存耗费等指标给予了器重。

一个算法的优越性并不是变化无穷的，数据集的特色在其中起着至关重要的作用。比方，在 Msong（语音生成的向量数据集）上 NSG 的减速是 HNSW 的 125 倍；然而，在 Crawl（文本生成的向量数据集）上 HNSW 的减速是 NSG 的 80 倍。咱们在多样的数据集上执行试验评估，从而对算法造成更全面的意识。

近邻图算法“分子”级剖析

在剖析基于近邻图的 ANNS 算法之前，首先给大家介绍下 4 个经典的图构造，即：德劳内图（DG）、绝对畛域图（RNG）、K 近邻图（KNNG）、最小生成树（MST）。如图 1 所示，这四种图构造的差别次要体现在选边过程，简略总结如下：DG 确保任意 3 个顶点 x, y, z 造成的三角形 xyz 的外接圆外部及圆上不能有除了 x, y, z 之外的其它顶点；RNG 要确保 (b) 中月牙形区域内不能有其它点，这里的月牙形区域是别离以 x 和 y 为圆心，x 与 y 之间的间隔为半径的两个圆的交加区域；KNNG 每个顶点连贯 K 个最近的街坊；MST 在保障联通性的状况下所有边的长度（对应两个顶点的间隔）之和最小。

图 1 四种图构造在雷同的数据集上的构建后果

接下来，我将基于图 1 中的 4 个图构造来梳理 13 个基于近邻图的 ANNS 算法。为了防止翻译造成了了解偏差，算法名应用英文简称，算法的原论文链接、局部高质量的中文介绍、局部代码请见参考资料。各算法之间更宏观的分割可参考论文中的表 2 和图 3。

算法 1：NSW

NSW 是对 DG 的近似，而 DG 能确保从任意一个顶点登程通过贪心路由获取准确的后果（即召回率为 1）。NSW 是一个相似于“交通枢纽”的无向图，这会导致某些顶点的出度激增，从论文的表 11 可知，NSW 在某些数据集上的最大出度可达几十万。NSW 通过增量插入式的构建，这确保了全局连通性，论文表 4 中可知，NSW 的连通重量数均为 1。NSW 具备小世界导航性质：在构建晚期，造成的边间隔较远，像是一条“高速公路”，这将晋升搜寻的效率；在构建前期，造成的边间隔较近，这将确保搜寻的精度。

原文：https://www.sciencedirect.com…

中文介绍：https://blog.csdn.net/u011233…

代码：https://github.com/kakao/n2

算法 2：HNSW

HNSW 在 NSW 的根底上有两个优化：“层次化”和“选边策略”。层次化的实现较为直观：不同间隔范畴的边通过档次出现，这样能够在搜寻时造成相似于跳表构造，效率更高。选边策略的优化原理是：如果要给某个顶点连贯 K 个街坊的话，NSW 抉择 K 个间隔最近的，而 HNSW 从大于 K 个最近的顶点外面选出更离散散布的街坊（见参考资料 1）。因而，从选边策略思考，HNSW 是对 DG 和 RNG 的近似。

原文：https://ieeexplore.ieee.org/a…

中文介绍：https://blog.csdn.net/u011233…

代码：https://github.com/kakao/n2

算法 3：FANNG

FANNG 的选边策略与 HNSW 是一样的，都是对 RNG 近似。FANNG 比 HNSW 更早提出，不过以后 HNSW 失去更广泛的利用，可能的起因是：

（1）FANNG 的选边策略是在暴力构建的近邻图的根底上实现的，构建效率很低；

（2）HNSW 通过增量式构建且引入分层策略，构建和搜寻效率都很高；

（3）HNSW 开源了代码，FANNG 则没有。

原文：https://www.cv-foundation.org…

算法 4：NGT

NGT 是雅虎日本开源的向量检索库，外围算法基于近邻图索引。NGT 在构建近邻图时相似于 NSW，也是对 DG 的近似，后续有一些度调整优化，其中最无效的门路优化也是对 RNG 的近似（论文的附件 B 也给出了证实）。

原文 1：https://link.springer.com/cha…

原文 2：https://arxiv.org/abs/1810.07355

代码：https://github.com/yahoojapan…

算法 5：SPTAG

SPTAG 是微软公布的向量检索库，它的构建过程基于分治策略，即迭代地划分数据集，而后在每个子集上构建近邻图，接着归并子图，最初通过邻域流传策略进一步优化近邻图。上述过程旨在构建一个尽可能准确的 KNNG。在搜寻时，SPTAG 采纳树索引和图索引交替执行的计划，即先从树上获取距查问较近的点作为在图上搜寻的起始点执行路由，当陷入部分最优时持续从树索引上获取入口点，反复上述操作直至满足终止条件。

原文 1：https://dl.acm.org/doi/abs/10…

原文 2：https://ieeexplore.ieee.org/a…

原文 3：https://ieeexplore.ieee.org/a…

中文介绍 1：https://blog.csdn.net/wheneve…

中文介绍 2：https://cloud.tencent.com/dev…

代码：https://github.com/microsoft/…

代码应用：https://blog.csdn.net/qq_4025…

算法 6：KGraph

KGraph 是对 KNNG 的近似，是一种面向个别度量空间的近邻图构建计划。基于街坊的街坊更可能是街坊的思维，KGraph 可能疾速构建一个高精度的 KNNG。后续的很多算法（比方 EFANNA、DPG、NSG、NSSG）都是在该算法的根底上的进一步优化。

原文：https://dl.acm.org/doi/abs/10…

中文介绍：https://blog.csdn.net/wheneve…

代码：https://github.com/aaalgo/kgraph

算法 7：EFANNA

EFANNA 是基于 KGraph 的优化。两者的差异次要体现在近邻图的初始化：KGraph 是随机初始化一个近邻图，而 EFANNA 是通过 KD 树初始化一个更准确的近邻图。此外，在搜寻时，EFANNA 通过 KD 树获取入口点，而 KGraph 随机获取入口点。

原文：https://arxiv.org/abs/1609.07228

中文介绍：https://blog.csdn.net/wheneve…

代码：https://github.com/ZJULearnin…

算法 8：IEH

类比 EFANNA，IEH 暴力构建了一个准确的近邻图。在搜寻时，它通过哈希表获取入口点。

原文：https://ieeexplore.ieee.org/a…

算法 9：DPG

在 KGraph 的根底上，DPG 思考顶点的街坊散布多样性，防止彼此之间十分靠近的街坊反复与指标顶点连边，最大化街坊之间的夹角，论文的附件 4 证实了 DPG 的选边策略也是对 RNG 的近似。此外，DPG 最终增加了反向边，是无向图，因而它的最大出度也是十分高的（见论文附件表 11）。

原文：https://ieeexplore.ieee.org/a…

中文介绍：https://blog.csdn.net/wheneve…

代码：https://github.com/DBW

算法 10：NSG

NSG 的设计思路与 DPG 简直是一样的。在 KGraph 的根底上，NSG 通过 MRNG 的选边策略思考街坊散布的平均性。NSG 的论文中将 MRNG 的选边策略与 HNSW 的选边策略做了比照，例证了 MRNG 的优越性。论文中的附件 1 证实了 NSG 的这种选边策略与 HNSW 选边策略的等价性。NSG 的入口点是固定的，是与全局质心最近的顶点。此外，NSG 通过 DFS 的形式强制从入口点至其它所有点都是可达的。

原文：http://www.vldb.org/pvldb/vol…

中文介绍：https://zhuanlan.zhihu.com/p/…

代码：https://github.com/ZJULearnin…

算法 11：NSSG

NSSG 的设计思路与 NSG、DPG 简直是一样的。在 KGraph 的根底上，NSSG 通过 SSG 选边策略思考街坊散布的多样性。NSSG 认为，NSG 适度裁边了（见论文表 4），相比之下 SSG 的裁边要松弛一些。NSG 与 NSSG 另一个重要的差别是，NSG 通过贪心路由获取候选街坊，而 NSSG 通过街坊的一阶扩大获取候选街坊，因而，NSSG 的构建效率更高。

原文：https://ieeexplore.ieee.org/a…

中文介绍：https://zhuanlan.zhihu.com/p/…

代码：https://github.com/ZJULearnin…

算法 12：Vamana

简略来说，Vamana 是 KGraph、HNSW 和 NSG 三者的联合优化。在选边策略上，Vamana 在 HNSW（或 NSG）的根底上减少了一个调节参数，选边策略为 HNSW 的启发式选边，取不同的值执行了两遍选边。

原文：http://harsha-simhadri.org/pu…

中文介绍：https://blog.csdn.net/wheneve…

算法 13：HCNNG

HCNNG 是目前为止惟一一个以 MST 为根本构图策略的向量检索算法。相似 SPTAG，HCNNG 的构建过程基于分治策略，在搜寻时通过 KD 树获取入口点。

原文：https://www.sciencedirect.com…

中文介绍：https://whenever5225.github.i…

近邻图算法“原子”级剖析
咱们发现所有的基于近邻图的 ANNS 算法都遵循对立的解决流程框架，该流程外面有多个公共模块（如图 2 的 C1->C7）。当一个近邻图算法依照该流程被解构后，咱们能够很容易理解该算法是如何设计组装的，这将给后续近邻图向量检索算法的设计带来很大的便利性。此外，咱们也可固定其它模块，放弃其余模块完全相同，从而更偏心地评估不同算法在某一模块实现上的性能差别。

图 2 近邻图向量检索算法遵循的对立流程框架图

接下来，咱们以 HNSW 和 NSG 为例，阐明如何实现图 2 的流程框架剖析算法。在此之前，咱们要先相熟这两个算法的索引构建和搜寻过程。

首先是 HNSW 合成，HNSW 的构建策略是增量式的。因而，每插入一个数据点都要执行一遍 C1->C3 过程。

HNSW 合成流程：

NSG 合成流程：

因为 HNSW 的 C3 与 NSG 的 C3 是等价的，因而，从下面两个表格可知，HNSW 与 NSG 这两个算法差异并不大。其实，论文波及到的 13 种算法中很多算法之间都是很类似的，详见论文第 4 章。

试验观测和探讨

具体的试验评估请参考论文第 5 章，接下来将概括介绍一下试验的观测后果和探讨：

不同场景下的算法举荐

NSG 和 NSSG 广泛有最小的索引构建工夫和索引尺寸，因而，它们实用于有大量数据频繁更新的场景；如果咱们想要疾速构建一个准确的 KNNG（不仅用于向量检索），KGraph、EFANNA 和 DPG 更适宜；DPG 和 HCNNG 有最小的均匀搜寻门路长度，因而，它们适宜须要 I/O 的场景；对于 LID 值高的较难数据集，HNSW、NSG、HCNNG 比拟适宜；对于 LID 值低的简略数据集，DPG、NSG、HCNNG 和 NSSG 较为适宜；NGT 有更小的候选集尺寸，因而实用于 GPU 减速（思考到 GPU 的内存限度）；当对内存耗费要求较高时，NSG 和 NSSG 适宜，因为它们内存占用更小。

算法设计向导

一个实用的近邻图向量检索算法个别满足以下四个方面：

• 高构建效率
• 高路由效率
• 高搜寻精度
• 低内存负载

针对第一方面，咱们不要在晋升近邻图索引品质（即一个顶点的街坊中实在的最近街坊所占的比例）上破费太多的工夫。因为最好的图品质（可通过图中与距它最近的顶点有边相连的顶点所占比例度量）不肯定实现最佳搜寻性能（联合论文中表 4 和图 7、8）。

针对第二方面，咱们该当管制适当的均匀出度，多样化街坊的散布，缩小获取入口点的破费，优化路由策略，从而缩小收敛到查问点的邻域所需的间隔计算次数。

针对第三方面，咱们该当正当设计街坊的散布，确保连通性，从而晋升对陷入部分最优的 ” 抵抗力 ”。

针对第四方面，咱们该当优化街坊抉择策略和路由策略，从而减小出度和候选集尺寸。

优化算法示例

基于下面的向导，咱们组装了一个新的近邻图算法（图 3 中的 OA），该算法在图 2 中的 7 个组件中每个组件选中现存算法的一个具体实现，即 C1 采纳 KGraph 算法的实现；C2 采纳 NSSG 算法的实现；C3 采纳 NSG 算法的实现；C4 采纳 DPG 算法的实现；C5 采纳 NSSG 算法的实现；C6 采纳 DPG 算法的实现；C7 采纳 HCNNG 和 NSW 算法的实现。

OA 算法实现了以后最优的综合性能，详见论文原文。因而，咱们甚至不必优化以后算法，仅仅把现存算法的不同局部组装起来就能够造成一个新算法。

图 3 OA 算法与以后最优的近邻图算法的搜寻性能比照

趋势与挑战

基于 RNG 的选边策略设计在以后近邻图向量检索算法的效率晋升中起到了关键作用。在论文的评估中，惟一一个基于 MST 的算法 HCNNG 也体现进去很好的综合性能。

在上述纯近邻图算法根底上，后续倒退有三个次要方向：

• 硬件优化；
• 机器学习优化；
• 更高级的查问需要，比方结构化和非结构化混合查问。

咱们将来面对这三个挑战：

• 数据编码技术与图索引如何有机联合以解决近邻图向量检索算法高内存耗费问题；
• 硬件加速近邻图索引构建缩小近邻图索引构建工夫；
• 依据不同场景的特色自适应抉择最优的近邻图算法。

参考资料

https://blog.csdn.net/wheneve…

对于作者：

王梦召，杭州电子科技大学计算机专业硕士。次要关注基于近邻图的向量相似性检索、多模态检索等钻研内容，并在相干方向申请发明专利三项，在数据库顶会 VLDB 和 SCI 一区 top 期刊 KBS 等发表论文两篇。

日常喜好弹吉他、打乒乓球、跑步、看书，他的集体网站是 http://mzwang.top，Github 主页是 http://github.com/whenever5225

Arch Meetup 深圳站开始报名啦，点击查看流动议程！

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

Zilliz 以从新定义数据迷信为愿景，致力于打造一家寰球当先的开源技术创新公司，并通过开源和云原生解决方案为企业解锁非结构化数据的暗藏价值。

Zilliz 构建了 Milvus 向量数据库，以放慢下一代数据平台的倒退。Milvus 数据库是 LF AI & Data 基金会的毕业我的项目，可能治理大量非结构化数据集，在新药发现、举荐零碎、聊天机器人等方面具备宽泛的利用。