相似性搜索概述

Embedding维度足够多，理论上可以将所有Vector区分开，即高维特征空间中对应一个点，世间万物都可以用Vector坐标表示。

向量数据库为向量数据提供专门的存储和索引机制。向量被存储为高维空间中的点，DB会为这些点建立索引。索引结构和算法有树、图、哈希等，索引结构让DB可高效进行相似搜索。每次搜索通过相似性度量评价相似度，从而得到向量查询结果。

高效的搜索算法有很多，其主要思想是通过两种方式提高搜索效率。

1.按索引使用数据结构:将向量组织成基于树、图等结构来缩小搜索范围。

2.减少向量大小:通过降维的方式(量化)表示向量值的长度。

搜索算法：按数据结构分类

基于哈希索引

高维向量映射到低维空间或低维哈希码:尽可能保持原始相似性;

数据库中向量被多次哈希:以确保相似点更有可能发生冲突(与传统哈希相反，其目标最大限度减少冲突);

通过哈希表或者倒排索引来存储和检索:在索引过程，查询点也使用与索引过程中相同哈希函数，由于相似点被分配到相同哈希桶，因此检索速度非常快;

典型算法:LSH 局部敏感哈希（Local Sensitive Hashing）

优缺点:优点扩展到大量数据时速度非常快，缺点是准确性一般。

基于树的索引

建立树结构:把高维空间划分成若干个子空间或者聚类中心然后用树形结构来存储和检索。

索引算法:通过二又搜索树算法搜索，相似数据易在同一子树从而更快地发现近似邻居。

特点:基于精确距离计算 or 近似距离计算,

优缺点:优点对低维数据准确率较高;缺点无法充分捕获数据复杂性，高维数据准确率较低。

基于图的索引（最多用）

数据结构:图中节点表示向量数据，边表示数据间相似

构图方式:相似数据点更有可能通过边连接，搜索算法以有效方式遍历图找到相似近邻。

优缺点:优点能够在高维数据中找到近似的近邻，从而提高搜索性能。缺点是构图方式复杂，影响内存效率。

倒排文件索引（第二多）

倒排文件索引(IVF):将向量空间划分为多格 Voronoi单元，单元以与聚类相同的方式，通过建立倒排索引表，以减少搜索空间。

优缺点:优点是有助于设计快速缩小感兴趣相似区域的搜索算法;缺点是对于海量数据，细分向量空间会变慢。

改进点:IF 常与乘积量化(PQ)等量化方法结合，以提高性能。

搜索算法：按照量化压缩分类

索引的本质是什么？常见索引:对直接存储的向量，使用特殊数据结构设计的算法加快索引效率。具体算法:查询向量时，与数据库中每个向量进行的比较。索引本质:减少了时间搜索效率，返回 TOP-K 最近邻向量。每一次相似性对比所需时间随数据维度增加而增加。

减少向量大小:通过降维的方式(量化)表示向量值的长度。

实现的方式?

1.索引基础向量被分解为较少字节组成的块，以减少搜索期间的内存消耗和计算成本。

2.代价是什么?

通过压缩提高索引效率，代价是降低检索准确性。

扁平化索引Flat Indexing

Flat Indexing:使用 ANN、IVF 或 HNSW 等索引，直接计算査询向量与 DB 中向量之间距离。为了将其与量化变体区分开来，使用这种方式使用时通常称为 IF-Flat、HNSW-Flat 等。

量化索引 Quantized Indexing

量化索引:将索引算法(IVF、HNSW)与量化方法相结合，以减少内存占用并加快索引速度量化分类:标量量化(Scalar Quantization,SQ)或乘积量化(Product Quantization，PO)。

标量量化SQ：将向量对称划分为包含每个维度的最小值和最大值的容器，将向量中的浮点数转换为整数。比如神经网络模型对权重参数的量化。

乘积量化PQ：考虑沿每个向量维度值分布，执行压缩和数据缩减。将较大维度向量空间分解为较小维度子空间的笛卡尔积。

相似性搜索算法

除暴力搜索能精确索引到近邻，所有搜索算法只能在性能、召回率、内存三者进行权衡。