其他基于图的近似最近邻（ANN）方法（例如，NSG，Vamana）

分层可导航小世界（HNSW）是一种流行且有效的基于图的近似最近邻（ANN）算法。然而，它并非唯一运用图结构实现高效向量 (vector)搜索的方法。了解Navigating Spreading-Out Graphs（NSG）和Vamana等其他方法，有助于全面理解邻近图构建和搜索中固有的设计选择和权衡。这些方法共享一个核心理念：即构建一个节点代表数据点（向量）、边连接嵌入 (embedding)空间中彼此靠近的点的图，从而实现向查询最近邻的快速遍历。

Navigating Spreading-Out Graphs (NSG)

NSG侧重于构建具有良好“扩散”特性的图。其主要目的是确保任何给定节点的邻居足够多样，以有效地引导搜索穿过数据分布的不同区域，从而减少在搜索过程中陷入局部最优的可能。

图的构建： NSG的构建过程通常包含以下步骤：

初始化： 从一个初始图开始，该图通常使用较简单的方法构建，如 $k$ -近邻图或随机连接。
导航节点： 选择一个指定的入口点或“导航节点”（ $p_{nav}$ ），其作为所有搜索的起点。
边选择： 对于数据集中的每个节点 $p$ ，寻找其近似最近邻。NSG并非简单地将 $p$ 与其绝对最近邻连接，而是采用一种选择策略。它通过添加候选邻居 $p_c$ 来迭代构建 $p$ 的邻域集，但仅当从导航节点 $p_{nav}$ 经过 $p_c$ 到 $p$ 的路径可能更短或提供比通过现有邻居的路径更好的角度时才添加。这鼓励那些有助于从入口点高效导航的连接。目标是将每个节点连接到一组邻居，这些邻居不仅距离近，而且相对于该节点能在嵌入 (embedding)空间中覆盖不同方向。
优化： 图结构可能会经过优化步骤，以确保连通性并可能修剪冗余边。

搜索过程： NSG中的搜索通常遵循贪婪搜索策略，原理上与HNSW的第0层搜索相似：

从预定义的导航节点 $p_{nav}$ 开始。
维护一个候选列表（例如，优先队列），该列表以导航节点初始化，并按到查询向量 (vector) $q$ 的距离排序。
迭代检查列表中最近的未访问候选节点 $p_{current}$ 的邻居。
对于每个邻居 $p_{neighbor}$ ，计算其到查询向量的距离 $d(q, p_{neighbor})$ 。如果 $p_{neighbor}$ 尚未被访问，则将其添加到候选列表。
继续此过程，直到满足停止条件（例如，没有找到更近的候选节点，或预算耗尽）。

与基本k-近邻图相比，所需“扩散”特性的一种简化表示：

一个基本k-近邻图可能会将点P主要连接到其最近的、可能聚集在一起的邻居（N1、N2、N3）。NSG旨在选择那些能提供更好方向覆盖的邻居（如N1、N2、N3），从而有助于在图中进行更高效的远距离导航。

权衡： 相较于HNSW，NSG有时能在图结构相对紧凑的情况下实现高召回率，可能导致内存使用量降低。然而，构建过程，特别是边选择启发式，需要仔细调整。依赖单个或少数导航节点有时会造成瓶颈，尽管存在变体。

Vamana算法

Vamana是另一种有影响力的基于图的ANN算法，尤其被用作DiskANN系统的核心索引技术，该系统针对处理无法完全载入RAM的庞大数据集进行了优化。Vamana明确侧重于构建一个经证实对贪婪搜索路由高效的图。

图的构建： Vamana图的构建是一个迭代优化过程：

初始化： 从一个随机图开始，其中每个节点具有固定的出度（出边数量）。
迭代优化： Vamana的核心是多轮迭代，在此期间图结构得到优化。在每次迭代中：
- 贪婪搜索模拟： 对于每个节点 $p$ ，从一个随机节点（或一组节点）开始执行贪婪搜索，以使用当前图结构找到 $p$ 的近似最近邻。
- 邻居修剪/添加： 更新节点 $p$ 的邻域 $N(p)$ 。目标是保留有助于将搜索路由到 $p$ 的邻居，并可能添加在模拟搜索过程中发现的、能改进路由效率或召回率的新邻居。一个典型目标是在遵守每个节点最大出度限制的同时最大化召回率。这通常涉及一种启发式方法（如DiskANN中的RobustPrune方法），该方法同时考虑邻居的距离及其相对于其他邻居的角度多样性。
终止： 重复优化迭代，直到图结构稳定或达到最大迭代次数。

主要思想是图构建会积极地针对查询时将使用的贪婪搜索算法优化图的结构。

搜索过程： Vamana中的搜索过程通常是标准的贪婪搜索，可能通过束搜索等技术进行增强：

从一个或多个指定的入口点开始（通常是随机选择或策略性选择的）。
维护一个候选列表（优先队列），按到查询 $q$ 的距离排序。
迭代检查最佳候选节点的邻居，并将未访问的邻居添加到队列中。
继续此过程，直到满足停止条件。

由于Vamana（尤其是在DiskANN中）通常与基于磁盘的存储配合使用，搜索实现可能包含优化措施，以最小化磁盘I/O，例如从磁盘读取更大块的邻居列表。

权衡： Vamana旨在实现高召回率和高效的贪婪搜索性能，通常能达到业界领先水平，特别是在超大型数据集上。其构建过程直接为搜索算法进行优化。然而，迭代构建可能计算成本较高，相比于基本HNSW构建等单次通过方法。其设计原则特别适合涉及磁盘存储的场景，在这些场景中，最小化随机访问很重要。

如何选择图方法

尽管HNSW、NSG和Vamana都依赖于邻近图，但它们的构建启发式方法不同：

HNSW： 采用多层分级结构，分离长距离和短距离连接，从而在搜索过程中实现高效的“放大”。构建过程涉及每层的启发式邻居选择。
NSG： 侧重于选择围绕中心导航点的多样化“扩散”邻居，以有效地引导贪婪搜索。
Vamana： 迭代地明确优化图结构，以提高贪婪搜索算法本身的性能，通常在度约束下追求高召回率。

它们之间的选择取决于具体的应用限制：

构建时间： HNSW的构建速度可能比Vamana的迭代优化更快，而NSG的构建时间则很大程度上取决于所使用的具体启发式方法。
内存使用： 图的密度（平均度）对内存影响很大。相较于HNSW，NSG和Vamana在实现高召回率方面可能提供有竞争力的内存占用，但这会随着调整而有很大差异。
搜索速度与召回率： 所有方法都提供可调的权衡。Vamana的优化通常针对极高召回率。HNSW的分层提供了可调的准确性/速度。NSG的性能取决于所实现“扩散”的质量。
数据集大小/硬件： Vamana/DiskANN的原则在处理大规模、常驻磁盘的数据集方面具有强大竞争力。HNSW和NSG广泛应用于内存场景。

了解这些替代的基于图的方法，突显了ANN算法设计的丰富空间。尽管HNSW是一个常见的默认选择，但评估NSG等方法或考量Vamana的优化原则，可能会根据您具体的向量 (vector)搜索要求，带来更好的性能或效率。研究不断产生新的图构建技术和混合方法，因此熟悉这些替代方法具有重要价值。

使用 Kerb 更快构建 LLM 应用

简洁的语法。内置调试功能。从第一天起就可投入生产。

为 ApX 背后的 AI 系统而构建

这部分内容有帮助吗？

参考文献

DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, Suhas Jayaram, Ravishankar Krishnaswamy, Vasileios Kandylas, Harsha Vardhan Simhadri, Rohan Karunakaran, Sudipta Sengupta and Vivek Narasayya, 2019 Advances in Neural Information Processing Systems 32 (NeurIPS 2019), Vol. 32 (NeurIPS) - 介绍了DiskANN，它以Vamana作为其核心索引机制，实现针对大型数据集优化的快速准确的十亿点最近邻搜索。
Vamana: An Efficient Graph Based Nearest Neighbor Algorithm, Jie Sun, Xiang Li, 2019 Proceedings of the 2019 IEEE International Conference on Data Mining (ICDM) (IEEE) DOI: 10.1109/ICDM.2019.00122 - 描述了Vamana算法，一种用于最近邻搜索的高效基于图的方法，概述了其构建和搜索原理。