Introduction

全文字数：290

阅读时间：1 minute

本书使用mdbook构建，托管于github.io，以WSL环境为例，记录一下构建过程。

安装

安装WSL

略

打开WSL

安装Rust

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

验证安装是否成功：

rustc --version

安装mdbook

cargo install mdbook

构建并运行

创建mdbook项目

mdbook init paper

• 是否需要.gitignore文件：y
• 输入项目名称：paper_reading（后续可在book.toml中更改）

构建mdbook

在/paper目录下执行：

• 构建项目：

mdbook build

• 或是在浏览器中实时预览：

mdbook serve

部署

1. 新建Github仓库，将项目上传至仓库。
2. 在顶栏目录中找到Actions，搜索mdbook，点击Configure，自动生成.yml文件。点击Commit Changes提交。
3. 在顶栏目录中找到Settings，在侧边栏中找到Pages，在Build and deployment下找到Source，选择Github Actions。
4. 第二步会在/paper下创建./.github/workflows/mdbook.yml文件，在本地pull更改。
5. 之后本地修改内容后push到仓库，Github Actions会自动构建并部署。访问https://<username>.github.io/<reponame>/即可查看。

参考

• 安装Rust
• mdbook文档

vector db

全文字数: 1022

阅读时间: 6 minutes

Index

• 内存索引

  • brute-force
    • Flat
  • 倒排：
    • IVF_FLAT
    • IVF_SQ8
    • IVF_PQ
  • 树：
  • 哈希：
  • 图：
    • HNSW

• 磁盘索引

  • 图
    • DiskANN
  • 簇
    • SPANN
    • SPFresh

Brute-force

Flat

暴力搜索

• 保证精确度
• 效率低

适合在小型、百万级数据集上寻求完全精确的搜索结果。

IVF

IVF_FLAT

使用倒排索引方法，结合聚类算法（如k-means），将高维空间中的向量划分为多个簇。每个簇包含相似向量，并且选取簇的中心作为代表向量。为每个簇创建倒排索引，并将每个向量映射到所属的簇。

查询时，系统只需关注相似簇，避免了遍历整个高维空间，从而显著降低了搜索复杂度。通过参数nprobe控制搜索时考虑的簇数，平衡查询精度与速度。

• IVF_FLAT将查询向量分配到距离最近的簇中心
• 然后在该簇内执行线性搜索，查找与查询向量相似的向量。

IVF_FLAT适用于需要在精度和查询速度之间取得平衡的场景，特别是在大规模高维数据集上，能够显著降低查询时间。它非常适合那些对精度要求较高，但可以容忍一定查询延迟的应用。

IVF_SQ8

IVF_SQ8 在 IVF_FLAT 基础上增加了量化步骤。IVF_SQ8通过标量量化（Scalar Quantization）将每个维度的 4 字节浮点数表示压缩为 1 字节整数表示。量化的过程是将原始的浮点数值映射到一个较小的整数范围。

• 通过量化将存储和计算资源的消耗大大降低
• 核心思想与 IVF_FLAT 类似

IVF_PQ

IVF_PQ 在 IVF_FLAT 基础上增加了 Product Quantization 步骤。将向量空间划分为更小的子空间并进行量化。

通过将向量划分为多个子空间，并对每个子空间进行独立的量化，生成一个代码本（codebook）。这样，原始的高维向量可以由多个子空间的量化表示组合而成，从而降低存储需求并加速检索。

在IVF_PQ中，乘积量化应用于IVF的聚类过程。每个簇的中心点会被进一步量化，原始的查询向量和数据向量在计算距离时，不是直接与每个簇中心进行计算，而是与每个子空间的量化中心进行计算。这种方法不仅降低了存储开销，还减少了计算距离时的运算量。

PQ相关内容详见

Graph-based

HNSW

HNSW（Hierarchical Navigable Small World Graph）是一种图索引算法，基于分层结构和小世界图理论，用于高效的近似最近邻搜索。它构建一个多层图结构，逐层精细化，提高高维数据集的搜索效率。

HNSW结合了跳表（Skip List）和小世界图（NSW）的技术：

• 跳表：底层为有序链表，逐层稀疏化，查询从最上层开始，逐层向下查找。
• NSW图：每个节点连接若干相似节点，使用邻接列表，从入口节点开始通过边查找最接近查询向量的节点。

HNSW工作分为两个主要阶段：索引构建和查询过程:

• 索引构建：HNSW构建多层图，每层提供不同精度和速度的搜索。最上层图提供粗粒度搜索，底层则提供更精细搜索。每个新节点连接若干近邻，形成局部小世界结构，保证图的稀疏性和高效性。
• 查询过程：查询从最上层开始，逐层向下，通过图的边接近目标。到达底层后，HNSW使用局部搜索找到最接近查询向量的结果。

HNSW相关内容详见

DiskANN

Cluster-based

SPANN

Strategy

Graph

Graph Structure

Delaunay Graphs

Relative Neighborhood Graphs (RNG)

Navigable Small-World Networks (NSW)

Randomized Neighborhood Graphs

Dataset

向量索引的基本方法有哪些？

Product Quantization for Nearest Neighbor Search

全文字数: 5527

阅读时间: 34 minutes

Notations

Vector quantization

量化是一种破坏性（destructive）过程，其目的是减少表示空间的基数。形式上，一个量化器（quantizer） 是一个函数 $q$，它将一个 $D$ 维向量 $x\in {\mathbb{R}}^D$ 映射到一个向量 $q(x)\in \mathcal{C}=\{c_i;i\in \mathcal{I}\}$，其中索引集合 $\mathcal{I}$ 现在假设是有限的，即 $\mathcal{I}=0\dots k-1$。再现值（reproduction values） $c_i$ 被称为质心（centroids） 。再现值的集合 $\mathcal{C}$ 被称为码本（codebook） ，其大小为 $k$。

映射到给定索引 $i$ 的向量集合 ${\mathcal{V}}_i$ 被称为 （Voronoi）单元（cell），定义如下： $${\mathcal{V}}_i\triangleq \{x\in {\mathbb{R}}^D:q(x)=c_i\}.$$ 量化器的 $k$ 个单元构成了 ${\mathbb{R}}^D$ 的一个划分。根据定义，所有位于同一单元 ${\mathcal{V}}_i$ 内的向量都由同一个质心 $c_i$ 重构。量化器的质量通常通过输入向量 $x$ 与其重构值 $q(x)$ 之间的均方误差（MSE, Mean Squared Error） 来衡量： $$\text{MSE}(q)={\mathbb{E}}_X\left[d(q(x),x{)}^2\right]=\int p(x)d(q(x),x{)}^{2}dx,$$

• $d(x,y)=\Vert x-y\Vert$ 表示 $x$ 和 $y$ 之间的欧几里得距离
• $p(x)$ 是对应于随机变量 $X$ 的概率分布函数。

对于任意概率分布函数，通常使用蒙特卡洛采样（Monte-Carlo sampling） 进行数值计算，即在大量样本上计算 $\Vert q(x)-x{\Vert }^2$ 的平均值。

为了使量化器达到最优，它必须满足Lloyd 最优条件（Lloyd optimality conditions） 中的两个性质。

1. 向量 $x$ 必须被量化为最近的码本质心，即在欧几里得距离意义下： $$q(x)=\arg \underset{c_i\in \mathcal{C}}{\min }d(x,c_i).$$ 因此，单元（cells）由超平面（hyperplanes） 划定。
2. 重构值必须是 Voronoi 单元内向量的期望值，即： $$c_i={\mathbb{E}}_X[x\mid i]={\int }_{{\mathcal{V}}_i}p(x\mid x\in {\mathcal{V}}_i)xdx.$$

Lloyd 量化器（Lloyd quantizer） 对应于 k-means 聚类算法，它通过迭代的方式寻找近似最优的码本，不断地将训练集中向量分配给质心，并从这些分配的向量中重新估计质心。需要注意的是，k-means 只能找到局部最优解，而非全局最优解（就量化误差而言）。

均方畸变（mean squared distortion） $\xi (q,c_i)$，描述了当一个向量被重构到所属单元 ${\mathcal{V}}_i$ 的质心 $c_i$ 时的误差。令： $$p_i=\mathbb{P}(q(x)=c_i)$$ 表示一个向量被分配到质心 $c_i$ 的概率，则该误差的计算公式如下： $$\xi (q,c_i)=\frac{1}{p_i}{\int }_{{\mathcal{V}}_i}d(x,q(x){)}^{2}p(x)dx.$$ 均方误差（MSE）可以由这些量计算得到： $$\text{MSE}(q)=\sum _{i\in \mathcal{I}}{p}_i\xi (q,c_i).$$

Product quantizers

乘积量化（Product quantization） 输入向量 $x$ 被划分为 $m$ 个不同的子向量 $u_j$，其中 $1\le j\le m$，每个子向量的维度为：

$$D^{\ast }=D/m$$

其中 $D$ 是 $m$ 的整数倍。这些子向量分别使用 $m$ 个不同的量化器进行量化。因此，给定的向量 $x$ 被映射如下：

$$\underset{u_1(x)}{\underbrace{x_1,...,x_{D^{\ast }}}},...,\underset{u_m(x)}{\underbrace{x_{D-D^{\ast }+1},...,x_D}}\to q_1(u_1(x)),...,q_m(u_m(x)),$$

其中 $q_j$ 是与第 $j$ 个子向量相关的低复杂度量化器。对于子量化器 $q_j$，关联索引集合 ${\mathcal{I}}_j$、码本 ${\mathcal{C}}_j$ 以及对应的重构值 $c_{j,i}$。

乘积量化器的重构值由 乘积索引集合 的一个元素唯一标识：

$$\mathcal{I}={\mathcal{I}}_1\times ...\times {\mathcal{I}}_m$$

因此，码本定义为笛卡尔积：

$$\mathcal{C}={\mathcal{C}}_1\times ...\times {\mathcal{C}}_m$$

该集合的质心是 $m$ 个子量化器的质心的串联。假设所有的子量化器都有相同的有限重构值数量 $k^{\ast }$，因此，总质心数为：

$$k=(k^{\ast }{)}^m$$

在极端情况下（当 $m=D$），向量 $x$ 的每个分量都会被单独量化，此时 乘积量化器退化为标量量化器，其中每个分量的量化函数可能不同。

乘积量化器的优势在于可以通过多个小型质心集（子量化器的质心集合）来生成大规模质心集合。当使用 Lloyd 算法学习子量化器时，使用的样本数量有限，但码本仍然可以适应数据分布。

乘积量化器的学习复杂度是 $m$ 倍于在 $D^{\ast }$ 维度上进行 $k^{\ast }$ 质心的 k-means 聚类的复杂度。

显式存储码本 $\mathcal{C}$ 并不高效，因此只存储所有子量化器的 $m\times k^{\ast }$ 个质心，即：

$$m{D}^{\ast }{k}^{\ast }=k^{\ast }D$$

个浮点值。量化一个元素需要 $k^{\ast }D$ 次浮点运算。下表总结了 k-means、HKM 和乘积 k-means 的计算资源需求。乘积量化器 是唯一能在大 $k$ 值时被索引存储于内存的方法。

为了保证良好的量化性能，在 $k^{\ast }$ 取常数时，每个子向量应具有相近的能量。一种方法是在量化前用随机正交矩阵变换向量，但对于大多数向量类型来说，这并不需要，也不推荐，因为相邻分量通常由于构造上的相关性而更适合使用相同的子量化器量化。

由于子空间正交，乘积量化器的平方畸变（Squared Distortion） 可计算为：

$$\text{MSE}(q)=\sum _j\text{MSE}(q_j)$$

其中 $\text{MSE}(q_j)$ 是与子量化器 $q_j$ 相关的畸变。

下图 显示了 MSE 随代码长度变化的曲线，其中代码长度为： $l=m{\log }_2{k}^{\ast }$,$k^{\ast }$是2的幂

可以观察到，在给定比特数的情况下，使用少量子量化器，但每个子量化器有更多质心，比使用多个子量化器但每个子量化器比特数较少要更好。

在极端情况下（当 $m=1$），乘积量化器退化为标准 k-means 码本。

高 $k^{\ast }$ 值 会增加量化器的计算成本（如表 I 所示），同时也增加了存储质心的内存开销（即 $k^{\ast }\times D$ 个浮点数）。如果质心查找表无法适应缓存，则效率会降低。

在 $m=1$ 的情况下，为了保证计算开销可控，无法使用超过 16 位的编码。通常，选择 $k^{\ast }=256$ 且 $m=8$ 是一个合理的选择。

Search

Computing distances using quantized codes

假设有一个查询向量 $x$ 和一个数据库向量 $y$。有两种方法来计算这些向量之间的近似欧几里得距离：对称距离计算（SDC） 和 非对称距离计算（ADC）。

对称距离计算（Symmetric Distance Computation, SDC）：

在 SDC 方法中，查询向量 $x$ 和数据库向量 $y$ 均由其对应的质心 $q(x)$ 和 $q(y)$ 表示。因此，距离 $d(x,y)$ 近似为：

$$\hat{d}(x,y)\triangleq d(q(x),q(y))$$

利用 乘积量化器，这个距离可以高效地计算为：

$$\hat{d}(x,y)=d(q(x),q(y))=\sqrt{\sum _{j}d(q_j(x),q_j(y){)}^2}$$

其中，距离项 $d(c_{j,i},c_{j,i^{\prime }}{)}^2$ 从查找表中读取，该查找表与第 $j$ 个子量化器相关。每个查找表包含所有质心对 $(i,i^{\prime })$ 之间的平方距离，即存储了 $(k^{\ast }{)}^2$ 个平方距离。

非对称距离计算（Asymmetric Distance Computation, ADC）：

在 ADC 方法中，数据库向量 $y$ 仍由其质心 $q(y)$ 表示，但查询向量 $x$ 不经过编码。因此，距离 $d(x,y)$ 近似为：

$$\tilde{d}(x,y)\triangleq d(x,q(y))$$

其计算方式如下：

$$\tilde{d}(x,y)=d(x,q(y))=\sqrt{\sum _{j}d(u_j(x),q_j(u_j(y)){)}^2}$$

其中，平方距离 $d(u_j(x),c_{j,i}{)}^2$ 在搜索之前已经计算，其中 $j=1,...,m$，$i=1,...,k^{\ast }$。

在最近邻搜索中，实际上不会计算平方根，直接使用平方距离进行排序。

下表 总结了在数据集中搜索最近邻所涉及的不同步骤的复杂度。假设数据集 $\mathcal{Y}$ 的大小为 $n=|\mathcal{Y}|$，可以看到 SDC 和 ADC 的查询准备成本是相同的，并且不依赖于数据集大小 $n$。

当 $n$ 很大（$n>k^{\ast }{D}^{\ast }$）时，计算量主要由求和运算决定。而搜索 $k$ 个最小元素的复杂度 是对 $n\gg k$ 的元素进行无序比较的平均复杂度。

SDC 与 ADC 的对比

在本文的剩余部分，将重点讨论 ADC 方法。

Analysis of the distance error

分析使用 $\tilde{d}(x,y)$ 代替 $d(x,y)$ 所带来的距离误差。这一分析不依赖于乘积量化器，对满足 Lloyd 最优条件的任何量化器都适用。

在重构的均方误差（MSE）准则的基础上，距离畸变（distance distortion） 通过均方距离误差（MSDE） 来衡量：

$$\text{MSDE}(q)\triangleq \iint (d(x,y)-\tilde{d}(x,y){)}^{2}p(x)dxp(y)dy.$$

根据三角不等式有：

$$d(x,q(y))-d(y,q(y))\le d(x,y)\le d(x,q(y))+d(y,q(y)).$$

同样地，可以写成：

$$(d(x,y)-d(x,q(y)){)}^2\le d(y,q(y){)}^2.$$

可得：

$$\text{MSDE}(q)\le \int p(x)\left(\int d(y,q(y){)}^{2}p(y)dy\right)dx.$$

最终得到：

$$\text{MSDE}(q)\le \text{MSE}(q).$$

其中，$\text{MSE}(q)$ 是与量化器 $q$ 相关的均方误差。

该不等式适用于任何量化器，表明本方法的距离误差在统计意义上受量化器的 MSE 约束。

对于 对称版本（SDC），类似的推导表明其误差在统计上受 $2\times \text{MSE}(q)$ 约束。因此，最小化量化误差（MSE）是重要的，因为它可以作为距离误差的统计上界。

如果在最高排名的向量上执行精确距离计算（如 局部敏感哈希（LSH）），那么量化误差可以用作动态选择需要后处理的向量集合的标准，而不是随意选择某一部分向量。

Estimator of the squared distance

分析使用 $\hat{d}(x,y)$ 或 $\tilde{d}(x,y)$ 进行估算时，如何在平均意义上低估描述符之间的距离。

该图显示了在 1000 个 SIFT 向量数据集中查询一个 SIFT 描述符所得的距离估计。该图比较了真实距离与SDC与ADC计算出的估计值。可以清楚地看到，这些距离估计方法存在偏差（bias），且对称版本（SDC）更容易受到偏差的影响。

为了消除偏差，计算平方距离的期望值。在乘积量化方法中，一个给定向量 $y$ 的近似值 $q(y)$ 由其子量化索引 $q_j(u_j(y))$（其中 $j=1,...,m$）获得。

量化索引标识了向量 $y$ 所处的单元 ${\mathcal{V}}_i$。因此，可以计算期望平方距离 $\tilde{e}(x,q(y))$ 作为修正项：

$$\tilde{e}(x,y)\triangleq {\mathbb{E}}_Y[(x-Y{)}^2\mid q(Y)=c_i]$$

$$={\int }_{{\mathcal{V}}_i}(x-y{)}^{2}p(y\mid i)dy$$

$$=\frac{1}{p_i}{\int }_{{\mathcal{V}}_i}(x-c_i+c_i-y{)}^{2}p(y)dy.$$

根据Lloyd 最优条件有：

$${\int }_{{\mathcal{V}}_i}(y-c_i)p(y)dy=0.$$

因此可简化为：

$$\tilde{e}(x,y)=(x-q(y){)}^2+{\int }_{{\mathcal{V}}_i}(q(y)-y{)}^{2}p(y\mid y\in {\mathcal{V}}_i)dy.$$

$$=\tilde{d}(x,y{)}^2+\xi (q,q(y)).$$

其中，$\xi (q,q(y))$ 代表了重构误差（distortion），即 $y$ 由其重构值 $q(y)$ 近似时的误差。

在乘积量化框架下，向量 $x$ 与 $y$ 之间的期望平方距离可以通过修正方程 (13) 计算：

$$e(x,y)=d(x,y{)}^2+\sum _j{\xi }_j(y).$$

其中，修正项 ${\xi }_j(y)$ 为第 $j$ 个子量化器的平均畸变（distortion）：

$${\xi }_j(y)\triangleq \xi (q_j,q_j(u_j(y))).$$

这些畸变值可以预先学习，并存储在查找表中，供量化索引 ${\mathcal{I}}_j$ 使用。

对于 对称版本（SDC），即 $x$ 和 $y$ 均经过量化，类似的推导可以得到修正后的平方距离估计公式：

$$\hat{e}(x,y)=\hat{d}(x,y{)}^2+\sum _j{\xi }_j(x)+\sum _{j^{\prime }}{\xi }_{j^{\prime }}(y).$$

Discussion 该图显示了真实距离与估计距离之间的概率分布。该实验基于大规模 SIFT 描述符数据集。

• 进行距离估计时，存在明显偏差。
• 采用 修正版本（，距离估计的偏差显著减少。

然而，修正偏差 会导致估计方差增大，这在统计学上是一个常见现象。此外，对于最近邻搜索而言：

• 修正项往往估计值更大，这可能会惩罚具有罕见索引的向量。
• 在 非对称版本（ADC） 中，修正项与查询 $x$ 无关，只依赖于数据库向量 $y$。

在实验中，修正方法在整体上效果较差，因此建议在最近邻搜索任务中使用原始版本，而修正版本仅在需要精准距离估计的任务中适用。

Avoid exhaustive search

使用乘积量化器进行近似最近邻搜索非常高效（每次距离计算仅需 $m$ 次加法运算），并且大大减少了存储描述符所需的内存。然而，标准搜索方法是穷举式（Exhaustive）的。

为了避免穷举搜索：

• 倒排文件系统（Inverted File System, IVF）
• 非对称距离计算（ADC）

该方法称为 IVFADC。

传统倒排文件仅存储图像索引，而本文在此基础上增加了额外的编码，以便对每个描述符进行更精细的存储。使用乘积量化器对向量与其对应的粗质心之间的残差进行编码。

• 显著加速搜索过程，代价仅是每个描述符存储额外的少量比特/字节。
• 提高搜索精度，因为对残差进行编码比直接编码向量本身更加精确。

Coarse quantizer, locally defined product quantizer

码本（codebook）是通过 k-means 学习得到的，并生成了一个量化器 $q_c$，在后续内容中称为 粗量化器（coarse quantizer）。对于 SIFT 描述符，与 $q_c$ 相关的质心（centroid）数量 $k^{\prime }$ 通常在 1000 到 1000000 之间。因此，与 乘积量化器相比，粗量化器的规模较小。

除了粗量化器，还使用乘积量化器对向量的描述进行细化。具体来说，粗量化器 $q_c(y)$ 生成的质心可以提供全局信息，但仍需进一步编码残差信息，因此使用 乘积量化器 $q_p$ 对残差向量进行编码：

$$r(y)=y-q_c(y),$$

其中，残差向量 $r(y)$ 表示 Voronoi 单元中的偏移量。由于残差向量的能量相比原始向量要小，因此存储其量化信息的代价也较低。

向量 $y$ 可被近似表示为：

$$\ddot{y}\triangleq q_c(y)+q_p(y-q_c(y)).$$

它可以用元组 $(q_c(y),q_p(r(y)))$ 来表示。

类比于二进制表示的概念：

• 粗量化器（$q_c$） 提供的是最高有效位（MSB），用于大致定位向量。
• 乘积量化器（$q_p$） 提供的是最低有效位（LSB），用于精细校正残差信息。

查询向量 $x$ 和数据库向量 $y$ 之间的距离可以近似计算为 $\ddot{d}(x,y)$：

$$\ddot{d}(x,y)=d(x,\ddot{y})=d(x-q_c(y),q_p(y-q_c(y))).$$

令 $q_{p_j}$ 表示第 $j$ 个子量化器（Subquantizer），则可分解计算该距离：

$$\ddot{d}(x,y{)}^2=\sum _{j}d(u_j(x-q_c(y)),q_{p_j}(u_j(y-q_c(y))){)}^2.$$

类似于 ADC（Asymmetric Distance Computation） 策略，对于每个子量化器 $q_{p_j}$，预计算部分残差向量 $u_j(x-q_c(y))$ 与所有质心 $c_{j,i}$ 之间的距离，并存储这些值。

乘积量化器是在一个学习集合中通过残差向量训练得到的。虽然向量最初由粗量化器映射到不同的索引，但最终的残差向量被用于训练一个统一的乘积量化器。

假设当残差在所有 Voronoi 单元上进行边际化（Marginalization）时，相同的乘积量化器仍然有效。然而，这种方法的效果可能不如为每个 Voronoi 单元单独训练一个独立的乘积量化器，但后者的计算成本极高。如果要为每个 Voronoi 单元分别训练乘积量化器，则需要存储 $k^{\prime }$ 个乘积量化码本，即：

$$k^{\prime }\times d\times k^{\ast }$$

个浮点值。这对于典型的 $k^{\prime }$ 值来说，将会导致极高的存储需求，在实际应用中难以承受。

Indexing structure

使用粗量化器（coarse quantizer）来实现一种倒排文件结构（inverted file structure），它被组织成一个包含列表的数组 ${\mathcal{L}}_1\dots {\mathcal{L}}_{k^{\prime }}$。如果 $\mathcal{Y}$ 是要索引的向量数据集，那么与质心 $c_i$ 相关联的列表 ${\mathcal{L}}_i$ 将存储集合 $\{y\in \mathcal{Y}:q_c(y)=c_i\}$。

在倒排列表 ${\mathcal{L}}_i$ 中，与 $y$ 相关的条目包含一个向量标识符（vector identifier）和编码后的残差 $q_p(r(y))$：

标识符字段是倒排文件结构带来的开销。根据存储向量的不同特性，标识符不一定是唯一的。例如，在使用局部描述符（local descriptors）表示图像时，图像标识符可以替代向量标识符，即同一张图像的所有向量都可以使用相同的标识符。因此，20 位的标识符字段足以在一个包含一百万张图像的数据集中唯一标识一张图像。

通过索引压缩（index compression）可以进一步降低存储开销，使存储标识符的平均成本降低到约 8 比特，具体取决于参数。

Search algorithm

倒排文件（inverted file）是非穷尽（non-exhaustive）的关键。当搜索向量 $x$ 的最近邻时，倒排文件提供了一个 $\mathcal{Y}$ 的子集，用于计算距离：仅扫描与 $q_c(x)$ 对应的倒排列表 ${\mathcal{L}}_i$。

然而，$x$ 及其最近邻通常不会被量化到同一个质心，而是被量化到相邻的质心。为了解决这个问题，采用 多重分配（multiple assignment） 策略 。查询向量 $x$ 被分配到 $w$ 个索引，而不是仅仅一个索引，这些索引对应于 代码本 $q_c$ 中 $x$ 的 $w$ 个最近邻。然后，扫描所有相应的倒排列表。多重分配不会用于数据库向量，因为这会增加内存占用。

下图概述了数据库的索引和搜索过程。

索引（Indexing）向量 $y$ 的过程如下：

1. 对 $y$ 进行量化，得到 $q_c(y)$；
2. 计算残差（residual）：$r(y)=y-q_c(y)$；
3. 对残差 $r(y)$ 进行量化，得到 $q_p(r(y))$，对于乘积量化器（product quantizer），这意味着将 $u_j(y)$ 映射到 $q_j(u_j(y))$，其中 $j=1\dots m$；
4. 向倒排列表 ${\mathcal{L}}_{q_c(y)}$ 添加新条目，该条目包含 向量（或图像）标识符 和 二进制编码（即乘积量化器的索引）。

查询（Searching）最近邻 $x$ 的过程如下：

1. 将 $x$ 量化到代码本 $q_c$ 中最近的 $w$ 个质心；

   为了便于表述，接下来的两步中简单地用 $r(x)$ 来表示与这些 $w$ 个分配相关的残差。这两个步骤适用于所有 $w$ 个分配。

2. 计算平方距离 $d(u_j(r(x)),c_{j,i}{)}^2$，对于每个子量化器 $j$ 以及其所有质心 $c_{j,i}$；

3. 计算 $r(x)$ 与倒排列表中所有索引向量的平方距离；

   使用上一步计算的子向量到质心距离，最终得到总距离。这一过程涉及查找 $m$ 个预计算值（见公式 31）。

4. 根据估计距离选择 $K$ 个最近邻：

   • 这一过程使用 最大堆（Maxheap） 结构（固定容量）来存储 当前已找到的 $K$ 个最小距离；
   • 每次计算距离后，仅当该点的距离小于最大堆中当前的最大距离时，才将其插入数据结构。

只有第 3 步 依赖于数据库的大小。与 ADC（Asymmetric Distance Computation，非对称距离计算） 相比，额外的 量化 $x$ 到 $q_c(x)$ 仅涉及计算 $k^{\prime }$ 个 D 维向量的距离。假设倒排列表是均衡的，则需要解析 $n\times w/k^{\prime }$ 个条目。因此，该搜索方法比 ADC 显著更快。

Product Quantization for Nearest Neighbor Search

Characterizing the Dilemma of Performance and Index Size in Billion-Scale Vector Search and Breaking It with Second-Tier Memory

全文字数: 2671

阅读时间: 16 minutes

Background

Second-tier memory（如通过 RDMA 或 CXL 连接的远程 DRAM/NVM）具有 细粒度的访问能力，能够有效解决 搜索粒度与访问粒度不匹配 的问题。

然而：

• 现有索引主要针对 SSD 设计，在 second-tier memory 上表现不佳。
• Second-tier memory 的行为更类似于存储，使其像 DRAM 那样使用时效率较低。

为此，本文提出了一种专为 second-tier memory 性能特性优化的 图索引与簇索引 方案，具有以下优势：

• 最优性能
• 数量级更小的索引放大

High Performance and Low Index Size Dilemma

增大索引大小可以提升性能：

• 对于 图索引（graph indexes），增加更多的边可以减少跳数（I/O 操作）。
• 对于 簇索引（cluster indexes），在簇之间复制相邻向量可以减少搜索的簇数量。

相反，缩小索引大小会导致性能下降。一种在不改变算法的情况下减少索引大小的替代方案是 复制地址而不是重复存储向量。然而，这种方法会引入额外的小随机读操作，在 SSD 上会显著降低性能。

根本原因：工作负载模式与 SSD 要求不匹配

• SSD 的页面通常为 4KB，而 second-tier memory 支持 更细粒度的 256B 访问。
• 图索引和簇索引 的读取操作通常仅涉及 几百字节的数据。

Graph Index

• 图索引（Graph indexes） 能够捕捉向量之间的细粒度关系，使得在访问 top-k 以外的少量额外向量时，保持较低的读取放大（read amplification）。
• 然而，其 指针跳转（pointer-chasing） 访问模式导致 高延迟，并且 带宽利用率较低。

在 DiskANN 中，每个向量默认分配 32 条边，每条边由 4B 向量 ID 表示。这意味着边列表的大小可能会超过原始数据的大小。例如，在 SPACEV 中，一个大小为 100B 的顶点需要 128B 来存储其边信息。

理想情况下，边所引起的空间放大应尽可能减少。然而，减少边的数量会增加查询向量的 遍历距离（traversal distance）。

即使增加边的数量，每次图遍历的加载量仍然受限于 SSD 的访问粒度（4KB）。如果超出此限制，索引大小将急剧膨胀，甚至可能达到原始数据集大小的 39 倍。例如，一个 100B 的节点若使用 3,996B 存储边信息，将导致 极高的空间占用。

Cluster Index

• 存储效率高，支持 大批量读取（large bulk reads） 簇数据。
• 由于簇内存在冗余向量读取，导致 高读取放大（read amplification）。
• 向量复制 造成 高空间放大（space amplification）。

理想情况下，簇索引的大小应尽可能小：

• 簇的索引数据 远小于整个数据集的规模，通常相差数个数量级。
• 每个簇可能跨越多个块，因此不需要填充（padding）。

为了 解决边界问题导致的准确率下降，相邻簇之间会复制 边界向量（boundary vectors），这需要 额外的索引存储空间。

为 减少过多的向量复制，一种替代方案是 增加每次查询搜索的簇数量。但 额外的簇搜索 会导致 额外的向量读取，从而 降低性能。

经验上来看，增加索引大小仍然可以提升吞吐量（throughput）。

Workloads Mismatch SSD Requirements

• 图索引（Graph index） 需要 细粒度的存储读取 以保持可接受的索引大小。然而，这与 使用足够大的 I/O 负载（4 KB） 来高效利用 SSD 等传统存储设备 的需求相冲突。

• 簇索引（Cluster index） 需要 不规则 I/O 来进行 去重（deduplication）。与其在其他簇中存储重复的向量数据，不如 存储一个指向原始簇的地址。向量地址（8B） 远小于实际数据（128–384B）。然而，这意味着每个被复制的向量都需要 单独的小随机读（100–384B） 来获取原始向量，进而影响读取性能。

Power of Second-tier Memory

• 细粒度块大小（Fine-grained block sizes）

  • 更高效地利用设备带宽

• 对不规则 I/O 具有更强的适应性（Robust to irregular I/O）

  • 将（部分）顺序访问 替换为 随机访问

Improvement

Graph Index

Software Pipeline

在发出second-tier memory请求后，立即调度下一个未完成的查询执行，从而在软件层面以流水线方式高效处理不同的查询。

Compressed Layout

DiskANN 采用填充方式进行存储，这种填充设计会浪费索引空间。在 second-tier memory 上，由于其能够有效适应 跨块大小的不规则 I/O，填充设计已无必要。因此直接选择 压缩稀疏行（Compressed Sparse Row，CSR） ，以减少存储空间占用，同时保持性能稳定。

Cluster Index

Decoupled Layout

向量数据采用独立存储，而每个簇仅存储对应向量的地址（b）。这样，对于需要复制的向量，仅复制地址，而无需复制向量本身，从而有效减少存储开销。

尽管decoupled Layout有助于缩小索引大小，但它将原本0.1–2.2 MB 的顺序 I/O 拆分为 60–68 次小随机 I/O（每次读取 100–384B）。更具体而言，工作负载中的 98% I/O 变成了小随机读取，而在 second-tier memory 上，这些 I/O 操作的效率同样不高。

Vector Grouping

为减少工作负载中的 小 I/O 操作，在 decoupled design 之上提出了 向量分组（vector grouping） 方法，以尽量减少 小随机 I/O。通过 将同一簇的向量分组存储在相邻的存储位置，可以使用 一次大 I/O 操作 读取整个分组的向量数据（见 图 11(c)）。分组操作 在 索引构建后（post index build） 进行。

由于 不复制向量，必然会存在某些簇无法通过一次 I/O 读取其所有向量。因此，分组的性能 主要取决于 向量如何被分组。

向量分组的目标是 确定哪些向量应该被分组，以减少给定工作负载中的小 I/O。这等价于 向特定簇分配向量 的问题。假设在一个向量数据库中，向量集合为 V，簇集合为 C，使用 $P_{i,j}$ 表示 第 i 个向量是否被分配到某个分组。

采用 整数线性规划（Integer Linear Programming, ILP） 来找到 $P_{i,j}$ 的最优分组，目标是 最小化发往存储管理节点（MN）的 I/O 请求。由于 I/O 数量取决于 每个簇的访问频率，我们使用 $h_{j}$ 来表示 簇 j 的访问频率。

这些频率可以通过 后台监控工作负载 获得，并可以根据 访问频率的变化 动态调整布局。

综合以上内容，问题可被公式化如下：

$$ \text{min} \sum_{j}^{|C|} h_j \cdot \left(1 + \sum_{i}^{|V|} P_{i,j}\right) $$

约束条件：

• 簇约束（Cluster constraints）
  根据簇索引设计，每个向量必须 分配到一个簇，但可以 复制到多个相邻簇。约束条件如下：

  $$ \begin{cases} 0 \leq A_{i,j} \leq 1, \quad i \in [0, |V|], j \in [0, |C|] \ \sum_{j}^{|C|} A_{i,j} \geq 1, \quad i \in [0, |V|] \end{cases} $$

• 分组约束（Group constraints）
  分组算法必须将 一个向量分配给唯一的簇组，约束如下：

  $$ \begin{cases} 0 \leq P_{i,j} \leq 1, \quad i \in [0, |V|], j \in [0, |C|] \ \sum_{j}^{|C|} P_{i,j} = 1, \quad i \in [0, |V|] \end{cases} $$

Conclusion

Second-tier memory is a promising storage medium for vector indexes.

Characterizing the Dilemma of Performance and Index Size in Billion-Scale Vector Search and Breaking It with Second-Tier Memory

NSG

Introduction

单调相对邻近图（MRNG，Monotonic Relative Neighborhood Graph）

• 保证连通性
• 降低平均出度
• 缩短搜索路径
• 减少索引大小

设计了 MRNG 的近似结构，称为 导航扩展图（NSG）

DiskANN

全文字数: 4966

阅读时间: 31 minutes

Background

DiskANN系列主要包含三篇论文：

• DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
• FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search
• Filtered − DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters

SNG

DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node

Algorithm

GreedySearch

大多数基于图的近似最近邻搜索（ANN）算法的工作方式如下：在索引构建过程中，它们根据数据集 $P$ 的几何属性构建图 $G=(P,E)$。在搜索时，对于查询向量 $x_q$，搜索采用自然的贪心或最优优先遍历，如算法1中的方式，在图 $G$ 上进行。从某个指定的点 $s\in P$ 开始，它们遍历图以逐步接近 $x_q$。

在SNG中，每个点 $p$ 的外部邻居通过以下方式确定：初始化一个集合 $S=P\setminus \{p\}$。只要 $S\ne \varnothing$，从 $p$ 到 $p^{\ast }$ 添加一条有向边，其中 $p^{\ast }$ 是离 $p$ 最近的点，从集合 $S$ 中移除所有使得 $d(p,p^{\prime })>d(p^{\ast },p^{\prime })$的点 $p^{\prime }$。因此，贪心搜索（GreedySearch(s, $x_p$, 1)）从任何 $s\in P$ 开始都将收敛到 $p$，对于所有基点 $p\in P$ 都成立。

RobustPrune

满足SNG性质的图都是适合贪心搜索搜索过程的良好候选图。然而，图的直径可能会相当大。例如，如果点在实数线的一维空间上线性排列，图的直径是 $O(n)$，其中每个点连接到两个邻居（一个在两端），这样的图满足SNG性质。搜索此类存储在磁盘上的图将导致在搜索路径中访问的顶点的邻居需要大量的顺序读取。

为了解决这个问题，希望确保查询距离在搜索路径的每个节点上按乘法因子 $\alpha >1$ 递减，而不仅仅是像SNG性质那样递减。

Vamana Indexing

Vamana 以迭代的方式构建有向图 $G$。

1. 图 $G$ 被初始化，使得每个顶点都有 $R$ 个随机选择的外部邻居(在 $R>\log n$ 时连接良好)。
2. 让 $s$ 表示数据集 $P$ 的中心点，它将作为搜索算法的起始节点。
3. 算法按随机顺序遍历 $p\in P$ 的所有点，并在每一步更新图，使其更加适合贪心搜索（GreedySearch(s, $x_p$, 1, L)）收敛到 $p$。

实际上，在对应点 $p$ 的迭代中，

1. Vamana 在当前图 $G$ 上运行 GreedySearch(s, $x_p$, 1, L)，并将 $V_p$ 设置为贪心搜索路径中所有访问过的点的集合。
2. 算法通过运行 RobustPrune(p, $V_p$, $\alpha$, $R$) 来更新图 $G$，以确定 $p$ 的新外部邻居。
3. Vamana 更新图 $G$，通过为所有 $p^{\prime }\in N_{\text{out}}(p)$ 添加反向边（$p^{\prime },p$）。这确保了在搜索路径和 $p$ 之间的顶点连接，从而确保更新后的图会更适合贪心搜索（GreedySearch(s, $x_p$, 1, L)）收敛到 $p$。
4. 添加这种形式的反向边（$p^{\prime },p$）可能会导致 $p^{\prime }$ 的度数超过阈值，因此每当某个顶点 $p^{\prime }$ 的外度超过 $R$ 的度数阈值时，图通过运行 RobustPrune($p^{\prime }$, $N_{\text{out}}(p^{\prime })$, $\alpha$, $R$) 来修改，其中 $N_{\text{out}}(p^{\prime })$ 是 $p^{\prime }$ 的现有外部邻居集合。

算法对数据集进行两次遍历，第一次遍历使用 $\alpha =1$，第二次使用用户定义的 $\alpha \ge 1$。

Design

Index Design

在数据集 $P$ 上运行 Vamana，并将结果存储在 SSD 上。在搜索时，每当算法1需要某个点 $p$ 的外部邻居时， 从 SSD 中获取该点的信息。

然而，单纯存储包含十亿个100维空间中的向量数据远超过工作站的RAM！这引出了两个问题：

1. 如何构建一个包含十亿个点的图？
2. 如果不能在内存中存储向量数据，如何在算法1的搜索时执行查询点与候选点之间的距离比较？

问题一

通过聚类技术（如k-means）将数据划分成多个较小的分片，为每个分片建立一个单独的索引，并仅在查询时将查询路由到几个分片。然而，这种方法会因为查询需要路由到多个分片而导致搜索延迟增加和吞吐量减少。

与其在查询时将查询路由到多个分片，不如将每个基础点发送到多个相邻的中心以获得重叠的聚类。事实上，我们将一个十亿点的数据集通过k-means划分为k个聚类（k=40，通常ℓ=2就足够），然后将每个基础点分配给ℓ个最近的中心。接着，我们为分配给每个聚类的点建立Vamana索引（这些点现在只有约Nℓ/k个点，可以在内存中建立索引），最后通过简单的边缘合并将所有不同的图合并为一个单一的图。

问题二

将每个数据库点 $p\in P$ 的压缩向量 $x_p$ 存储在主存中，同时将图存储在SSD上。使用Product Quantization将数据和查询点编码为短代码在查询时高效地计算近似距离 $d(x_p,x_q)$。尽管在搜索时只使用压缩数据，但是Vamana在构建图索引时使用的是“全精度坐标”，因此能够高效地引导搜索到图的正确区域，

Index Layout

将所有数据点的压缩向量存储在内存中，并将图以及全精度向量存储在SSD上。在磁盘中，对于每个点 $i$，我们存储其全精度向量 $x_i$，并跟随其$\le R$ 个邻居的标识。如果一个节点的度小于 $R$，我们用零填充，以便计算数据在磁盘中对应点 $i$ 的偏移量变得简单，并且不需要在内存中存储偏移量。

Beam Search

运行算法1，按需从SSD获取邻居信息 $N_{\text{out}}(p^{\ast })$。这需要很多次SSD的往返（每次往返仅需几百微秒），从而导致更高的延迟。为了减少往返SSD的次数（以便顺序地获取邻居），而不过多的增加计算量，一次性获取一个较小数量 $W$（例如4、8）最近的点的邻居，并将 $\mathcal{L}$ 更新为这一小步中的前 $L$ 个最优点。从SSD获取少量随机扇区的时间几乎与获取一个扇区的时间相同。

• 如果 $W=1$，这种搜索类似于正常的贪婪搜索。
• 如果 $W$ 太大，比如16或更多，则计算和SSD带宽可能会浪费。

Caching Frequently Visited Vertices

为了进一步减少每个查询的磁盘访问次数，缓存与一部分顶点相关的数据，这些顶点可以基于已知的查询分布来选择，或者通过缓存所有距离起始点 $s$ 为 $C=3$ 或 $C=4$ 跳的顶点来选择。

由于索引图中与距离 $C$ 相关的节点数量随着 $C$ 增加呈指数增长，因此较大的 $C$ 值会导致过大的内存占用。

Implicit Re-Ranking Using Full-Precision Vectors

由于PQ是一种有损压缩方法，因此使用基于PQ的近似距离计算出的与查询最接近的 $k$ 个候选点之间存在差距。为了解决这个问题，使用存储在磁盘上与每个点相邻的全精度坐标。

事实上，在搜索过程中检索一个点的邻域时，也可以在不增加额外磁盘读取的情况下获取该点的全精度坐标。这是因为读取4KB对齐的磁盘地址到内存的成本不高于读取512B，而顶点的邻域（对于度为128的图，邻域大小为 $4\times 128$ 字节）和全精度坐标可以存储在同一磁盘扇区中。

因此，随着BeamSearch加载搜索前沿的邻域，它还会缓存在搜索过程中访问的所有节点的全精度坐标，而不需要额外的SSD读取操作。这使得我们能够基于全精度向量返回前 $k$ 个候选点。

Evaluation

(具体实验条件参见论文)

• 内存搜索性能比较
  • NSG和Vamana在所有情况下recall@100都优于HNSW
  • Vamana的索引构建时间优于HNSW和NSG
• 跳数（搜索中基于图的跳跃次数）比较
  • Vamana更适合用于基于SSD的搜索，其在大型数据集上比HNSW和NSG要快2到3倍。
  • 随着最大度数的增加，HNSW和NSG跳数出现了停滞趋势，而Vamana跳数有所减少，因为它能够增加更多的长距离边缘。推测Vamana在 $\alpha >1$ 时，比HNSW和NSG更好地利用了SSD提供的高带宽（在BeamSearch中，通过最大化𝑊来扩展搜索进行更大的磁盘读取）。
• One-Shot Vamana 和 Merged Vamana
  • Single：2 days, degree=113.9, peek memory usage=1100GB
  • Merged：5 days, degree=92.1, peek memory usage＜64GB
  • 单一索引优于合并索引，合并索引的延迟更高
  • 合并索引仍是十亿规模k-ANN索引和单节点服务的一个非常好的选择：相比单一索引，目标召回时只需增加不到20%的额外延迟

FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search

Introduction

在许多重要的现实场景中，用户与系统的交互会创建并销毁数据，并导致 $P$ 的更新。针对这种应用的ANN系统需要能够托管包含数万亿个实时更新点的索引，这些更新可以反映数据集中的变化，理想情况下是实时进行的。

形式上定义 fresh-ANNs 问题如下：给定一个随时间变化的数据集 $P$ （在时间 $t$ 时的状态为 $P_t$），目标是维护一个动态索引，该索引计算任何查询 $q$ 在时间 $t$ 时，仅在活动数据集 $P_t$ 上的近似最近邻。这样的系统必须支持三种操作：

• （a）插入新点，
• （b）删除现有点，以及
• （c）给定查询点进行最近邻搜索。

一个 fresh-ANNs 系统的总体质量由以下几个方面来衡量：

• 搜索查询的召回率与延迟之间的权衡，以及随着数据集 $P$ 演变其对时间的鲁棒性。
• 插入和删除操作的吞吐量与延迟。
• 构建和维护此类索引所需的整体硬件成本（CPU、RAM 和 SSD 占用）。

freshDiskANN 注重于 quiescent consistency 的概念

删除操作为什么难以实现？

HNSW算法通过将删除的点添加到黑名单并将其从搜索结果中省略来处理删除请求，因为缺乏能够在保持原始搜索质量的同时修改可导航图的方法。考虑三种流行的静态ANNS算法，分别是HNSW、NSG和Vamana，并尝试了以下自然更新策略，看看在面对插入和删除操作时它们的表现。

• 插入策略。 对于插入一个新点 $p$，运行相应算法使用的候选生成算法，并添加选定的入边和出边；如果任何顶点的度数超过预算，则运行相应的修剪过程。
• 删除策略A。 当删除一个点 $p$ 时，简单地删除与 $p$ 相关的所有入边和出边，而不添加任何新边以弥补潜在的可导航性丧失。
• 删除策略B。 当删除一个点 $p$ 时，移除所有与 $p$ 相关的入边和出边，并在 $p$ 的局部邻域中添加边：对于图中的每对有向边 $(p_{in},p)$ 和 $(p,p_{out})$，在更新的图中添加边 $(p_{in},p_{out})$。如果任何顶点的度数超过限制，则运行相应算法的修剪过程来控制度数。

一个稳定的更新策略应该在每个周期之后产生相似的搜索性能，因为索引是建立在相同的数据集上的。然而，所有算法都表现出搜索性能持续下降的趋势。

FreshVamana

随着图的更新，图变得稀疏（平均度数较小），因此变得不那么可导航。怀疑这是由于现有算法（如HNSW和NSG）使用非常激进的修剪策略来偏向稀疏图所导致的。

α-RNG Property. DiskANN中构建的图的关键思想是采用更为宽松的剪枝过程，它仅在存在一条边 $(p,p^{\prime })$ 且 $p^{\prime }$ 必须比 $p$ 更接近 $p^{\prime \prime }$ 时才移除边 $(p,p^{\prime })$，即 $d(p^{\prime },p^{\prime \prime })<\frac{d(p,p^{\prime \prime })}{\alpha }$，其中 $\alpha >1$。使用 $\alpha >1$ 生成这样的图直观地确保了查询向量到目标向量的距离在算法 1 中以几何方式逐步减小，因为只移除那些存在绕道边，使得s'yu显著朝目标方向推进的边。因此，随着 $\alpha$ 的增加，图变得更加密集。利用α-RNG属性，确保图的持续可导航性，并保持多个插入和删除操作过程中的稳定召回率。

Algorithms

GreedySearch 与 DiskANN中的算法1相同

Index Build

构建一个可导航图。图的构建通常有两个对立的目标，以最小化搜索复杂度：

1. 使应用到每个基点 $p\in P$ 上的贪心搜索算法在最少的迭代中收敛到 $p$
2. 使所有 $p\in P$ 的最大出度 $R$ 不超过 $R$

从初始图开始，经过以下两步构建算法逐步精炼G，以提高可导航性。

1. 生成候选 ： 对于每个基点 $x_p$，在图 $G$ 上运行算法1（从固定的起始点s开始）来获得 $\mathcal{V},\mathcal{L}$，其中 $\mathcal{L}$ 包含最接近 $p$ 的节点，将它们添加到 $Nout(p)$ 和 $Nin(p)$ 的良好候选，从而提高更新图G中对 $p$ 的可导航性。
2. 边修剪 ： 当节点 $p$ 的出度超过 $R$ 时，修剪算法（如算法3，$\alpha =1$）会从邻接列表中过滤出类似的（或冗余的）边，以确保 $|Nout(p)|\le R$。过程会按距离 $p$ 的增大顺序对其邻居进行排序，如果算法1能够通过 $p^{\prime }$ 从 $p$ 到达 $p^{\prime \prime }$，则可以安全地移除边 $(p,p^{\prime })$）。

Insertion

新的点 $x_p$ 被插入到 FreshVamana 索引中，使用算法 2。它查询当前索引中的点 $p$ 的最近邻，以获取访问集 $V$。

通过在 $V$ 上使用算法 3 的剪枝过程生成 $x_p$ 的候选外部邻居，并在 $p$ 和剪枝后的候选之间添加双向边。如果任何顶点的出度超过 $R$，则可以使用算法 3 将其剪枝至 $R$。

使用基于锁的并发控制来保护对节点 $p$ 的 $N_{out}(p)$ 的访问，从而允许通过多个线程进行高效插入。由于锁的粒度较细，并且锁保持的时间较短，因此插入吞吐量在多线程下接近线性扩展。

Deletion

删除算法算法 4 参考了上文中的 删除策略B，关键特性是使用宽松的 $\alpha$-剪枝算法来保持修改后图的稠密性。具体而言，如果删除点 $p$，则在图中添加边 $(p^{\prime },p^{\prime \prime })$，其中 $(p^{\prime },p)$ 和 $(p,p^{\prime \prime })$ 是有向边。在此过程中，如果 $|N_{out}(p^{\prime })|$ 超过最大出度 $R$，我们使用算法 3 对其进行剪枝，以保持 $\alpha$-RNG 性质。

然而，由于该操作涉及编辑 $p$ 的所有入邻居的邻域，代价可能很大，无法在删除到达时立即处理。FreshVamana 采用了懒删除策略 —— 当一个点 $p$ 被删除时，我们将 $p$ 添加到 DeleteList 中而不改变图。DeleteList 包含所有已删除但仍存在于图中的点。在搜索时，修改后的算法 1 使用 DeleteList 中的节点进行导航，但会从结果集中筛选掉它们。

删除合并。在累积了大量删除操作（例如，索引大小的 1%-10%）后，使用算法 4 批量更新图，以更新有外边的点的邻域，从而将这些删除的节点更新到图中。此操作可以通过前缀和操作来并行化，并通过并行映射操作来本地更新删除节点周围的图。

Summary

Comparison of Vamana with HNSW and NSG

Vamana 与 HNSW 和 NSG 非常相似。这三种算法都在数据集 $P$ 上进行迭代，并使用 GreedySearch(s, $x_p$, 1, L) 和 RobustPrune(p, $V$, $\alpha$, $R$) 的结果来确定 $p$ 的邻居。这些算法之间存在一些重要的差异。

• 最关键的是，HNSW 和 NSG 都没有可调参数 $\alpha$，而且隐式使用 $\alpha =1$。(这是使 Vamana 在图的度数和直径之间实现更好折衷的主要因素)
• 虽然 HNSW 将候选集 $V$ 设置为贪心搜索（GreedySearch(s, $p$, 1, L)）的修剪过程的最终候选结果集，Vamana 和 NSG 将 $V$ 设置为贪心搜索（GreedySearch(s, $p$, 1, L)）访问的所有顶点的集合。从直觉上讲，这个特征有助于 Vamana 和 NSG 添加长距离边，而 HNSW 仅通过添加局部边来构建图的层次结构，进而构建嵌套的图序列。
• NSG 将数据集上的图初始化为近似 $K$-最近邻图，这是一个时间和内存密集型的步骤，而 HNSW 和 Vamana 则有更简单的初始化过程，前者从一个空图开始，Vamana 从一个随机图开始。
• Vamana 进行两次遍历数据集，而 HNSW 和 NSG 只进行一次遍历，动机是基于我们观察到的第二次遍历能提高图的质量。

• DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
• FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search
• Filtered − DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters

SPANN

SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search

Faiss

Faiss的使用说明和相关知识。

Getting Started

全文字数: 1773

阅读时间: 11 minutes

Installing Faiss

# 新建一个干净的环境
conda create -n faiss_env python=3.9 -y
# 切换
conda activate faiss_env

根据需要安装CPU或GPU版本的Faiss

# CPU-only version
conda install -c pytorch faiss-cpu=1.10.0

# GPU(+CPU) version
conda install -c pytorch -c nvidia faiss-gpu=1.10.0

# GPU(+CPU) version with NVIDIA cuVS
conda install -c pytorch -c nvidia -c rapidsai -c conda-forge libnvjitlink faiss-gpu-cuvs=1.10.0

# GPU(+CPU) version using AMD ROCm not yet available

更多关于安装的信息

Basic Usage

import numpy as np
d = 64                           # dimension
nb = 100000                      # database size
nq = 10000                       # nb of queries
np.random.seed(1234)             # make reproducible
xb = np.random.random((nb, d)).astype('float32')
xb[:, 0] += np.arange(nb) / 1000.
xq = np.random.random((nq, d)).astype('float32')
xq[:, 0] += np.arange(nq) / 1000.

import faiss                   # make faiss available
index = faiss.IndexFlatL2(d)   # build the index
print(index.is_trained)
index.add(xb)                  # add vectors to the index
print(index.ntotal)

k = 4                          # we want to see 4 nearest neighbors
D, I = index.search(xb[:5], k) # sanity check
print(I)
print(D)
D, I = index.search(xq, k)     # actual search
print(I[:5])                   # neighbors of the 5 first queries
print(I[-5:])                  # neighbors of the 5 last queries

Getting some data

import numpy as np
d = 64                           # dimension
nb = 100000                      # database size
nq = 10000                       # nb of queries
np.random.seed(1234)             # make reproducible
xb = np.random.random((nb, d)).astype('float32')
xb[:, 0] += np.arange(nb) / 1000.
xq = np.random.random((nq, d)).astype('float32')
xq[:, 0] += np.arange(nq) / 1000.

• d：向量的维度
• nb：数据库的大小
• nq：查询的数量
• xb：数据库向量
• xq：查询向量

xb[:, 0] += np.arange(nb) / 1000.：构造具有一定分布规律的数据，使与i号查询相近的向量就在数据库中i号附近。

Building an index and adding the vectors to it

import faiss                   # make faiss available
index = faiss.IndexFlatL2(d)   # build the index
print(index.is_trained)
index.add(xb)                  # add vectors to the index
print(index.ntotal)

Faiss 是围绕 Index 对象构建的。它封装数据库向量集，并选择性地对它们进行预处理以提高搜索效率。

所有索引在构建时都需要知道它们操作的向量的维度。大多数索引还需要一个训练阶段，以分析向量的分布。对于 IndexFlatL2可以跳过这个操作。

当索引构建并训练完成后，可以对索引执行两个操作：add 和 search 。

要向索引中添加元素，调用 add 并传入 xb。还可以查看索引的两个状态变量：is_trained（指示是否需要训练）和 ntotal（索引中存储的向量数量）。

Searching

k = 4                          # we want to see 4 nearest neighbors
D, I = index.search(xb[:5], k) # sanity check
print(I)
print(D)
D, I = index.search(xq, k)     # actual search
print(I[:5])                   # neighbors of the 5 first queries
print(I[-5:])                  # neighbors of the 5 last queries

为了检查正确性，可以先搜索数据库中的前5个向量，查看其最近邻居是否是自身。

[[  0 393 363  78]
 [  1 555 277 364]
 [  2 304 101  13]
 [  3 173  18 182]
 [  4 288 370 531]]

[[ 0.          7.17517328  7.2076292   7.25116253]
 [ 0.          6.32356453  6.6845808   6.79994535]
 [ 0.          5.79640865  6.39173603  7.28151226]
 [ 0.          7.27790546  7.52798653  7.66284657]
 [ 0.          6.76380348  7.29512024  7.36881447]]

实际搜索输出的结果类似于

[[ 381  207  210  477]
 [ 526  911  142   72]
 [ 838  527 1290  425]
 [ 196  184  164  359]
 [ 526  377  120  425]]

[[ 9900 10500  9309  9831]
 [11055 10895 10812 11321]
 [11353 11103 10164  9787]
 [10571 10664 10632  9638]
 [ 9628  9554 10036  9582]]

由于向量的第一个分量增加了附加值，数据集在 d 维空间的第一轴上被扩散。所以，前几个向量的邻居位于数据集的开头，而大约在 10000 附近的向量的邻居也在数据集的 10000 索引附近。

Faster search (IVF)

...

import faiss

nlist = 100
k = 4
quantizer = faiss.IndexFlatL2(d)  # the other index
# here we specify METRIC_L2, by default it performs inner-product search
index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)
index.train(xb)
index.add(xb)                  # add may be a bit slower as well

D, I = index.search(xq, k)     # actual search
print(I[-5:])                  # neighbors of the 5 last queries
index.nprobe = 10              # default nprobe is 1, try a few more
D, I = index.search(xq, k)
print(I[-5:])                  # neighbors of the 5 last queries

为了加快搜索速度，可以将数据集划分为多个片段。在 $d$ 维空间中定义 Voronoi cells，每个数据库向量都会归属于其中一个细胞。

在搜索时，仅比较查询向量 $x$ 所落入的细胞及其附近的一些相邻细胞中的数据库向量 $y$。

这一过程是通过 IndexIVFFlat 索引实现的。这种类型的索引需要一个训练阶段，该阶段可以在与数据库向量具有相同分布的任何向量集合上执行。在本例中，我们直接使用数据库向量进行训练。

IndexIVFFlat 还需要一个额外的索引，即 quantizer，用于将向量分配到 Voronoi 细胞中。每个细胞由一个centroid定义，确定一个向量属于哪个 Voronoi 细胞的过程，本质上是找到该向量在所有中心点中的最近邻居。这个任务通常由IndexFlatL2索引来完成。

搜索方法有两个关键参数：

• nlist：细胞的总数。
• nprobe：搜索时访问的细胞数量。

搜索时间大致与探测的细胞数量成线性关系，同时还会有一部分由量化过程带来的额外开销。

当nprobe=1时，结果类似于：

[[ 9900 10500  9831 10808]
 [11055 10812 11321 10260]
 [11353 10164 10719 11013]
 [10571 10203 10793 10952]
 [ 9582 10304  9622  9229]]

当nprobe=10时，结果类似于：

[[ 9900 10500  9309  9831]
 [11055 10895 10812 11321]
 [11353 11103 10164  9787]
 [10571 10664 10632  9638]
 [ 9628  9554 10036  9582]]

得到了正确的结果。但是获得完美的结果只是因为该数据有很规律的分布，它在 x 轴上具有很强的分量，这使得它更容易处理。该参数始终是调整结果的速度和准确性之间的权衡的一种方式。设置 nprobe = nlist 给出的结果与暴力搜索相同。

Lower memory footprint (PQ)

...

nlist = 100
m = 8
k = 4
quantizer = faiss.IndexFlatL2(d)  # this remains the same
# 8 specifies that each sub-vector is encoded as 8 bits
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8)                                
index.train(xb)
index.add(xb)

D, I = index.search(xb[:5], k) # sanity check
print(I)
print(D)
index.nprobe = 10              # make comparable with experiment above
D, I = index.search(xq, k)     # search
print(I[-5:])

之前看到的索引，IndexFlatL2 和 IndexIVFFlat，都会存储完整的向量。为了扩展到非常大的数据集，Faiss 提供了基于**乘积量化（Product Quantizer）**的有损压缩变体，以压缩存储的向量。

这些向量仍然存储在Voronoi 单元中，但其大小被减少到可配置的字节数 m（维度 d 必须是 m 的倍数）。

由于向量并不是以完全精确的形式存储的，因此搜索方法返回的距离值也是近似的。

运行结果如下：

[[   0  608  220  228]
 [   1 1063  277  617]
 [   2   46  114  304]
 [   3  791  527  316]
 [   4  159  288  393]]

[[ 1.40704751  6.19361687  6.34912491  6.35771513]
 [ 1.49901485  5.66632462  5.94188499  6.29570007]
 [ 1.63260388  6.04126883  6.18447495  6.26815748]
 [ 1.5356375   6.33165455  6.64519501  6.86594009]
 [ 1.46203303  6.5022912   6.62621975  6.63154221]]

可以看到最近邻被正确找到（即向量本身），但向量与自身的估算距离并不为 0（明显小于它与其他邻居的距离），这是由于有损压缩导致的。

这里将64 个 32 位浮点数压缩到8 字节，压缩比为32。

Simplifying index construction

构建索引可能会变得复杂，Faiss 提供了工厂函数根据字符串来构造索引。

index = faiss.index_factory(d, "IVF100,PQ8")

将 PQ8 替换为 Flat，即可获得 IndexFlat。当对输入向量进行**预处理（如 PCA）**时，工厂函数特别有用。例如，使用字符串 "PCA32,IVF100,Flat" 可以通过 PCA 投影将向量维度降至 32D。

Basics

全文字数: 14

阅读时间: 0 minutes

MetricType and distances