# Approximate Nearest Neighbor Search in High Dimensions

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2018.

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

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Multi-View Document Representation Learning for Open-Domain Dense Retrieval](https://mlsanity.com/paper/2203.08372/) (2022)
- [Multi-Vector Models with Textual Guidance for Fine-Grained Scientific Document Similarity](https://mlsanity.com/paper/2111.08366/) (2021)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Hidden in the Noise: Two-Stage Robust Watermarking for Images](https://mlsanity.com/paper/2412.04653/) (2024)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddings](https://mlsanity.com/paper/2112.05872/) (2021)
- [Learning to Hash Robustly, Guaranteed](https://mlsanity.com/paper/2108.05433/) (2021)
- [Sublinear Time Algorithm for Online Weighted Bipartite Matching](https://mlsanity.com/paper/2208.03367/) (2022)
- [Self-Supervised Motion Retargeting with Safety Guarantee](https://mlsanity.com/paper/2103.06447/) (2021)
- [Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2206.01382/) (2022)
- [A Theoretical View on Sparsely Activated Networks](https://mlsanity.com/paper/2208.04461/) (2022)
- [HashEvict: A Pre-Attention KV Cache Eviction Strategy using Locality-Sensitive Hashing](https://mlsanity.com/paper/2412.16187/) (2024)
- [Query Encoder Distillation via Embedding Alignment is a Strong Baseline Method to Boost Dense Retriever Online Efficiency](https://mlsanity.com/paper/2306.11550/) (2023)
- [LSHBloom: Memory-efficient, Extreme-scale Document Deduplication](https://mlsanity.com/paper/2411.04257/) (2024)
- [syftr: Pareto-Optimal Generative AI](https://mlsanity.com/paper/2505.20266/) (2025)
- [Data Structures for Density Estimation](https://mlsanity.com/paper/2306.11312/) (2023)
- [4bit-Quantization in Vector-Embedding for RAG](https://mlsanity.com/paper/2501.10534/) (2025)
- [Monitoring Robustness and Individual Fairness](https://mlsanity.com/paper/2506.00496/) (2025)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [Conditional Mean and Variance Estimation via textitk-NN Algorithm with Automated Variance Selection](https://mlsanity.com/paper/2402.01635/) (2024)
- [Gini Coefficient as a Unified Metric for Evaluating Many-versus-Many Similarity in Vector Spaces](https://mlsanity.com/paper/2411.07983/) (2024)
- [Unsupervised Space Partitioning for Nearest Neighbor Search](https://mlsanity.com/paper/2206.08091/) (2022)
- [DASH-KV: Accelerating Long-Context LLM Inference via Asymmetric KV Cache Hashing](https://mlsanity.com/paper/2604.19351/) (2026)
- [Nearest Neighbor Search Under Uncertainty](https://mlsanity.com/paper/2103.05057/) (2021)

## Abstract (arXiv)

The nearest neighbor problem is defined as follows: Given a set P of n points in some metric space (X,D), build a data structure that, given any point q, returns a point in P that is closest to q (its "nearest neighbor" in P). The data structure stores additional information about the set P, which is then used to find the nearest neighbor without computing all distances between q and P. The problem has a wide range of applications in machine learning, computer vision, databases and other fields. To reduce the time needed to find nearest neighbors and the amount of memory used by the data structure, one can formulate the em approximate nearest neighbor problem, where the the goal is to return any point p' ∈ P such that the distance from q to p' is at most c · minp ∈ P D(q,p), for some c ≥ 1. Over the last two decades, many efficient solutions to this problem were developed. In this article we survey these developments, as well as their connections to questions in geometric functional analysis and combinatorial geometry.