The in-memory algorithms for approximate nearest neighbor search (ANNS) have
achieved great success for fast high-recall search, but are extremely expensive
when handling very large scale database. Thus, there is an increasing request
for the hybrid ANNS solutions with small memory and inexpensive solid-state
drive (SSD). In this paper, we present a simple but efficient memory-disk
hybrid indexing and search system, named SPANN, that follows the inverted index
methodology. It stores the centroid points of the posting lists in the memory
and the large posting lists in the disk. We guarantee both disk-access
efficiency (low latency) and high recall by effectively reducing the
disk-access number and retrieving high-quality posting lists. In the
index-building stage, we adopt a hierarchical balanced clustering algorithm to
balance the length of posting lists and augment the posting list by adding the
points in the closure of the corresponding clusters. In the search stage, we
use a query-aware scheme to dynamically prune the access of unnecessary posting
lists. Experiment results demonstrate that SPANN is 2$\times$ faster than the
state-of-the-art ANNS solution DiskANN to reach the same recall quality $90\%$
with same memory cost in three billion-scale datasets. It can reach $90\%$
recall@1 and recall@10 in just around one millisecond with only 32GB memory
cost. Code is available at:
{\footnotesize\color{blue}{https://github.com/microsoft/SPTAG}}.

本文提出了一种名为 SPANN 的内存磁盘混合索引和搜索系统，它采用倒排索引方法论，将单元点存储在内存中，较大的单元列表存储在磁盘中，采用分层平衡聚类算法来平衡单元列表的长度，采用查询感知方案动态修剪不必要的单元列表查询，实验证明该系统相较于现有的近似最近邻搜索（ANNS）解决方案 DiskANN 在处理数十亿数据集时，可以用相同的内存成本实现同样的召回率质量，并且速度快 2 倍以上 。