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

arXiv: https://arxiv.org/abs/1610.02455 · HTML: https://mlsanity.com/paper/1610.02455/

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2016.

## Built on by (most cited first, 30 of 44)

- [Hyperdimensional computing as a framework for systematic aggregation of image descriptors](https://mlsanity.com/paper/2101.07720/) (2021)
- [Visual Place Recognition: A Tutorial](https://mlsanity.com/paper/2303.03281/) (2023)
- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [Similarity search in the blink of an eye with compressed indices](https://mlsanity.com/paper/2304.04759/) (2023)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [Distill-VQ: Learning Retrieval Oriented Vector Quantization By Distilling Knowledge from Dense Embeddings](https://mlsanity.com/paper/2204.00185/) (2022)
- [What makes visual place recognition easy or hard?](https://mlsanity.com/paper/2106.12671/) (2021)
- [Pre-trained Embeddings for Entity Resolution: An Experimental Analysis [Experiment, Analysis & Benchmark]](https://mlsanity.com/paper/2304.12329/) (2023)
- [Auto-Formula: Recommend Formulas in Spreadsheets using Contrastive Learning for Table Representations](https://mlsanity.com/paper/2404.12608/) (2024)
- [RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2408.08933/) (2024)
- [Generative Dense Retrieval: Memory Can Be a Burden](https://mlsanity.com/paper/2401.10487/) (2024)
- [Locally-Adaptive Quantization for Streaming Vector Search](https://mlsanity.com/paper/2402.02044/) (2024)
- [Data Twinning](https://mlsanity.com/paper/2110.02927/) (2021)
- [Mask-GVAE: Blind Denoising Graphs via Partition](https://mlsanity.com/paper/2102.04228/) (2021)
- [TaDaa: real time Ticket Assignment Deep learning Auto Advisor for customer support, help desk, and issue ticketing systems](https://mlsanity.com/paper/2207.11187/) (2022)
- [Multi-Label Plant Species Classification with Self-Supervised Vision Transformers](https://mlsanity.com/paper/2407.06298/) (2024)
- [Beyond ANN: Exploiting Structural Knowledge for Efficient Place Recognition](https://mlsanity.com/paper/2103.08366/) (2021)
- [Track Mix Generation on Music Streaming Services using Transformers](https://mlsanity.com/paper/2307.03045/) (2023)
- [Cross Modal Data Discovery over Structured and Unstructured Data Lakes](https://mlsanity.com/paper/2306.00932/) (2023)
- [VDTuner: Automated Performance Tuning for Vector Data Management Systems](https://mlsanity.com/paper/2404.10413/) (2024)
- [Reducing Training Sample Memorization in GANs by Training with Memorization Rejection](https://mlsanity.com/paper/2210.12231/) (2022)
- [Evaluation of Semantic Search and its Role in Retrieved-Augmented-Generation (RAG) for Arabic Language](https://mlsanity.com/paper/2403.18350/) (2024)
- [CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestion](https://mlsanity.com/paper/2406.19651/) (2024)
- [LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2410.18926/) (2024)
- [AdANNS: A Framework for Adaptive Semantic Search](https://mlsanity.com/paper/2305.19435/) (2023)
- [K-Nearest-Neighbor Resampling for Off-Policy Evaluation in Stochastic Control](https://mlsanity.com/paper/2306.04836/) (2023)
- [MultiEM: Efficient and Effective Unsupervised Multi-Table Entity Matching](https://mlsanity.com/paper/2308.01927/) (2023)
- [Locally Adaptive and Differentiable Regression](https://mlsanity.com/paper/2308.07418/) (2023)
- [Approximate Nearest Neighbour Search on Dynamic Datasets: An Investigation](https://mlsanity.com/paper/2404.19284/) (2024)
- [ChipExpert: The Open-Source Integrated-Circuit-Design-Specific Large Language Model](https://mlsanity.com/paper/2408.00804/) (2024)

## Abstract (arXiv)

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.