  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.
