Algorithms for approximate nearest-neighbor search (ANNS) have been the topic
of significant recent interest in the research community. However, evaluations
of such algorithms are usually restricted to a small number of datasets with
millions or tens of millions of points, whereas real-world applications require
algorithms that work on the scale of billions of points. Furthermore, existing
evaluations of ANNS algorithms are typically heavily focused on measuring and
optimizing for queries-per second (QPS) at a given accuracy, which can be
hardware-dependent and ignores important metrics such as build time.
In this paper, we propose a set of principled measures for evaluating ANNS
algorithms which refocuses on their scalability to billion-size datasets. These
measures include ability to be efficiently parallelized, build times, and
scaling relationships as dataset size increases. We also expand on the QPS
measure with machine-agnostic measures such as the number of distance
computations per query, and we evaluate ANNS data structures on their accuracy
in more demanding settings required in modern applications, such as evaluating
range queries and running on out-of-distribution data. We optimize four
graph-based algorithms for the billion-scale setting, and in the process
provide a general framework for making many incremental ANNS graph algorithms
lock-free. We use our framework to evaluate the aforementioned graph-based ANNS
algorithms as well as two alternative approaches.

本文提出了一组基于可扩展性的原则度量 ANNS 算法的评估标准，包括并行性能、建树时间、性能随数据集增加的扩展性以及机器无关的度量方法等，并优化了四种基于图的算法，提供了一种通用的无锁的递增 ANNS 图算法框架来应对现代应用所需的更高难度的准确性评价