ANN近似最近邻检索（搜索和推荐）_ann检索和 相似度

ANN之KD-Tree

PQ量化和倒排 

NSW和HNSW（基于图的搜索结构）

一、 基于倒排的检索算法

基于倒排的搜索算法，思路主要是快速缩小筛选范围。

例如有这样一个场景：现在有100w条数据，作为数据库，每条数据对应一个特征向量，给定一个查询特征向量，去数据库里查找最相似的100条数据返回。

如果暴力计算则会花费很长时间，基于倒排索引的思路是这样，把这100w条数据，进行聚类，例如聚成4000个类别，每个类别里的数据，都有一定的相关性，也就是同一个类别里的数据相似度很高。然后计算出每个类别的中心向量，即有4000个中心向量，此时计算查询向量和这4000个中心向量的距离，取出前100个（具体数字自定）类别，再从这100个类别里暴力查找，相当于把100w的查找范围缩小到约100*250个。

二、PQ乘积量化

相当于对原始特征向量进行简化，类似于模拟信号数字化采样，会造成一定的精度损失，但大大减小了存储空间。

三、HNSW图检索

NSW把特征向量构建成一张无向图结构，每个节点是一个特征向量，其内保存与之最相邻的K个特征向量的编号，当把查询向量放入图结构中，就可以通过寻找与查询向量最近的节点，进而确定与查询向量最相近的topN个结果。