通过向量索引加速超大规模数据的相似度搜索
如果没有向量索引，许多现代AI应用将会变得极其缓慢。接下来将探讨索引如何显著加速向量相似度搜索，不同的索引类型，以及如何为您的机器学习应用选择合适的索引。
向量索引如何加速相似度搜索和机器学习？
相似度搜索引擎通过将输入与数据库进行比较来找到与输入最相似的对象。
索引是高效组织数据的过程，它通过显著加快大型数据集上的耗时查询，在使相似度搜索变得实用方面发挥着重要作用。
在对大规模向量数据集建立索引后，查询可以被路由到最有可能包含与输入查询相似向量的集群或数据子集。在实践中，这意味着牺牲一定程度的准确性来加速超大规模向量数据的查询。
这可以类比于字典，其中单词按字母顺序排序。在查找单词时，可以快速导航到仅包含具有相同首字母的单词的部分 - 大大加快了查找输入单词定义的过程。
ANNS
在处理高维数据时，最近邻搜索（NNS, Nearest Neighbor Search）是一个常见且重要的任务。
随着数据规模的增大，精确的最近邻检索通常会变得非常耗时和资源密集。因此，近似最近邻搜索（ANNS, Approximate Nearest Neighbor Search）应运而生。
不同类型的IVF索引及其适用场景
针对高维向量相似度搜索，有许多种索引设计，每种索引在性能、准确性和存储需求方面都有权衡。本文介绍几种常见的IVF索引类型，它们的优势和劣势，以及每种索引类型的性能测试结果。
FLAT索引
- 核心原理：
- 采用暴力搜索（brute-force），对每个查询向量与数据库中所有向量逐一计算距离，保证100%精确度。
- 适用于：当需要100%召回率时搜索相对较小的数据集（百万级）
- 特点：
- 不压缩向量
- 唯一可以保证精确搜索结果的索引
- 采用穷举搜索方法
- 速度最慢
IVF_FLAT索引
IVF_FLAT 是一种基于倒排的索引方法，广泛用于在大规模数据集上实现高效的近似最近邻搜索。它适用于在精度和查询速度之间寻求平衡的场景
-
核心原理：
1. 聚类原理
- 采用 k-means 聚类算法将高维向量空间划分为多个子空间（簇）
- 每个簇包含一组相似的向量
- 每个簇都有一个代表向量（中心点）
- 中心点通常是该簇内所有向量的平均值
2. 倒排索引构建
- 为每个簇建立倒排表索引
- 每个向量被映射到其所属的簇
- 建立向量到其所在簇的映射关系
- 通过倒排索引可以快速定位向量所在的簇
3. 查询处理流程
-
初始定位
- 首先将查询向量分配到距离最近的簇中心
- 快速确定最可能包含相似向量的子空间
-
精确搜索
- 在定位到的簇内执行精确的线性搜索
- 查找与查询向量最相似的向量
-
参数优化
- 使用
nprobe参数控制搜索的簇数量 nprobe越大：- 搜索范围更广
- 结果更精确
- 查询时间更长
nprobe越小：- 搜索范围更小
- 查询速度更快
- 可能损失部分精度
- 使用
-
特点：
- 通过牺牲准确性来提高速度（反之亦然）
- 使用ANN（近似最近邻）搜索
- 将向量数据分为多个集群单元(nlist)
- 可以通过调整nprobe来平衡准确性和速度
- 不压缩向量数据
IVF_SQ8索引
1. 基本概念
- IVF_SQ8 是 IVF_FLAT 的改进版本
- 在 IVF_FLAT 基础上增加了标量量化(Scalar Quantization)
- 通过量化技术显著降低存储和计算资源消耗(降低70%-75%)
2. 核心机制
-
标量量化
- 将每个维度的 4 字节浮点数压缩为 1 字节整数
- 示例：将 [0.0, 1.0] 范围的浮点数映射为 uint8 类型
- 实现存储空间的显著节省
-
向量处理
- 使用整数(如 uint8)表示量化后的向量
- 大幅减少存储空间和计算量
- 保持原始数据的分布特征
-
搜索流程
- 继承 IVF_FLAT 的聚类方法(k-means)
- 将向量空间分为多个簇
- 使用量化后的向量进行存储和搜索
- 查询时先定位簇，再在簇内快速搜索
3. 主要优势
- 存储效率：比 IVF_FLAT 节省70%-75%的资源
- 查询性能：计算量显著降低
- 适用场景：适合大规模数据集的相似度搜索
IVF_PQ索引
倒排文件：
倒排文件是一种高效的索引结构，用于存储和检索向量。在IVF_PQ中，数据集中的每个向量被分配到一个或多个倒排表中，每个表包含了对应向量的标识符。查询时，我们首先在倒排文件中找到候选的向量集合，从而大大减少了搜索空间。倒排文件特别适合于高维空间，因为它允许我们仅搜索与查询向量相似的部分数据，而不是遍历整个数据集。
乘积量化（PQ）：
乘积量化是一种将高维向量压缩为低维表示的技术。它通过将向量划分为多个子空间，并对每个子空间进行独立的量化，生成一个代码本（codebook）。这样，原始的高维向量可以由多个子空间的量化表示组合而成，从而降低存储需求并加速检索。
在IVF_PQ中，乘积量化应用于IVF的聚类过程。每个簇的中心点会被进一步量化，原始的查询向量和数据向量在计算距离时，不是直接与每个簇中心进行计算，而是与每个子空间的量化中心进行计算。这种方法不仅降低了存储开销，还减少了计算距离时的运算量。
核心原理：
- 结合IVF聚类和乘积量化（Product Quantization），将向量分块后分别量化编码，极大压缩存储空间，适合超大规模数据集。
- 特点：
- 结合了IVF和乘积量化(Product Quantization)
- 比IVF_SQ8提供更高的压缩率
- 内存占用非常小
- 搜索速度快
- 准确率会有一定损失
- 适合超大规模数据集
- 参数：
- nlist: 聚类单元数量
- m: 向量被切分的子向量数量
- nbits: 每个子向量的编码位数
HNSW索引
- 核心原理：
- 构建分层小世界图（Hierarchical Navigable Small World），每层为不同粒度的近邻图。查询时自顶向下逐层跳转，底层做局部最优搜索，极大提升高维检索效率。
- 特点：
- 基于图的索引方法
- 搜索速度非常快
- 构建索引时间较长
- 内存占用较大
- 适合需要高速搜索的在线服务
- 参数：
- M: 图中每个节点的最大边数
- efConstruction: 构建索引时的搜索宽度
- ef: 搜索时的候选集大小
DISKANN索引
- 核心原理：
- 基于磁盘的高性能近邻图索引，将轻量级索引结构放在内存，原始数据和图结构存储在磁盘，兼顾高召回率、低延迟和极低内存消耗。
- 特点：
- 基于磁盘的图索引
- 适合超大规模数据集
- 内存占用极小
- 支持SSD存储
- 查询延迟稳定
- 适合需要低内存消耗的场景
索引选择决策流程
怎么选择合适的索引，可以按照下面的流程进行选择：
可以参考：
1. 按数据规模选择
| 数据规模 | 向量数量 | 推荐索引 | 说明 |
|---|---|---|---|
| 小规模 | <100万 | FLAT | 保证100%精确度，适合对精确度要求高的场景 |
| 小规模 | <100万 | HNSW | 高性能，适合需要快速响应的在线服务 |
| 中等规模 | 100万-1亿 | IVF_FLAT | 平衡精度和性能，资源占用适中 |
| 中等规模 | 100万-1亿 | IVF_SQ8 | 较好的压缩率，适合资源受限场景 |
| 中等规模 | 100万-1亿 | ANNOY | 构建快速，内存占用小，适合频繁更新的场景 |
| 大规模 | >1亿 | IVF_PQ | 超高压缩率，适合超大规模数据集 |
| 大规模 | >1亿 | DISKANN | 基于磁盘存储，适合内存受限的大规模场景 |
2. 按性能需求选择
| 性能需求 | 推荐索引 | 性能特点 | 代价 |
|---|---|---|---|
| 100%精确 | FLAT | 保证精确结果 | 速度最慢，资源消耗大 |
| 极低延迟 | HNSW | 查询速度极快 | 建索引慢，内存占用大 |
| 高压缩率 | IVF_PQ | 超高压缩比 | 精度损失较大 |
| 稀疏向量 | SPARSE_INVERTED_INDEX | 专门优化稀疏数据 | 仅适用于稀疏向量 |
| 平衡性能 | IVF_FLAT | 精度和速度均衡 | 资源占用中等 |
3. 按应用场景选择
| 应用场景 | 推荐索引 | 适用原因 | 典型应用 |
|---|---|---|---|
| 在线服务 | HNSW | 查询延迟低，性能稳定 | 实时搜索、推荐系统 |
| 在线服务 | IVF_FLAT | 精度好，延迟可控 | 图像检索、相似度匹配 |
| 离线批处理 | IVF_SQ8 | 资源消耗适中，吞吐量大 | 数据分析、批量处理 |
| 离线批处理 | IVF_PQ | 处理超大规模数据集 | 大规模数据挖掘 |
| 文本检索 | SPARSE_INVERTED_INDEX | 优化文本特征 | 文本搜索、关键词匹配 |
| 混合搜索 | SPARSE_INVERTED_INDEX + 其他索引 | 结合稠密和稀疏特征 | 多模态搜索、复杂查询 |
