ANN索引
输入“/”快速插入内容
ANN索引
ANN索引
飞书用户77822024年4月7日修改
ANN（Approximate Nearest Neighbor）
brute-force搜索的方式是在全空间进行搜索，为了加快查找的速度，几乎所有的ANN方法都是通过对全空间分割，将其分割成很多小的子空间，在搜索的时候，通过某种方式，快速锁定在某一（几）子空间，然后在该（几个）子空间里做遍历。
大致可以分为三类：
•
基于树：KD树、Annoy
•
基于哈希：LSH（locality sensitive hash）
•
基于矢量量化：PQ（Product Quantization）
PQ乘积量化
核心思想还是聚类。
1. 向量分段
假设有1000个128维的向量，将其做8等分，每一段向量的维度变成16，形成8个子空间。
2. 训练
对每个子空间进行K-means聚类，聚类中心的个数为K（K=256）。训练完成后会形成一个码表，对每一个聚类中心点都赋予一个1-256的整数值。于是我们会得到8*256个聚类中心
3. 编码
计算每个子空间与对应子空间的每个聚类中心的距离，选择距离最近的向量对应的码表ID来表示原始子空间的向量，这样原始向量就被encoding成8维的向量。
4. 在线检索
对于新来的查询query向量，也是同样先拆分成8等分，接着计算query每个分段与之前预训练好的对应分段的簇心的距离。
最后计算库里向量和query向量的距离。比如库里某一个向量量化成了[124, 56, 132, 222], 那么首先查表得到查询向量第一段子向量与其ID为124的簇心的距离，然后再查表得到查询向量第二段子向量与其ID为56的簇心的距离......最后就可以得到四个距离d1、d2、d3、d4，查询向量跟库里向量的距离d = d1+d2+d3+d4。