ANN

IVF_PQ (Inverted File Index with Product Quantization) 是一种结合了倒排文件索引 (IVF) 和乘积量化 (PQ) 的高级近似最近邻 (ANN) 算法。它旨在同时解决大规模高维向量数据的存储效率和查询速度问题，是目前许多主流向量数据库（如 Faiss、Milvus）中常用且高效的索引类型之一。IVF_PQ 通过“粗粒度 + 细粒度”的两阶段搜索策略，在保证较高召回率的同时，显著降低了内存占用和查询延迟。 核心思想：首先利用 IVF 的分区策略进行粗粒度筛选，将搜索范围缩小到少数几个簇；然后在这些选定的簇中，利用 PQ 对残差向量进行高效压缩和加速距离计算，实现高效的细粒度搜索。 一、为什么需要 IVF_PQ？结合两者的优势我们已经了解了 IVF 和 PQ 各自的优势和局限： IVF (倒排文件索引) 优势：通过将数据划分为多个簇（Voronoi 单元）和构建倒排列表，实现了对搜索空间的粗粒度筛选，大大加速了查询速度。 局限：如果倒排列表中存储的是原始浮点向量，随着向量维度和数据集规模的增大，内存占用仍然会非常高，且...

乘积量化 (Product Quantization, PQ) 是一种高效的向量压缩和近似最近邻 (Approximate Nearest Neighbor, ANN) 搜索技术。它通过将高维向量分解为多个低维子向量，并对每个子向量独立进行矢量量化（即聚类），从而显著降低存储成本并加速距离计算。PQ 常与其他 ANN 算法（如 IVF）结合使用，以进一步提升大规模向量搜索系统的性能。 核心思想：将高维向量拆分为多个子向量，对每个子向量进行独立聚类，用聚类中心（码字）的索引来表示原始向量的子向量，从而达到高倍率压缩和加速距离计算的目的。 一、为什么需要乘积量化？高维向量的挑战在现代人工智能应用中，数据通常以高维向量的形式表示（例如，词嵌入、图像特征、用户行为嵌入等）。这些高维向量带来了一系列挑战： 存储成本高昂：一个 $D$ 维的浮点向量需要 $D \times 4$ 字节的存储空间。当数据集包含数百万甚至数十亿个向量时，总存储量将非常庞大，无法全部载入内存，也增加了磁盘 I/O 成本。 距离计算缓慢：计算两个 $D$ 维向量之间的距离需要 $O(D)$ 次浮点...

倒排文件索引 (Inverted File Index, IVF) 是一种广泛应用于近似最近邻 (Approximate Nearest Neighbor, ANN) 搜索的算法。它通过对高维向量空间进行分区 (Partitioning) 和构建倒排列表 (Inverted Lists)，将大规模的最近邻搜索问题分解为更小、更易于管理的问题，从而显著提高查询速度和效率。IVF 是许多主流向量数据库（如 Faiss、Milvus 中的部分索引类型）的基础。 核心思想：将整个向量数据集划分为多个簇（分区），然后只在与查询向量最相关的少数几个簇中进行局部搜索，以牺牲少量精度换取查询效率的巨大提升。 一、为什么需要 IVF？分区策略的重要性在处理海量高维向量数据时，精确最近邻 (Exact Nearest Neighbor) 搜索的计算成本过高，效率低下。例如，线性扫描需要计算查询向量与所有数据库向量的距离。为了加速这一过程，核心思想是避免与所有向量计算距离，而是通过某种机制，快速定位到可能包含最近邻的少量区域。 IVF 正是基于这种分区策略而设计的。它将复杂的全局搜索问题转化为...

近似最近邻 (Approximate Nearest Neighbor, ANN) 算法是一类旨在高效解决高维空间中“最近邻搜索”问题的计算方法。与精确最近邻 (Exact Nearest Neighbor, kNN) 搜索不同，ANN 算法通过牺牲少量的搜索精度（即不保证找到的 K 个邻居是严格意义上最接近的），来换取搜索速度和内存效率的显著提升。它们在高维数据、大规模数据集和实时应用中扮演着核心角色。 核心思想：在保证可接受的搜索精度前提下，大幅减少在高维空间中查找最近邻的计算量，克服“维数灾难”带来的性能瓶颈。 一、为什么需要 ANN？精确最近邻 (kNN) 的局限性在人工智能和数据科学领域，我们经常需要在一个大型数据集中找到与给定查询点最相似的 K 个数据点。例如： 在推荐系统中，找到与用户购买历史最相似的其他用户或商品。 在图像搜索中，找到与查询图像视觉内容最相似的其他图像。 在语义搜索中，找到与查询文本含义最接近的文档。 这些场景的核心是最近邻搜索。 1.1 精确最近邻 (Exact Nearest Neighbor, kNN) 搜索传统的精确 kNN 搜...

Hierarchical Navigable Small Worlds (HNSW) 是一种高效的近似最近邻 (Approximate Nearest Neighbor, ANN) 搜索算法。它通过构建一个多层图结构来在多维空间中快速查找与查询点最相似的数据点。HNSW 结合了分层结构（hierarchical）和跳表（skip-list）的思想，旨在克服高维空间中精确最近邻搜索的“维数灾难”问题，同时保持较高的搜索精度和查询速度。 核心思想：将高维向量空间中的搜索问题转化为在多层图结构上的路径导航问题，通过“粗粒度”的顶层快速定位到大致区域，再通过“细粒度”的底层精确搜索局部最近邻。 一、为什么需要 HNSW？ANN 算法的背景在向量数据库中，核心任务是在一个包含数百万甚至数十亿高维向量的数据集中，找到与给定查询向量最相似的 $K$ 个向量（即 K-Nearest Neighbors, K-NN）。 传统的精确 K-NN 搜索方法，如通过计算查询向量与所有存储向量的欧氏距离或余弦相似度进行全量扫描，其时间复杂度为 $O(N \cdot D)$，其中 $N$ 是向量总数，...