Vector nearest neighbor search, which provides relevant results by searching vectors with minimum distance to the query vector, is crucial in the information retrieval area. Many algorithms of approximate nearest neighbor search (ANNS) have been proposed; however, in large-scale scenarios, such as web search, the memory cost becomes extremely expensive.
A recent paper on arXiv.org argues that the simple inverted index approach can also achieve state-of-the-art performance for large-scale datasets in terms of recall, latency, and memory cost.
SPANN, a simple and efficient memory-disk hybrid vector indexing and search system, is proposed. It guarantees low latency and high recall by greatly reducing the number of disk accesses and improving the quality of posting lists. Experiments demonstrate that SPANN is more than two times faster than the state-of-the-art ANNS algorithm to reach the same recall quality.
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× 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% [email protected] and [email protected] in just around one millisecond with only 32GB memory cost. Code is available at this https URL.
Research paper: Chen, Q., “SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search”, 2021. Link: https://arxiv.org/abs/2111.08566