Online Approximate Nearest Neighbor Search

September 23, 2023

在线（流式）近似近邻检索

现有的近似近邻检索算法大多是针对静态数据集的，即数据集是固定的，不会再有新的数据加入，不能反映许多关键现实场景所需的语料库的实时变化(例如文档、电子邮件或新闻索引中的句子索引)。在实际应用中，新的数据不断加入，旧的数据不断被删除。为了克服这个缺点，当前将更新展示到此类索引的行业实践是定期重新构建这些索引，这可能带来非常昂贵的计算代价。

基于此，目前可行的方案就是构建在线近似近邻检索算法，即可以在数据集不断变化的情况下，实时更新索引，而不需要重新构建索引。比较具有代表性的算法是FreshDiskANN，在了解FreshDiskANN之前，需要先了解DiskANN算法。

DiskANN

DiskANN是一种基于磁盘的近似最近邻检索算法，它可以在磁盘上存储索引，从而允许索引的大小超过内存容量。 DiskANN的主要思想是将索引分为多个块，每个块都可以完全加载到内存中。在查询时，只有一个块被加载到内存中，然后在该块上执行查询。如果查询失败，则加载下一个块并继续查询。这种方法的优点是，它可以在磁盘上存储大型索引，而不会对内存造成任何压力。缺点是，由于每个块都是独立的，因此无法利用块之间的信息来提高查询性能。在本文中，我们不详细讨论内存+硬盘的索引过程，而仅仅只是考虑纯内存下的DiskANN算法，并进一步了解的FreshDiskANN算法。

Vamana

DiskANN采用的核心图结构是Vamana，与NSG类似，但主要区别在于裁边策略。

对于NSG：对于目标点邻居的选择尽可能多样化，如果新邻居相比目标点，更靠近目标点的某个邻居，我们可以不必将这个点加入邻居点集中。也就是说，对于目标点的每个邻居节点，周围方圆 dist（目标点，邻居点）范围内不能有其他邻居点。

尽管这种裁边策略有效的降低了内存的占用，但也相对激进。这样可能存在的问题是，如果目标点的邻居节点数量较少，那么可能会导致目标点的邻居节点不够多样化，从而影响查询性能。因此，Vamana相比于的裁边策略其实就是通过参数 alpha 自由控制裁边的尺度。具体作用原理是给裁边条件中的 dist（某个邻居点，候选点）乘上一个不小于 1 的参数 alpha，当 dist（目标点，某个候选点）大于这个被放大了的参考距离后才选择裁边，增加了目标点的邻居点之间的互斥容忍度。

Vamana的建索引流程：

开始时，创建一张随机图；
确定起点，类似于NSG的导航点选择。首先，计算全局质心，然后从全局质心找到距离最近的点作为导航点。与NSG不同的是，NSG的输入已经是一张近邻图，因此可以直接在初始近邻图上搜索最近的质心点。然而，Vamana的初始化是一张随机近邻图，因此不能在随机图上直接进行近似搜索，需要进行全局比对以找到导航点。这个导航点将用作后续迭代的起始点，旨在尽量减少平均搜索半径；
对于基于初始化的随机近邻图和步骤2中确定的搜索起点，对每个点执行最近邻搜索（ANN），将搜索路径上的所有点作为候选邻居集，同时执行alpha=1的裁边策略。与NSG类似，选择从导航点出发的搜索路径上的点作为候选邻居集会增加一些长边，有效减少搜索半径。
调整alpha值（通常建议为1.2），然后重复步骤3。由于第3步是基于随机近邻图进行的，第一次迭代后图的质量可能较低，因此需要进行额外迭代以提高图的质量，这对于提高召回率非常重要。

FreshDiskANN

相比于DiskANN，FreshDiskANN的贡献有：

讨论了为什么传统的图结构（HNSW，NSG）加入或者删除结点之后，图索引的质量会下降
提出了FreshVamana，FreshVamana是第一个支持插入和删除的图索引，并且FreshVamana具有良好的稳定性
为了实现适配大规模的数据集，将大部分图索引存储在SSD中，将最近更新的结点存储在内存中。为了支持这一点，设计了两步流式合并算法。（这块在纯内存的算法中我们暂时不考虑）
通过FreshDiskANN，将SSD中的长期驻留索引和短期内存索引聚合在一起

FreshVamana

FreshVamana是FreshDiskANN的核心图结构，它是一种基于Vamana的图结构，支持插入和删除操作。FreshVamana的主要思想是，当插入或删除结点时，只更新受影响的结点，而不是重新构建整个图结构。

Algorithm 1: GreedySearch(𝑠, x𝑞, 𝑘, 𝐿)

输入：一个图𝐺，一个起始节点𝑠，一个查询点x𝑞，以及两个参数：结果大小𝑘和搜索列表大小𝐿（𝐿必须大于或等于𝑘）。
返回：返回一个包含最接近的𝑘个节点的结果集合𝐿以及已访问节点集合𝑉。
开始：初始化两个集合：结果集合𝐿（初始包含起始节点𝑠）和已访问节点集合𝑉（初始为空集）。
搜索列表𝐿减去已访问节点集合𝑉不为空则进入循环，在循环的每一步中，算法选择搜索列表𝐿中距离查询点x𝑞最近的节点𝑝∗（即具有最小的||x𝑝 - x𝑞||距离）。将节点𝑝∗添加到已访问节点集合𝑉中，并更新搜索列表𝐿以包含节点𝑝∗的出边𝑁out(𝑝∗)中的所有节点。如果搜索列表𝐿的大小超过了参数𝐿（即𝐿 < |𝐿|），则对𝐿进行更新，以保留距离查询点x𝑞最近的𝐿个节点。

Algorithm 2: Insert(x𝑝, 𝑠, 𝐿, 𝛼, 𝑅)

输入：一个图𝐺(𝑃, 𝐸)，一个起始节点𝑠，一个新点x𝑝，一个距离阈值𝛼（必须大于1），一个出度限制𝑅，以及一个搜索列表大小𝐿。
输出：更新后的图𝐺′(𝑃′, 𝐸′)，其中𝑃′包括原始节点𝑃和新插入的点𝑝，𝐸′包括原始边𝐸和新的边。
开始：初始化两个集合：已扩展节点集合V（初始为空集）和候选列表L（初始为空集）。
首先使用GreedySearch函数执行贪婪搜索，以找到新点x𝑝的𝐿个最近邻居节点。GreedySearch函数返回两个列表[L, V]，其中L是包含最近邻居结点，V是已访问的结点。
使用RobustPrune函数对新点x𝑝的出邻居节点进行剪枝（prune），以确保出度不超过R
对于新点x𝑝的每个出邻居节点𝑗，检查𝑁out(𝑗) ∪ {𝑝}是否超过了出度限制𝑅。如果超过了𝑅，则再次使用RobustPrune函数对节点𝑗的出邻居进行剪枝，以确保出度不超过𝑅。
如果𝑁out(𝑗) ∪ {𝑝}没有超过𝑅，那么就将新点x𝑝添加到节点𝑗的出邻居中，更新𝑁out(𝑗)。

Algorithm 3: RobustPrune(𝑝, V, 𝛼, 𝑅)

输入：图𝐺，节点𝑝，候选集合V，距离阈值𝛼（必须大于或等于1），和度数限制𝑅。
将节点𝑝从已访问结点（候选集合）V中移除，并将节点𝑝的出邻居集合𝑁out(𝑝)初始化为空。
进入一个循环，条件是候选集合V不为空。循环的目标是选择距离节点𝑝最近的节点𝑝∗，并将其添加到节点𝑝的出邻居𝑁out(𝑝)中。这是一个迭代的过程，直到满足度数限制𝑅为止。
对于候选集合V中的每个节点𝑝′，如果满足条件 𝛼·𝑑(𝑝∗, 𝑝′) ≤ 𝑑(𝑝, 𝑝′)，则将节点𝑝′从候选集合V中移除。

Algorithm 4: Delete(𝐿𝐷, 𝑅, 𝛼)

输入：图𝐺(𝑃, 𝐸)，其中𝑃是节点集合，𝐸是边集合，以及要删除的点的集合𝐿𝐷。
输出：一个不包含LD的新图
对于𝑃中的每个节点𝑝，如果𝑝的出邻居中存在属于𝐿𝐷的节点（即𝑁out(𝑝) ∩ 𝐿𝐷 ≠ ∅），则执行以下操作：
初始化一个集合D，其中包含𝑝的出邻居中属于𝐿𝐷的节点。
初始化一个候选列表C，其中包含𝑝的出邻居中不属于D的节点。
对于D中的每个节点𝑣，将𝑣的出邻居添加到候选列表C中。
从候选列表C中移除集合D中的节点，以确保不包含被删除的节点。
最后，使用RobustPrune函数对节点𝑝的出邻居进行剪枝，以确保出度不超过指定的度数限制𝑅。

Incremental Proximity Graph Maintenance (IPGM)

这是一种增量近似图维持算法，其底层使用的数据结构主要是德劳内图，与FreshVamana算法相似的是，对于插入和删除操作，IPGM也是只更新受影响的结点，而不是重新构建整个图结构。

这里主要考虑删除带来的图索引质量下降的情况。对于删除，我们有几种可以考虑的模式，包括：

直接删除，即删除一个点，并把它连接的边都删除（显然这种情况可能带来图质量的显著下降）
将节点记录到一个删除列表中，在搜索的过程中不将其加入到候选集合中。（这可能会带来内存占用问题，同时也会使得搜索路径更长，更难达到目标点）
局部重构，删除这个点，并且将原来指向这个点的节点与这个点的出边相连（简单来说，就是原先通过这个点能到达的路径直接直达，但这样存在一定的局部性，效果并不一定好）
全局重构。删除这个点，并对于所有指向该点的节点，进行重新插入操作。显然这样主要带来的是删除效率的下降，但会带来图质量的提升。

因此，考虑到上述四种情况，基于图的流式插入删除应该是一个trade-off的问题，即需要考虑删除效率和图质量的平衡。