k-nearest neighbors algorithm

Web query classification

Web search query

Correlation clustering

Canopy clustering algorithm

Nearest neighbor search

Data mining

Machine learning

Range query (database)

Composite material

Best bin first

Materials science

Range (aeronautics)

Information retrieval

Computer science

Cluster analysis

Fixed-radius near neighbors

Cover tree

Large margin nearest neighbor

Search engine

IEEE Transactions on Knowledge and Data Engineering

Nearest neighbor search is a fundamental and essential operation in applications from many domains, such as databases, machine learning, multimedia, and computer vision. Because exact searching results are not efficient for a high-dimensional space, a lot of efforts have turned to approximate nearest neighbor search. Although many algorithms have been continuously proposed in the literature each year, there is no comprehensive evaluation and analysis of their performance. 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 19 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.

Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement