Approximate Nearest neighbor search (ANNS) is fundamental and essential
operation in applications from many domains, such as databases, machine
learning, multimedia, and computer vision. Although many algorithms have been
continuously proposed in the literature in the above domains each year, there
is no comprehensive evaluation and analysis of their performances.
In this paper, we conduct a comprehensive experimental evaluation of many
state-of-the-art methods for approximate nearest neighbor search. Our study (1)
is cross-disciplinary (i.e., including 16 algorithms in different domains, and
from practitioners) and (2) has evaluated a diverse range of settings,
including 20 datasets, several evaluation metrics, and different query
workloads. The experimental results are carefully reported and analyzed to
understand the performance results. Furthermore, we propose a new method that
achieves both high query efficiency and high recall empirically on majority of
the datasets under a wide range of settings.

本文详细评估了 16 种不同算法在 20 个不同数据集、多个评估指标和不同查询工作负载下的性能表现，并提出了一种新的方法以提高查询效率和召回率。