按年被提到
20212024 · 2 次2026
系统、数据库与网络›数据库与向量检索·arXiv:2111.08566 · cs.DB

SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search

SPANN:高效的十亿级近似最近邻搜索
Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, Jingdong Wang · 2021

内存加 SSD 混合索引,十亿级向量检索比 DiskANN 快一倍

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 3 人首次 2024-10-22 · 最近 2026-03-17
3不同的人
3活跃月份
3讨论串
29被引(OpenAlex)

SPANN 是一个沿用倒排索引思路的内存-磁盘混合 ANNS 系统:把各 posting list 的中心点放在内存,大的 posting list 放在 SSD。建索引时用层次化平衡聚类均衡 posting list 长度,并把聚类闭包内的点补进列表;搜索时用查询感知策略动态裁剪不必要的 posting list。在三个十亿级数据集上,相同内存开销下达到 90% 召回的速度约为 DiskANN 的 2 倍。

HN 为什么提它

评论者把它列为能扩展到超出内存规模的向量索引方案,常与其他向量检索论文放在一起推荐。

方法难度 3 / 5约 40 分钟经得起时间
读之前最好知道
1近似最近邻搜索(ANNS)
2倒排索引(inverted index)
3聚类算法(clustering)
4SSD 与磁盘访问特性

学习路径

读这篇之前,按顺序读书架上的 2 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

先熟悉十亿级向量检索的两条主线:基于量化的倒排索引与基于图的索引,再看 SPANN 如何把它们放到内存加 SSD 上。

  1. 1
    Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs基于分层可导航小世界图的高效、鲁棒近似最近邻搜索 · 2016

    图索引的代表,SPANN 对比与借鉴的内存索引方案

    读理解分层可导航小世界图的构造与搜索过程,以及它对内存的需求

  2. 2
    Billion-scale similarity search with GPUs基于 GPU 的十亿级相似性搜索 · 2017

    倒排索引加乘积量化的十亿级检索基线,SPANN 沿用倒排思路

    读读倒排文件(IVF)与乘积量化的部分,看规模化瓶颈在哪里

  3. 3
    SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor SearchSPANN:高效的十亿级近似最近邻搜索 · 2021 · 就是这篇

    目标论文:内存存质心、磁盘存大 posting list 的混合索引

    读抓住质心常驻内存、posting list 落盘以及减少磁盘访问的设计

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐tanoku · 2024-10

“SPANN is a hybrid graph/tree algorithm that does a fantastic job of scaling larger-than-RAM indexes”

推荐 SPANN,称这种图/树混合算法能很好扩展超出内存的索引
The PlanetScale vectors public beta原评论 ↗
引用kingcauchy · 2026-03

“Not strictly google but microsoft/bing too, here's the top ones from my notes:”

把它列入自己笔记里的几篇向量搜索论文,指出微软/Bing 也有成果
Show HN: Antfly: Distributed, Multimodal Search and Memory and Graphs in Go原评论 ↗
被提交为 story · 1 次