精确 k 近邻要对全表算距离——规模两千万、维度 768。ANN 为何只碰一小撮仍能给出几乎最近的邻居?图方法、分桶、压缩各自省掉哪一段运算?
题目
精确 k 近邻要对全表算距离——规模两千万、维度 768。ANN 为何只碰一小撮仍能给出几乎最近的邻居?图方法、分桶、压缩各自省掉哪一段运算?
参考答案
点击展开参考答案
- 精确 k 近邻代价约 (O(nd)),两千万 × 768 次乘加对单次在线查询通常不可接受。
- 近似近邻先在离线把空间组织好,让查询沿着更可能近的路径走,只对候选算精确或近似距离。
- 图方法把点连到近邻再贪心爬;分桶方法先聚类,查询只进最近的若干桶;压缩把每次距离从 (d) 维浮点换成查表。
- 牺牲的是召回:真正的第 k 近邻可能根本没被碰到。
- 两千万 × 768 × 4 字节大约 60GB 裸向量,全扫既是计算问题也是带宽问题。
- HNSW 一类多层图:上层边少、步子大,下层边密、局部精修,一次查询常只碰几千到几万条边,
efSearch控制候选有多宽。