近似的需求

向量 (vector)数据库的目标是高效地找到与给定查询向量相似的向量。最直接的方法是精确近邻搜索，当查找前$k$个结果时，这通常称为k近邻 (k-NN)。它涉及计算查询向量与数据库中每个向量之间的距离（例如，余弦相似度或欧氏距离），然后对这些距离进行排序，以找到最接近的匹配项。

尽管易于理解，但随着数据集大小（$N$，向量数量）和向量维度（$D$）的增加，这种暴力方法会迅速导致计算成本过高。想象一个包含数百万甚至数十亿向量的数据库，每个向量都有数百或数千个维度，这在现代机器学习 (machine learning)应用（如自然语言处理和计算机视觉）中很常见。

维度灾难再次来袭

这个挑战源于一个被称为“维度灾难”的现象。在高维空间 (high-dimensional space)中，会出现几个问题，使得精确近邻搜索变得不切实际：

1. 计算成本： 暴力精确搜索的时间复杂度通常为 $O(N \times D)$。计算两个$D$维向量 (vector)之间的距离需要$O(D)$次操作。对数据库中所有$N$个向量执行此操作，导致总成本与数据集大小和维度的乘积成正比。对于大$N$和高$D$，这种线性扫描对于要求低延迟响应的实时应用来说实在太慢了。考虑一个包含1000万个向量（$N=10^7$），每个向量有768个维度（$D=768$）的数据库。一次精确搜索大约需要$7.68 \times 10^9$次浮点运算，这仅用于距离计算，还不包括排序或数据检索开销。

随着向量数量的增加，精确搜索的计算时间呈线性增长（假设维度固定）。

2. 传统索引的低效： 像k-d树或R树这样的空间索引结构，在低维空间（例如2D或3D地理数据）中表现良好，但随着维度的增加而变得低效。它们的性能在高维中通常会下降，不比线性扫描好，甚至更差。有效划分空间所需的分支因子随维度呈指数增长，使得这些结构不切实际。

3. 距离集中： 反直觉地，在非常高维的空间中，大多数点对之间的距离趋于非常相似。最近邻与最远邻之间的距离比率接近1。这使得仅基于距离来区分邻居本质上更难，尽管有效的嵌入 (embedding)通常通过确保向量空间中有意义的聚类来缓解此问题。

为何近似通常就已足够

鉴于这些限制，对每个查询执行精确近邻搜索对于向量 (vector)数据库中常见的大规模高维数据集来说通常是不可行的。对于语义搜索、推荐系统或图像检索等交互式应用，延迟将是不可接受的。

这时，近似近邻 (ANN) 搜索就发挥作用了。ANN算法牺牲了找到绝对数学上最近邻的保证。相反，它们旨在以高概率找到非常接近的邻居，同时显著减少所需的搜索时间和计算资源。

考虑一个典型的语义搜索应用。用户是否绝对需要其嵌入 (embedding)向量与查询嵌入具有数学上最小余弦距离的单个文档？通常不需要。他们需要一组高度相关的文档。如果一个ANN算法返回前10个精确匹配中的9个，或者返回第2、3、5个最接近的匹配而不是第1、2、3个，用户体验通常是难以区分的，特别是如果结果在语义上非常相似。

ANN的基本思想是牺牲少量准确性（通常由召回率衡量，即找到的真实最近邻的比例），以换取速度（更低延迟）和效率（更少计算、更少内存）上的显著提升。这种权衡是可配置的，允许开发者根据其特定应用的性能要求与期望的准确性水平进行平衡。

由于精确搜索无法扩展，近似方法已成为高维向量数据库中高效相似性搜索的标准。以下章节将介绍ANN的核心思想，并介绍几种实现这种平衡的流行算法。