矢量相似性搜索改变了搜索领域的游戏规则。它使我们能够有效地搜索范围广泛的媒体，从 GIF 到文章——对于超过 10 亿大小的数据集，在亚秒级时间尺度上具有令人难以置信的准确度。高效搜索的关键组成部分之一是灵活性。为此，我们有广泛的搜索索引可供我们使用——在相似性搜索中没有“一刀切”。然而，这种巨大的灵活性产生了一个问题——我们如何知道哪种尺寸适合我们的用例？本文将探讨一些最重要的指标——Flat、LSH、HNSW 和 IVF 的优缺点。我们将学习如何决定使用哪个以及每个索引中参数的影响。我们将使用优秀的 Facebook AI Similarity Search (Faiss) 库来测试每个索引。在讨论可用的不同索引之前，让我们先看看为什么我们关心相似性搜索——以及我们如何使用索引进行有效的相似性搜索。让我们从与本文相关性的最基本问题开始——我们为什么关心相似性搜索？相似性搜索可用于快速比较数据。给定一个查询（可以是任何格式——文本、音频、视频、GIF——你能说出它），我们可以使用相似性搜索来返回相关结果。
这是跨行业的大量公司和应用程序的关键。它用于识别基因组数据库中的相似基因、数据集的重复数据删除或每天搜索数十亿个结果以搜索查询。搜索似乎是一个简单的过程——我们将一个项目与另一个项目进行比较。但是，当我们有数百万（甚至数十亿）个“其他”项目可供比较时——它开始变得棘手。为了使搜索有用，它需要准确和快速。我们感兴趣的正是这种更高效的搜索。在向量相似性搜索中，我们使用索引来存储我们打算搜索的数据的向量表示。通过统计方法或机器学习——我们可以构建向量来编码有关原始数据的有用、有意义的信息。我们将这些“有意义”的向量存储在索引中，以用于智能相似性搜索。有很多可用的索引解决方案；特别是其中一种称为 Faiss（Facebook AI 相似性搜索）。我们将向量存储在 Faiss 中，并使用“查询”向量查询我们的新 Faiss 索引。将此查询向量与其他索引向量进行比较以找到最近的匹配项——通常使用欧几里得 (L2) 或内积 (IP) 指标。
因此，通过对相似性搜索的原因和方式的介绍。但是 Faiss 和选择正确的索引有什么关系呢？ Faiss 带有许多不同的索引类型——其中许多可以混合和匹配以生成多层索引。我们将关注一些优先考虑搜索速度、质量或索引内存的索引。现在，我们使用这些索引中的哪一个在很大程度上取决于我们的用例。我们必须考虑数据集大小、搜索频率或搜索质量与搜索速度等因素。扁平索引是“扁平的”，因为我们不会修改我们提供给它们的向量。因为我们的向量没有近似或聚类——这些索引产生最准确的结果。我们拥有完美的搜索质量，但这是以大量搜索时间为代价的。对于平面索引，我们引入了查询向量 xq 并将其与索引中的每个其他全尺寸向量进行比较——计算到每个向量的距离。
在计算所有这些距离之后，我们将返回最近的 k 个作为我们最近的匹配项。 k 最近邻 (kNN) 搜索。那么我们什么时候应该使用平面索引呢？好吧，当搜索质量无疑是高优先级时 - 搜索速度就不那么重要了。对于较小的数据集，搜索速度可能是一个无关紧要的因素——尤其是在使用更强大的硬件时。上图展示了 M1 芯片上的 Faiss CPU 速度。 Faiss 经过优化，与 Linux 上支持 CUDA 的 GPU 搭配使用时，可以以显着更高的速度在 GPU 上运行，从而显着缩短搜索时间。要初始化平面索引，我们需要我们的数据 Faiss 和两个平面索引之一 — IndexFlatL2（如果使用 Euclidean/L2 距离）或 IndexFlatIP（如果使用内积距离）。首先，我们需要数据。我们将使用 Sift1M 数据集，我们可以将其下载并加载到笔记本中： 现在我们可以使用我们的两个平面索引之一来索引我们的新数据。我们看到 IndexFlatIP 稍微快一点，所以让我们使用它。
d = 128 # Sift1M 的维度 datak = 10 # 要返回的最近邻数index = faiss .IndexFlatIP(d)index .add(data)D, I = index .search(xq, k) 而对于平面索引，仅此而已我们需要做 - 没有训练（因为在没有转换或聚类的情况下存储向量时，我们没有要优化的参数）。扁平索引非常准确，但速度非常慢。在相似性搜索中，搜索速度和搜索质量（准确性）之间总是存在权衡。我们必须做的是确定我们的用例最佳位置在哪里。有了平面索引，我们就在这里：这里我们有完全未优化的搜索速度，这将适合许多较小的索引用例——或者搜索时间无关紧要的场景。但是，其他用例需要更好的平衡速度和质量。减少向量大小——通过降维或减少表示向量值的位数。缩小搜索范围——我们可以通过基于某些属性、相似性或距离将向量聚类或组织成树结构来实现这一点——并将我们的搜索限制在最近的集群或过滤最相似的分支。
使用这两种方法中的任何一种意味着我们不再执行详尽的最近邻搜索，而是执行近似最近邻 (ANN) 搜索——因为我们不再搜索整个全分辨率数据集。因此，我们产生的是一个更平衡的组合，优先考虑搜索速度和搜索时间：局部敏感哈希 (LSH) 的工作原理是通过一个哈希函数处理每个向量，从而将每个向量分组到桶中，从而最大化哈希冲突——而不是最小化作为通常使用散列函数。那是什么意思？假设我们有一个 Python 字典。当我们在字典中创建新的键值对时，我们使用散列函数对键进行散列。键的哈希值决定了我们存储其各自值的“存储桶”：Python 字典是一个使用典型哈希函数的哈希表示例，该函数可以最小化哈希冲突，哈希冲突是两个不同的对象（键）产生相同的哈希值。在我们的字典中，我们希望避免这些冲突，因为这意味着我们会将多个对象映射到一个键——但对于 LSH，我们希望最大化散列冲突。为什么我们要最大化碰撞？好吧，对于搜索，我们使用 LSH 将相似的对象组合在一起。当我们引入一个新的查询对象（或向量）时，我们的 LSH 算法可用于找到最接近的匹配组：
在 Faiss 中实现我们的 LSH 索引很容易。我们使用向量维度 d 和 nbits 参数初始化一个 IndexLSH 对象——并像这样添加我们的向量：我们的 nbits 参数指的是散列向量的“分辨率”。更高的值意味着更高的准确性，但代价是更多的内存和更慢的搜索速度。我们的基准 IndexFlatIP 指数是我们的 100% 召回性能，使用 IndexLSH 我们可以使用非常高的 nbits 值实现 90%。这是一个强有力的结果——如果我们得到改进的搜索时间，那么 90% 的性能肯定是对性能的合理牺牲。然而，当使用较大的 d 值时，LSH 对维数灾难高度敏感，我们还需要增加 nbits 以保持搜索质量。因此，随着原始向量维数 d 的增加，我们存储的向量变得越来越大。这很快会导致过多的搜索时间：所以如果我们有很大的向量维度（128 已经太大了），IndexLSH 不适合。相反，它最适合低维向量和小索引。
如果我们发现自己的 d 值很大或索引很大——我们会完全避免 LSH，而是专注于我们的下一个索引 HNSW。分层导航小世界 (HNSW) 图是搜索领域的另一个最新发展。基于 HNSW 的 ANNS 始终名列前茅，是性能最高的指标 [1]。 HNSW 是对可导航小世界 (NSW) 图的进一步改编——其中 NSW 图是一种图结构，其中包含通过边连接到最近邻居的顶点。 “NSW”部分是由于这些图中的顶点到图中所有其他顶点的平均路径长度都很短——尽管它们没有直接连接。以 Facebook 为例——在 2016 年，我们可以将每个用户（一个顶点）连接到他们的 Facebook 朋友（他们最近的邻居）。尽管有 1.59B 的活跃用户，但从一个用户到另一个用户遍历图表所需的平均步数（或跳数）仅为 3.57 [2]。 Facebook 只是庞大网络中高连通性的一个例子——也称为新南威尔士州图。在高层次上，HNSW 图是通过将 NSW 图分解成多个层来构建的。随着每个增量层消除顶点之间的中间连接。
对于具有更高维度的更大数据集——HNSW 图是我们可以使用的一些性能最佳的索引。我们将单独使用 HNSW 索引进行介绍，但通过对其他量化步骤进行分层，我们可以进一步缩短搜索时间。要在 Faiss 中构建和搜索平面 HNSW 索引，我们只需要 IndexHNSWFlat：但是，只有 M 和 efSearch 会增加搜索时间——efConstruction 只会增加索引构建时间（意味着更慢的 index.add）。 HNSW 以非常快的搜索速度为我们提供了出色的搜索质量——但总有一个问题——HNSW 索引占用大量内存。对 Sift1M 数据集使用 128 的 M 值需要超过 1.6GB 的内存。但是，我们可以增加其他两个参数 — efSearch 和 efConstruction，而不会影响索引内存占用。因此，在 RAM 不是限制因素的情况下，HNSW 作为一个平衡良好的指数非常棒，我们可以通过增加我们的三个参数来推动更多地关注质量。这就是 Faiss 中的 HNSW — 一个令人难以置信的强大和高效的索引。现在让我们进入我们的最终指标——试管婴儿。
倒排文件索引 (IVF) 索引包括通过聚类减少搜索范围。这是一个非常受欢迎的索引，因为它易于使用，具有高搜索质量和合理的搜索速度。它适用于 Voronoi 图的概念——也称为 Dirichlet 镶嵌（一个更酷的名字）。要理解 Voronoi 图，我们需要想象我们放置在 2D 空间中的高维向量。然后我们在我们的 2D 空间中放置一些额外的点，它们将成为我们的“集群”（在我们的例子中是 Voronoi 单元）质心。然后我们从每个质心向外延伸相等的半径。在某些时候，每个单元圆的圆周将与另一个相撞——创建我们的单元边缘：现在，每个数据点都将包含在一个单元中——并分配给相应的质心。就像我们的其他索引一样，我们引入了一个查询向量 xq——这个查询向量必须落在我们的一个单元格内，此时我们将搜索范围限制在那个单元格内。但是如果我们的查询向量落在一个单元格的边缘附近，就会出现问题——它最接近的其他数据点很有可能包含在相邻的单元格中。我们称之为边缘问题：
现在，我们可以做些什么来缓解这个问题并提高搜索质量，那就是增加一个称为 nprobe 值的索引参数。使用 nprobe 我们可以设置要搜索的单元格数量。更高的 nlist 意味着我们必须将我们的向量与更多的质心向量进行比较——但是在选择最近的质心的单元格进行搜索之后，每个单元格内的向量将更少。因此，增加 nlist 以优先考虑搜索速度。至于nprobe，我们发现相反。增加 nprobe 会增加搜索范围——因此优先考虑搜索质量。在内存方面，IndexIVFFlat 相当高效——修改 nprobe 不会影响这一点。 nlist 对内存使用的影响也很小——更高的 nlist 意味着稍微大一点的内存需求。我们在本文中介绍了很多内容，所以让我们快速总结一下每个索引的内存、速度和搜索质量性能。所以我们有四个索引，各有优缺点——取决于用例。希望通过这篇文章，您现在可以更好地决定哪些索引最适合您自己的用例。除了这些指标之外，还可以通过添加其他量化或压缩步骤来进一步提高内存使用率和搜索速度——但这是另一篇文章。
[2] S Edunov, et al., 三度半分离 (2016), Facebook Research