SPANN：高效的十亿级近似最近邻搜索 (arxiv.org)

SPANN是一个高效的内存-磁盘混合近似最近邻搜索系统，它采用倒排索引方法，将posting lists的中心点存储在内存中，而将大型posting lists存储在磁盘中。SPANN通过减少磁盘访问次数和检索高质量的posting lists来保证磁盘访问效率和高召回率。在索引构建阶段，它采用分层平衡聚类算法来平衡posting lists的长度，并通过添加相应聚类中点的闭包来扩充posting lists。在搜索阶段，它使用query-aware方案动态修剪不必要的posting lists的访问。实验结果表明，SPANN比当前最先进的ANNS解决方案DiskANN快2倍，在三个十亿级数据集上达到相同的召回率90%，内存成本相同。