推荐tanoku · 2024-10
“SPANN is a hybrid graph/tree algorithm that does a fantastic job of scaling larger-than-RAM indexes”
推荐 SPANN,称这种图/树混合算法能很好扩展超出内存的索引
内存加 SSD 混合索引,十亿级向量检索比 DiskANN 快一倍
SPANN 是一个沿用倒排索引思路的内存-磁盘混合 ANNS 系统:把各 posting list 的中心点放在内存,大的 posting list 放在 SSD。建索引时用层次化平衡聚类均衡 posting list 长度,并把聚类闭包内的点补进列表;搜索时用查询感知策略动态裁剪不必要的 posting list。在三个十亿级数据集上,相同内存开销下达到 90% 召回的速度约为 DiskANN 的 2 倍。
评论者把它列为能扩展到超出内存规模的向量索引方案,常与其他向量检索论文放在一起推荐。
先熟悉十亿级向量检索的两条主线:基于量化的倒排索引与基于图的索引,再看 SPANN 如何把它们放到内存加 SSD 上。
图索引的代表,SPANN 对比与借鉴的内存索引方案
读理解分层可导航小世界图的构造与搜索过程,以及它对内存的需求
倒排索引加乘积量化的十亿级检索基线,SPANN 沿用倒排思路
读读倒排文件(IVF)与乘积量化的部分,看规模化瓶颈在哪里
目标论文:内存存质心、磁盘存大 posting list 的混合索引
读抓住质心常驻内存、posting list 落盘以及减少磁盘访问的设计
“SPANN is a hybrid graph/tree algorithm that does a fantastic job of scaling larger-than-RAM indexes”
“Not strictly google but microsoft/bing too, here's the top ones from my notes:”