向量索引:向量数据库路线图

时间:2024-10-31 07:11:39

路线图在旅行时很有用,因为它们从现实世界中获取密集的地理信息并将其浓缩成一张易于导航的纸(或智能手机显示屏)。就像旅行者从地图中受益一样,矢量数据库也受益于矢量索引。向量索引是原始向量的压缩形式,允许高效、快速的搜索。与通过原始嵌入处理搜索相比,索引的紧凑性降低了内存需求并增强了可访问性。

索引有多种形式,由不同的算法方法创建。您不需要了解使用大多数 vector 数据库创建索引本身的细节;它们可以通过您选择的简单命令轻松创建。但是,掌握向量索引的基本工作原理及其各种形式有助于了解选择哪一个以及何时选择。本文讨论了向量索引的三个主要类别:

Flat Index

平坦索引(也称为“蛮力”)在所有索引方法中提供最佳精度,但是,它们的速度是出了名的慢。这是因为 flat indices 是向量嵌入的直接表示。与其他索引方法不同,生成flat 索引不使用预先训练的集群或向量嵌入的任何其他修改。对于 flat 索引,搜索是详尽的:它是从 query 向量跨每个向量嵌入执行的,并且计算每对的距离。然后,使用 k 最近邻 (kNN) 搜索返回 k 个嵌入向量:

这种类型的成对距离计算似乎不是很有效,但是,有时需要搜索结果的高准确性,具体取决于您的应用程序。具体而言,以下是 Flat 索引有益的一些情况:

  • Low-Dimensional Data:对于低维向量(通常是几十个维度),flat 索引可以在保持高精度的同时足够快。
  • Small-Scale Databases:当数据库包含相对较少的向量时,flat 索引足以提供快速检索时间。
  • Simple Querying:如果主要使用案例涉及简单的查询,则与其他索引相比,flat 索引可以提供有竞争力的性能,而不会产生复杂性。
  • Benchmarking Comparisons: 在您想要评估其他指数方法的准确性的情况下,使用完全准确的 flat index 可以用作比较的基准。

Graph Index

图索引使用节点和边缘来构建类似网络的结构。节点(或“顶点”)表示向量嵌入,而边表示嵌入之间的关系。最常见的图形索引类型是 Hierarchical Navigable Small Words(HNSW)。

HNSW 是一种“临近图”,其中两个嵌入顶点根据它们的近似度链接起来——通常由欧几里得距离定义。图形中的每个顶点都连接到称为“朋友”的其他顶点,每个顶点都保留一个“朋友列表”。从预定义的 “入口点” 开始,该算法遍历连接的友元顶点,直到找到 query 向量的最近邻居:

每次遍历都通过“friends list”中的 Nearest Neighboring vertices 继续进行,直到找不到更近的顶点 — 达到距离的局部最小值。

入口点通常位于高阶顶点(具有许多连接的顶点)上,以减少通过从低阶顶点开始而提前停止的可能性:

可以指定入口顶点上的度数,并且通常在召回率和搜索速度之间保持平衡。

索引空间不是跨一个层执行此操作(这将花费大量时间和内存),而是被拆分为多层,即 HNSW 中的“H”:

顶层具有最长的距离,但包含最高阶数的顶点。该算法首先遍历较长的距离,直到找到具有高次顶点的局部最小值,然后向下放置一个层,相比前一层有更多 “friend” 顶点可用。此遍历将继续,直到最近邻与查询向量的距离达到局部最小值。

具体而言,以下是 HNSW 索引的优势:

  • High-Dimensional Data:HNSW 专为高维数据而设计,通常为数百或数千个维度。
  • Efficient Nearest Neighbor Search:HNSW 非常适合快速查找与给定查询最相似的节点,例如推荐系统、基于内容的图像检索和自然语言处理任务。
  • Approximate Nearest Neighbor Search:虽然 HNSW 主要用于准确的最近邻搜索,但它也可用于用户寻求最小化搜索计算成本的近似最近邻搜索任务。
  • Large-Scale Databases:HNSW 旨在很好地扩展大型数据集。
  • Real-time and Dynamic Data:HNSW 能够容纳动态变化的数据,例如实时更新
  • Highly-Resourced Environments:HNSW 的性能不仅仅依赖于单台计算机的内存,因此非常适合分布式和并行计算环境。

Inverted Index(and Product Quantization)

倒排索引在搜索引擎中广泛使用,因为它们提供了一种查找文档内容的有效方法。假设您有一个文档集合,例如搜索引擎数据库中的网页。每个文档都包含单词,您希望能够快速找到包含特定单词的所有文档。对于整个文档集合中的每个唯一单词,倒排索引会创建一个文档引用或标识符(例如文档 ID)的列表,该单词会出现在其中:

这是倒排索引的粗略演示。我们可以通过 “Product Quantization” 进一步优化索引。

Product Quantization 分 4 个步骤进行:

  1. 将文本转换成高维向量
  2. 将文本的高维向量拆分为大小相等的子向量
  3. 将每个子向量分配给其最近的质心(由 k-means 聚类定义)
  4. 将每个质心值替换为唯一 ID

一旦量化的子向量可用,它们就可以排列在 Voronoi 单元 中。如下所示,子向量为黄色,Voronoi 单元以白线为界,它们的质心为白色圆圈。查询向量是绿色星号:

所选的 Voronoi 单元格由 query 向量和 probe 参数定义。搜索仅限于 query 向量所在的单元格,以及周围单元格的最近质心。下面,probe 参数获取距离 query 向量最近的 3 个单元格:

这大大减少了内存使用量和搜索时间,并且召回率很高。与 HNSW 一样,它非常适合高维向量以及需要快速最近邻搜索的情况。事实上,IVFPQ 与 HNSW 具有许多相似的优势,从高资源环境到高维向量,再到大规模数据库。突出显示两种索引类型中的细微差别会更有用:

IVFPQ Index is better for:

  • Accuracy:当你需要更高精度的最近邻分数
  • Approximate Search:精确搜索和近似最近邻搜索都会被使用,但是,在需要精确结果的情况下,它特别强大。
  • Memory Efficiency:由于使用了乘积量化,IVFPQ 的内存效率非常高。

HNSW Index is better for:

  • Approximate Search:HNSW 专为高效的近似最近邻计算而设计。如果您的目标是快速找到一个相对较好的解决方案,即使它不是确切的最近邻,请选择 HNSW。
  • Simplicity:与 IVFPQ 相比,HNSW 的实现和配置相对简单。由于不涉及 PQ,因此构造索引的步骤较少。
  • Scalability:轻松处理大型数据集,并适应实时和动态数据。
  • Storage:HNSW 不需要 PQ,因此需要的存储空间更少。
  • Speed (over accuracy):如果您能接受近似结果,那么 HNSW 的速度优势可能是值得的。

Final Considerations

下表总结了此处描述的三种索引类型中每一种的优点: