Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement (v1.0)

By Wen Li, Ying Zhang, Yifang Sun, W. Zhang, Xuemin Lin. arXiv.org, 2016

299 citations recorded by the source corpus.

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.

Subfields: Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/454eb05da739ad78b1ed4b456d85d756ae79c84b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Orchestrating single-cell analysis with Bioconductor (2019, methodology): “For example, the BiocNeighbors package [97–100] can be used to search for nearest neighbors and then a shared nearest neighbor graph using cells as nodes can be built using the scran [59].”
Towards Neural Theorem Proving at Scale (2018, background): “In particular, we show that the problem of finding the facts in the KB that best explain a query can be reduced to a k-nearest neighbour problem, for which efficient exact and approximate solutions exist (Li et al., 2016).”
Milvus: A Purpose-Built Vector Data Management System (2021, methodology): “Milvus supports three primitive query types: • Vector query: This query type is the traditional vector similarity search [33, 41, 48, 49], where each entity is described as a single vector.”
Dense Text Retrieval Based on Pretrained Language Models: A Survey (2022, methodology): “To reduce the high computational costs of brute-force enumeration, a number of Approximate Nearest Neighbor Search (ANNS) algorithms [248]–[251] are developed to retrieve the approximates of the exact nearest neighbors, possibly with”