Scaling Graph-Based ANNS Algorithms to Billion-Size Datasets: A Comparative Analysis
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.