近似最近邻搜索(ANN)

定义

近似最近邻搜索(Approximate Nearest Neighbor,ANN)指在高维向量集合中快速找到与查询向量"足够近"而不保证严格最近的邻居。由于维度灾难使精确搜索在高维下退化为线性扫描,ANN 以可控的精度损失换取数量级的加速。

主要方法

四大流派:基于图(HNSW、NSG)沿近邻图贪心游走;基于量化(PQ 乘积量化、IVF 倒排文件)压缩向量并粗筛;基于哈希(LSH)将相近向量映射入同桶;基于树(Annoy 的随机投影树、KD 树)划分空间。工业系统常组合使用,如 IVF+PQ。

应用

ANN 是向量数据库、语义搜索、RAG 召回、人脸识别、推荐系统与以图搜图的共同底层,Faiss、ScaNN、hnswlib 等库提供了成熟实现,并有 ann-benchmarks 等公开基准比较各算法。

权衡

核心权衡是召回率、延迟、内存与构建时间四者不可兼得,需按场景选型调参。