Milvus向量数据库03-搜索理论

1-ANN搜索

通过 k-最近邻（kNN）搜索可以找到一个查询向量的 k 个最近向量。kNN 算法将查询向量与向量空间中的每个向量进行比较，直到出现 k 个完全匹配的结果。尽管 kNN 搜索可以确保准确性，但十分耗时。尤其是数据量大，向量维度高时，耗时更久。

相比之下，近似最近邻（ANN）搜索耗时更短。ANN 算法会预先构建索引。选择不同的索引算法会影响搜索速度、内存使用情况和准确性。各种类型的 ANN 索引算法主要分为 2 种思路：缩小搜索范围和将高维向量空间分解为低维子空间。

缩小搜索范围是指仅在可能性较高的候选项子集中对比查询向量，从而缩短搜索时间。但是可能结果不可避免地会返回不相关的向量。为确定一个向量是否在子集中，需要构建索引结构来对向量进行排序。

通常，有 3 种索引结构：图索引、树索引、哈希索引。

HNSW：图索引算法

HNSW：图索引算法链接

Hierarchical Navigable Small World（HNSW）算法通过创建多层接近图（Proximity graph）来索引向量空间。HNSW 算法在每 1 层中，都会在向量（或顶点）之间绘制连接相邻点的边，以形成单层Proximity graph，并最终形成多层图。底层包含所有向量及边。越上面的层，包含的向量和边越少。

创建分层 Proximity graph 后，搜索步骤如下：

在顶层找到一个向量作为入口点。
沿着可用的边逐渐移动到最近的向量。
一旦确定了顶层的最近向量，使用较低层的相同向量作为入口点，在该层中找到其最近邻。
重复上述步骤，直到找到底层的最近向量。

LSH：哈希索引算法

LSH：哈希索引算法链接

局部敏感哈希（LSH）算法的基本思想为空间域转换。LSH 算法通过使用各种哈希函数将任意长度的数据映射为固定长度的值作为哈希，将这些哈希收集到哈希桶中，并将已经哈希到相同值的向量标记为候选对。

RRMybZeKQoGgQRx6kSNcvwxsnre

DiskANN：基于 Vamana 图的磁盘索引算法

DiskANN：基于 Vamana 图的磁盘索引算法链接

不同于 HNSW 算法构建分层图，Vamana 索引过程相对简单：

初始化随机图；
先定位全局质心并确定最近点来找到导航点。使用全局比较以最小化平均搜索半径。
使用初始化的随机近邻图和从步骤2开始的搜索起点执行近似最近邻搜索。使用搜索路径上的所有点作为候选近邻集，并采用 alpha = 1 的边缘修剪策略以减少搜索半径。
将 alpha 值调整为 alpha> 1（文献推荐将数值设置为 1.2）后，重复步骤 3 以优化图质量和召回率。

索引准备就绪后，搜索步骤如下：

加载相关数据，包括查询数据集、PQ 中心点数据、Codebook 数据、搜索起点和索引元数据。
使用索引数据集执行 cached_beam_search，计算每个点的访问次数，并缓存具有最高访问频率的 num_nodes_to_cache 个点。
默认情况下执行 WARMUP 操作，使用示例数据集执行 cached_beam_search。
对于给定参数 L，使用查询集执行 cached_beam_search，并输出召回率和QPS等统计信息。查询时间不包括预热和热点数据统计信息。

更多详情，请阅读《DiskANN：十亿规模数据集上高召回高 QPS 的 ANNS 单机方案》。

2-相似度类型

在度量向量相似性时，相似度类型发挥着关键作用。选择恰当的相似度类型可以极大地提升分类与聚类的效果。

目前，Zilliz Cloud 支持以下相似度类型：欧氏距离（L2）、内积（IP）、余弦相似度（COSINE）、JACCARD ^(Beta) 和 HAMMING ^(Beta)。

下表总结了不同字段类型与其对应的相似度类型的映射关系。

| 字段类型                | 维度范围       | 支持的相似度类型       | 默认相似度类型   |
|-----------------------|------------|--------------------|--------------|
| FLOAT_VECTOR          | 2-32,768   | Cosine, L2, IP    | Cosine       |
| FLOAT16_VECTOR (Beta) | 2-32,768   | Cosine, L2, IP    | Cosine       |
| BFLOAT16_VECTOR (Beta)| 2-32,768   | Cosine, L2, IP    | Cosine       |
| SPARSE_FLOAT_VECTOR (Beta) | 无需指定维度 | IP                | IP           |
| BINARY_VECTOR (Beta)  | 8-32,768*8 | HAMMING (Beta), JACCARD (Beta) | HAMMING (Beta) |

下表展示了使用不同的相似度类型，其度量值的特点及取值范围。

相似度类型	特点	取值范围
L2	较小的L2距离表示更高的相似性。	[0, ∞)
IP	较大的IP距离表示更高的相似性。	[-1, 1]
COSINE	较大的cosine值表示更高的相似性。	[-1, 1]
JACCARD	较小的Jaccard距离表示更高的相似性。	[0, 1]
HAMMING	较小的Hamming距离表示更高的相似性。	[0, dim(vector)]

欧氏距离（L2）

欧氏距离（L2）链接

欧氏距离主要是用来计算连接两点的线段的实际长度。

其计算公式如下：

HhIdbxRd7oGoDrxCGh6cBIX9ncf

其中，a = (a₀, a₁,…, a_n-1) 和 b = (b₀, b₁,…, b_n-1) 表示 n 维欧氏空间中的两个点。

L2 是最普遍的距离度量方法，在处理连续性数据时尤为有效。

📘说明

在选择 L2 作为度量标准时，Zilliz Cloud 仅计算开方之前的数值。

内积（IP）

内积（IP）链接

两个 Embedding 向量间的 IP 距离可按以下方式定义：

LXkCbWG6IoCXSux5uc9cZn28nnc

当处理未归一化的数据或关注数据的大小和方向时，内积尤为重要。

📘说明

使用 IP 计算 Embedding 向量间的相似度时，须先对 Embedding 向量进行归一化。之后，内积即可等同于余弦相似度。

例如，Embedding 向量 X 归一化为 X’：

两个 Embedding 向量间的关联度如下所示：

余弦相似度（COSINE）

余弦相似度（COSINE）链接

余弦相似度是通过计算两组向量之间的夹角余弦来衡量它们的相似度。可以把这两组向量想象为从同一起点（如 [0,0,…]）出发，但朝向不同的线段。

计算两组向量 A = (a₀, a₁,…, a_n-1) 和 B = (b₀, b₁,…, b_n-1) 之间的余弦相似度，可使用以下公式：

M6C6b2W8toduLSxfV6ac3ZcDnQh

余弦相似度的值总是介于 [-1, 1] 之间。比如，两个向量的夹角越接近 0 度，余弦相似度越接近 1；两个向量的夹角为 90 度时，其相似度为 0；两个向量的夹角越接近 180 度，两个向量相似度越接近 -1。余弦值越大，表示两向量之间的夹角越小，意味着它们越相似。

通过 1 减去两向量间的余弦相似度，可以得到它们之间的余弦距离。

📘说明

该相似度类型目前还在测试阶段。升级您的集群至 Beta 版即可体验 COSINE 相似度类型。

JACCARD 距离 (Beta)

JACCARD 距离 (Beta)链接

JACCARD 相似系数用于衡量两个样本集之间的相似度，其定义是两个集合交集的元素数量除以它们并集的元素数量。该系数仅适用于有限样本集。

JACCARD 距离用于衡量数据集之间的不相似度，其计算方法是 1 减去 JACCARD 相似系数。对于二进制变量，JACCARD 距离等同于 Tanimoto 系数。

📘说明

该相似度类型目前仅适用于已升级到 Beta 版的 Zilliz Cloud 集群。

HAMMING 距离 (Beta)

HAMMING 距离 (Beta)链接

HAMMING 距离用于测量二进制数据字符串。两个等长字符串之间的距离是它们在不同比特位上的数量。

例如，假设有两个字符串，1101 1001 和 1001 1101。 11011001 ⊕ 10011101 = 01000100。由于其中有两个 1，因此 HAMMING 距离 d (11011001, 10011101) = 2。

📘说明

该相似度类型目前仅适用于已升级到 Beta 版的 Zilliz Cloud 集群。

3-一致性水平

在分布式数据库中，一致性水平确保在读写操作期间，每个节点或副本都能获取到相同的数据。Zilliz Cloud 提供 3 种一致性级别：Strong、Bounded 和 Eventually。Zilliz Cloud 默认采用的一致性水平为 Bounded。

PACELC 定理：权衡一致性、可用性、时延

PACELC 定理：权衡一致性、可用性、时延链接

PACELC 定理是 CAP 定理的延伸，在分布式数据库中，用户需要在可用性和一致性之间做选择，否则，就在延迟和一致性之间做选择。虽然高一致性保证了数据的准确性，但其代价是更长的搜索延时。相反，低一致性保证了更快的搜索速度，但可能会牺牲数据准确性。因此，您需要根据具体的使用案例场景选择合适的一致性水平。

强一致性（Strong）

强一致性（Strong）是最严格的级别，确保用户始终读取最新版本的数据，提供最高的数据准确性。但是，采用 Strong 等级一致性可能导致搜索延迟增加。

Strong 一致性水平最适用于功能测试和在线金融系统等对于数据准确性有着极高要求的场景。
有限过期一致性（Bounded）

有限过期一致性（Bounded）顾名思义，允许数据在一小段时间内不一致，但整体而言数据还是一致的。Bounded 能够平衡延时和数据准确性。

Bounded 适用于视频推荐平台等系统，偶尔的数据不一致不会严重影响系统性能。
最终一致性（Eventually）

最终一致性（Eventually）是最宽松的级别，允许数据不一致，但最终随着时间推移收敛到数据一致的状态。Eventually 不会严格遵照数据读写顺序。

Eventually 通过牺牲即时一致性来提升搜索性能，因此用于追求搜索速度而非即时数据准确性的场景，如产品评论展示系统等。

利用保证时间戳实现一致性

利用保证时间戳实现一致性链接

Zilliz Cloud 通过保证时间戳（GuaranteeTs）实现不同的一致性水平。保证时间戳主要用于控制查询节点，需要等到 GuaranteeTs 之前的所有都可查看后，才能开始执行搜索或查询。不同一致性级别，GuaranteeTs 值也不同：

**强一致性（Strong）：**GuaranteeTs 设为系统最新时间戳，QueryNodes 需要等待 ServiceTime 推进到当前最新时间戳才能执行该 Search 请求。
**最终一致性（Eventually）：**GuaranteeTs 设为一个特别小的值（比如说设为 1），跳过一致性检查，立刻在当前已有数据上执行 Search 查询。
**有限过期一致性（Bounded）：**GuaranteeTs 是一个比系统最新时间稍旧的时间，在可容忍范围内可以立刻执行查询。

如需了解一致性和保证时间戳的实现机制，请阅读本文。

4-Reranking重排序

Zilliz Cloud 通过 hybrid_search() API，实现了 hybrid search 功能，结合了复杂的 reranking 策略，以优化多个 AnnSearchRequest 对象的搜索结果。本文将详细介绍 reranking 机制，阐述其重要性以及在 Milvus 中实施不同 reranking 策略的方法。

Reranking 是 hybrid search 中的一个关键步骤，它整合了基于多个向量字段的检索结果，确保最终输出结果的相关性和准确性。目前，Zilliz Cloud 支持以下 reranking 策略：

WeightedRanker 分数加权平均算法的核心思想是对多个召回路的输出结果的分数进行加权平均计算，以得到一个综合的结果，其中不同召回路的贡献可由预设的权重来决定。例如，在多模态搜索中，文本描述可能被认为比图像中的颜色分布更重要。

from pymilvus import WeightedRanker

# Use WeightedRanker to combine results with specified weights
rerank = WeightedRanker(0.8, 0.8, 0.7)

RRF（Ranked Retrieval Fusion，排序检索融合）是一种常见的检索融合算法，此方法侧重于使用排名信息，将每个系统的排名结果加权并合并，以提高整体检索的相关性和效果。当希望对所有向量字段给予平等考虑，或当字段的相对重要性不确定时，通常采用此策略。

5-知识总结

以下是文章内容要点的思维导图：

graph TD
    A --> B[ANN搜索]
    A --> C[相似度类型]
    A --> D[一致性水平]
    A --> E[Reranking重排序]

    B --> B1[k-最近邻（kNN）搜索]
    B --> B2[近似最近邻（ANN）搜索]
    B --> B3[索引算法]
    B --> B4[HNSW：图索引算法]
    B --> B5[LSH：哈希索引算法]
    B --> B6[DiskANN：磁盘索引算法]

    C --> C1[L2]
    C --> C2[IP]
    C --> C3[COSINE]
    C --> C4[JACCARD]
    C --> C5[HAMMING]

    D --> D1[一致性水平]
    D --> D2[PACELC定理]
    D --> D3[强一致性-Strong]
    D --> D4[有限过期一致性-Bounded]
    D --> D5[最终一致性-Eventually]
    D --> D6[保证时间戳实现一致性]

    E --> E1[Reranking重排序]
    E --> E2[hybrid_search API]
    E --> E3[WeightedRanker]
    E --> E4[RRF-Ranked Retrieval Fusion]

详细知识点如下：