论文笔记：DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
Authors: Devvrit, Suhas Jayaram Subramanya Created: October 4, 2022 9:45 PM PublishedAt: NIPS URL: https://suhasjs.github.io/files/diskann_neurips19.pdf Year: 2019 Summary DiskANN使用64G RAM来索引和服务100维左右的10亿数据集，95%以上的1-recall@1的时延在5ms以内。 提出Vamana图算法，直径比NSG和HNSW更小。 将点加入重叠聚类，每个聚类构建Vamana索引，然后通过合并边来实现图合并，和所有数据点构建单一索引的搜索性能相近。 Strength 通过将点加入重叠聚类，构建的图简单合并也有不错的效果。 Weakness 图索引用在SSD上，直觉上太多随机访问效果应该会打折扣，虽然Vamana做了优化。后续的SPANN通过层次均衡聚类构建倒排索引，性能超过了DiskANN。 索引中需要同时存原始向量和PQ压缩向量，应该磁盘使用会比较大。 性能数据只比较了1-recall@1，很多系统在召回时不止召回一个。 Take Away 图索引合并。 ...