Andrei Vasnetsov

返回 Qdrant 内部原理

·

2019 年 11 月 24 日

如果你需要查找向量空间中的一些相似对象，例如通过嵌入或匹配的神经网络提供的数据，你可以从多种库中选择：Annoy、FAISS 或 NMSLib。所有这些库都能在几乎任何空间内提供快速的近似近邻搜索。

但如果你需要在搜索中引入一些约束怎么办？例如，你只想搜索某个类别中的产品，或者选择特定品牌的客户中最相似的。我没有找到任何简单的解决方案。有一些讨论，比如此讨论，但它们只建议迭代顶部搜索结果，然后在搜索后依次应用条件。

让我们看看是否可以修改任何 ANN 算法，使其能够在搜索过程中应用约束。

Annoy 基于随机投影构建树索引。树索引意味着我们将遇到与关系数据库中出现的相同问题：如果字段索引是独立构建的，那么一次只能使用其中一个。由于之前没有人解决过这个问题，似乎没有简单的方法。

还有另一种算法，在基准测试中表现出色。它被称为 HNSW，代表分层可导航小世界（Hierarchical Navigable Small World）。

原始论文写得很好，非常容易阅读，所以我在这里只介绍主要思想。我们需要在所有索引点之间构建一个导航图，以便在该图上进行贪婪搜索能够找到最近的点。这个图是通过顺序添加点构建的，这些点通过固定数量的边连接到之前添加的点。在生成的图中，每个点的边数不超过给定的阈值 $m$，并且总是包含考虑到的最近点。

我们如何修改它？

如果我们简单地将过滤条件应用于该图的节点，并在贪婪搜索中只使用满足这些条件的节点，会怎样？事实证明，即使是这种简单的修改，算法也能涵盖一些用例。

其中一个用例是，如果你的条件与向量语义不相关。例如，你使用向量搜索来查找服装名称，并想过滤掉某些尺寸。在这种情况下，节点将均匀地从整个聚类结构中过滤掉。因此，在渗流理论中获得的理论结论变得适用。

渗流与图（也称为网络）的鲁棒性有关。给定一个包含 $n$ 个节点、平均度为 $\langle k\rangle$ 的随机图。接下来，我们随机删除 $1-p$ 部分的节点，只留下 $p$ 部分。存在一个临界渗流阈值 $ pc = \frac{1}{\langle k\rangle} $，低于此阈值时网络会碎片化，而高于 $pc$ 时存在一个巨大的连通分量。

这个说法也得到了实验的证实。

连接性与边数的关系

让我们考虑一下我们可能想要在搜索中应用的其他过滤条件

分类过滤

• 仅选择特定类别中的点
  • 选择属于特定类别子集的点
  • 选择具有特定标签集的点
  • 数值范围
• 在某个地理区域内选择
• 在第一种情况下，我们可以通过使用相同的图构建算法在每个类别内部单独创建附加边，然后将它们合并到原始图中，从而保证 HNSW 图是连通的。在这种情况下，无论类别的数量如何，总边数最多不会增加两倍。

第二种情况稍微困难一些。如果两个类别位于不同的聚类中，它们之间的连接可能会丢失。

这里的想法是构建相同的导航图，但不是在节点之间，而是在类别之间。两个类别之间的距离可以定义为类别入口点之间的距离（或为了精确，定义为随机样本之间的平均距离）。现在我们可以通过排除的类别数量而不是节点来估计预期的图连通性。这仍然不能保证两个随机类别是连通的，但允许我们在连通性阈值通过后切换到对每个类别进行多次搜索。在某些情况下，如果利用并行处理，多次搜索甚至可能更快。

连接性与搜索中包含的随机类别的关系

如果至少一个子集很小：对包含最小子集的标签执行搜索，然后依次过滤点。

• 如果大子集产生大的交集：执行带有约束的常规搜索，期望交集大小符合连通性阈值。
• 如果大子集产生小的交集：对交集执行线性搜索，期望它足够小，以便在规定的时间内完成。
• 数值范围的情况可以简化为前一种情况，如果我们将数值范围分成包含相等数量点的桶。接下来，我们还将相邻的桶连接起来以实现图连通性。我们仍然需要过滤掉一些位于边界桶中但不符合实际约束的结果，但它们的数量可以通过桶的大小来调节。

地理位置的情况与数值情况非常相似。通常的地理搜索涉及geohash，它将任何地理点匹配到固定长度的标识符。

我们可以使用这些标识符作为类别，并额外在相邻的 geohash 之间建立连接。这将确保任何选定的地理区域也将包含连通的 HNSW 图。

结论

有可能改进 HNSW 算法，使其在第一搜索阶段支持过滤点。过滤可以基于所属类别进行，这又可以推广到数值范围和地理位置等流行情况。

实验是通过修改该算法的Python 实现进行的，但实际生产系统需要更快的版本，例如 NMSLib。

此页面对您有用吗？