近似搜索

[[KD 树]] #card

• 一次搜索都把空间分成两份，然后在其中继续搜索。

• 在k-d树中，并不能保证沿着某一个分支下去就能得到所有结果，

• 因此当特征维度升高之后，复杂度也会急剧升高，在现在的搜索方案中一般不会选择。

哈希方法，#card

• 具体说是局部敏感哈希(Locality Sensitive Hashing,LSH)，

• 目标是把两个距离较近的高维向量经过哈希映射到一起。

量化方法，是本节的重点之一，#card

• 先把一些点“捏”成一个团，它们要么一起被选，要么一起被丢弃。

• 向量量化方法在近几年的主流都是基于乘积量化(Product Quantization,PQ)方法[插图]的，也是开源库[[Faiss]]的实现方法。

基于图的方法，注意这里的“图”和上一节的“图”的区别。在上一节中即使也叫“图”​，它主要是一种训练嵌入的方法，这里的“图”是真正按照数据结构本身来搜索的。