分享
ANN索引
输入“/”快速插入内容
ANN索引
飞书用户7782
2024年4月7日修改
https://zhuanlan.zhihu.com/p/447343011
ANN(Approximate Nearest Neighbor)
brute-force搜索的方式是在全空间进行搜索,为了加快查找的速度,几乎所有的ANN方法都是通过对全空间分割,将其分割成很多小的子空间,在搜索的时候,通过某种方式,快速锁定在某一(几)子空间,然后在该(几个)子空间里做遍历。
大致可以分为三类:
•
基于树:KD树、Annoy
•
基于哈希:LSH(locality sensitive hash)
•
基于矢量量化:PQ(Product Quantization)
PQ乘积量化
•
https://towardsdatascience.com/product-quantization-for-similarity-search-2f1f67c5fddd
•
https://mp.weixin.qq.com/s/EtnTDkaXwVNMXKagIw9JCg
核心思想还是聚类。
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。