本文尝试梳理了一些高维向量相似性搜索中的核心索引算法，包括 IVF、HNSW、PQ 和 ScaNN 等。整理了各种相似性度量方法（欧氏距离、余弦距离、内积距离等），探讨了从暴力搜索到高效近似搜索的算法演进过程，并尝试理解了 Google ScaNN 算法中的分数感知量化、各向异性损失和 4-bit SIMD 优化等前沿技术。此外，也涵盖了向量搜索中的过滤策略（Pre-filter 和 Post-filter）以及混合查询优化方案的相关内容。

ScaNN演示

向量索引算法概览

Similarity Metrics

欧式距离 L2，表示向量间的绝对距离
点积距离 Inner Product，计算速度快，兼顾长度和方向
A · B = |A| cos a * |B|
余弦距离 Cos，表示向量的方向的差异，不包含长度信息
- NLP 中屏蔽长文本与短文本的长度差异
曼哈顿距离 L1，移动只能沿着坐标轴方向运行（比如二维空间中只能沿着水平或竖直方向）
- 栅格地图、图像处理、编码压缩（高维空间下比 L2 更稳定）

算法

开源数据库
Flat 暴力搜索能够满足 100% Recall

IVF Flat

K-Mean 聚类

K-Means聚类示意图

code

import numpy as np

# 假设我们有一些高维向量数据集
original_vectors = np.array([
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
    [2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
    [2, 4, 6, 8, 10, 12, 14, 16, 18, 20],
    [-1, -2, -3, -4, -5, -6, -7, -8, -9, -10],
    [1, -2, 3, -4, 5, -6, 7, -8, 9, -10],
    [-1, 2, -3, 4, -5, 6, -7, 8, -9, 10]])

def kmeans(data, k=2, max_iters=10):
    # Step 1: 初始化k个质心
    idxs = np.random.choice(data.shape[0], k, replace=False)
    centroids = data[idxs]
    print(f'default_centroids: {centroids}')

    for _ in range(max_iters):
        # Step 2: 计算每个数据点到每个质心的距离
        distances = np.sqrt(((
            data[:, np.newaxis, :] - centroids)**2).sum(axis=2))
        # 分配每个数据点到最近的质心
        closest_idxs = np.argmin(distances, axis=1)
        print(f'cloest_idxs: {closest_idxs}')
        # Step 3: 计算新的质心
        new_centroids = np.array([
            data[closest_idxs == i].mean(axis=0) for i in range(k)])
        print(f'new_centroids: {new_centroids}')
        # 检查质心是否发生变化
        if np.all(centroids == new_centroids):
            break

        centroids = new_centroids
    return centroids

kmeans(original_vectors, 2)

Invert file
- 将质心作文件倒排索引，相对于质心是向量的索引，倒排索引是质心的索引。隔一段时间需要更新一次质心，保证检索的准确性。
- parameter：
  - query 在簇的边缘的问题，搜索参数 probe 指定检索的质心的数量
    - 所检测的质心数量越多，近邻检索结果越精准（Recall 更高）
  - 聚簇参数 num of clusters 指定构建时质心的数量
    - a good place to start is rows / 1000 for up to 1M rows and sqrt(rows) for over 1M rows

LSH（Locality Sensitive Hashing）

LSH算法示意图

高维空间问题
- Random Projection 随机投影
  - 将高位空间数据投影到低维空间
    - 提高计算效率，但精度较低

HNSW（Hierarchical Navigable Small World）

SW，小世界理论将所有的点用“图”的方式相连，至多需要六步即可到达最远点。–> 退化到暴力搜索
NSW，可导航小世界，刻意的构建长边和短边，长边增加检索速度，短边增加检索精度。
HNSW，多层级可导航小世界，建立多层的小世界，每一层作为下一层的索引，长边在顶层，短边在底层。（像跳表；空间换时间）
核心思想是构建一个邻近图，其中图中的每个向量根据以下三个特征连接到其他若干向量：
- 向量之间的距离
- 在插入过程中每一步搜索时考虑的最接近向量候选者的最大数量（EF_CONSTRUCTION）
- 每个向量允许的最大连接数
parameter：
- m - 每层的最大连接数 the max number of connections per layer (16 by default)，决定召回速度 & 内存占用
- ef_construction - 构建时的候选集数量 the size of the dynamic candidate list for constructing the graph (64 by default)，决定构建精度 & 插入速度
- ef_search，搜索时的候选集数量，决定召回精度 & 召回数
HNSW vs IVFFlat
- build time - more
- size - more
- speed - 15x
- sensitive to index updates - less

PQ（Product Quantization）

向量量化 Vector Quantization：向量量化是将连续的向量空间离散化的过程，目的是减少表示向量所需的数据量。它是通过将输入向量映射到一组预定义的代表值（称为“质心”）来实现的。→ 聚类

乘积量化 Product Quantization：乘积量化是一种特殊的向量量化方法，它将高维向量分解为多个低维子向量，然后对这些子向量进行独立的向量量化。利用了高维空间中数据分布的局部性原理。

索引构建步骤

子空间划分：
- 将 D 维的输入向量空间划分为 m 个低维子空间，每个子空间的维度为 D* = D / m。
子量化器学习：
- 对每个子空间，使用一个独立的量化器进行量化。每个量化器有 k 个质心。
向量量化：
- 每个子向量在相应的子空间中被量化。量化过程是将子向量直接映射成最近的质心。
编码表示：
- 每个子向量的量化结果是一个索引，表示它所属的质心。整个向量的表示是这些子空间量化索引的组合，形成一个较短的码。

PQ乘积量化示意图

128 维向量

⇒ 划分为 16 维子向量 * 8个

⇒ 每个子向量聚类 256 个质心

⇒ 表示为 8bits 整数 id * 8个

优势

减少存储需求：由于使用了多个小的码本而不是一个大的码本，减少了存储质心所需的内存。
提高搜索效率：在搜索过程中，可以通过预先计算 query 子向量与所有数据库子质心的距离，将 cpu 对距离的计算转化为查表。
保持精度：仍然能够提供相对准确的最近邻搜索结果。

搜索步骤

两种近似距离计算方法：
- 非对称距离计算（ADC）：只有数据库向量被量化，查询向量保持原样，并计算查询向量与量化后的数据库向量之间的距离。
- 对称距离计算（SDC）：查询向量和数据库向量都被量化，然后计算它们量化表示之间的距离。

计算query向量与数据库向量距离的过程

计算 query 向量与各数据库向量距离的过程

query 向量需要与每个数据库量化向量对比距离，但计算量已经远小于 Flat 暴力搜索。还有没有办法再次优化呢？

倒排文件结构（IVF-PQ）：通过使用倒排文件，配个较粗粒度的原始维度聚类，聚类出较小数量的质心。筛选出与查询向量相似的数据库向量子集，而不是整个数据库。
- PQ 子向量数量越大，总共需要的 IVF 分区数量越少（效率&精度）

ScaNN

PQ in ScaNN

分数感知 Score-aware quantization loss

传统 PQ 将每个子向量用质心表示，并没有考虑 query 的影响。

目标：定义 query 与原始向量间距离 和 query 与量化后的向量间的距离 的差距为量化误差。要求尽可能地降低量化误差。

附加条件：

距离 query 更近的数据库向量对召回结果的影响更大。
内积 inner product 更大的，距离更近。

减小这部分的向量的量化误差，根据内积值对量化误差进行加权，给予具有更高内积的查询和数据库点对更大的权重。

分数感知量化损失

各向异性 anisotropic loss

各向异性损失示意图1

各向异性损失示意图2

In the above diagrams, ellipses denote contours of equal loss. In anisotropic vector quantization, error parallel to the original data point x is penalized more.

平行量化误差 r∥(x,x^) 是影响内积值的误差 ，对结果的影响更大，应给予更严厉的惩罚。

垂直量化误差 r⊥(x,x^) 的权重应该尽量减小。

但在构建索引的阶段，并不知道未来的 query 是什么，无法利用 query 信息。

4 bit SIMD

4-bit SIMD优化

将 PQ 过程压缩的足够小，以至于更够被放到 CPU 寄存器里。将读内存操作转化成 CPU 计算操作（SIMD-shuffle）。

普通 PQ 子向量: 256 * 32bit(float) = 8192 bit

优化方法：

构建索引时，只聚类 16 个质心
计算距离时，对 float 距离做进一步的标量量化 Scalar Quantization，将其表示为 uint8
- 将所有的距离分布切分为 256 个区域 ⇒ 8bit

4bit PQ 子向量: 16(4bit) * 8bit(uint) = 128 bit

AVX2 寄存器 n1 系列 CPU，256 bit 位宽。

AVX2寄存器优化

parameter：
- approximateNeighborsCount: 在 reordering 步骤之前查找的近邻数 The default number of neighbors to find through approximate search before exact reordering is performed. Exact reordering is a procedure where results returned by an approximate search algorithm are reordered using a more expensive distance computation.
- fractionLeafNodesToSearch: 默认的搜索的叶节点百分比 The default fraction of leaf nodes that any query may be searched. Must be in range 0.0 - 1.0, exclusive. The default value is 0.05 if not set.
- leafNodeEmbeddingCount: 单叶节点的向量数 Number of embeddings on each leaf node. The default value is 1000 if not set.
SOAR