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

Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Wenjie Zhang +1 more
10/8/2016
cs.DB

Official code: DBAIWangGroup/nns_benchmark (215 stars, last commit 2021-06-28).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

DBAIWangGroup/nns_benchmarkOfficial100%

Benchmark of Nearest Neighbor Search on High Dimensional Data

21555C, C++Apr 30, 20165 years ago

Similar Papers

EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph

87% match1 repo2992016

Graph-Based Algorithms for Diverse Similarity Search

86% match2025

Approximate Nearest Neighbour Search on Dynamic Datasets: An Investigation

83% match2024

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

83% match1 repo5.4k2016

LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table

82% match1 repo132025

Robust Nearest Neighbour Retrieval Using Targeted Manifold Manipulation

82% match2025

Cite this paper

@article{li2016approximate,
  title  = {Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)},
  author = {Wen Li and Ying Zhang and Yifang Sun and Wei Wang and Wenjie Zhang and Xuemin Lin},
  year   = {2016},
  eprint = {1610.02455},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1610.02455}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1610.02455.svg)](https://codeofpaper.com/paper/1610.02455)

Discussion