mlsanityData to 14 Oct 2026

Approximate Nearest Neighbor Search in High Dimensions

arXiv 1806.09823 ↗First posted 26 Jun 2018cs.DS cs.CG cs.DBcited by 47

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 10; 2022: 7; 2023: 6; 2024: 7; 2025: 11; 2026: 6.

47 papers.

Sort:

By area:

  1. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 252
  2. 2022Multi-View Document Representation Learning for Open-Domain Dense Retrievalcited by 41
  3. 2021Multi-Vector Models with Textual Guidance for Fine-Grained Scientific Document Similaritycited by 35
  4. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  5. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  6. 2021Learning-Augmented k-means Clusteringcited by 26
  7. 2024Hidden in the Noise: Two-Stage Robust Watermarking for Imagescited by 21
  8. 2023Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitationscited by 20
  9. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  10. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  11. 2021Linear Bandit Algorithms with Sublinear Time Complexitycited by 9
  12. 2021SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddingscited by 9
35 more
  1. 2021Learning to Hash Robustly, Guaranteedcited by 7
  2. 2022Sublinear Time Algorithm for Online Weighted Bipartite Matchingcited by 7
  3. 2021Self-Supervised Motion Retargeting with Safety Guaranteecited by 6
  4. 2022Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Searchcited by 6
  5. 2022A Theoretical View on Sparsely Activated Networkscited by 6
  6. 2024HashEvict: A Pre-Attention KV Cache Eviction Strategy using Locality-Sensitive Hashingcited by 6
  7. 2023Query Encoder Distillation via Embedding Alignment is a Strong Baseline Method to Boost Dense Retriever Online Efficiencycited by 5
  8. 2024LSHBloom: Memory-efficient, Extreme-scale Document Deduplicationcited by 5
  9. 2025syftr: Pareto-Optimal Generative AIcited by 5
  10. 2023Data Structures for Density Estimationcited by 4
  11. 20254bit-Quantization in Vector-Embedding for RAGcited by 4
  12. 2025Monitoring Robustness and Individual Fairnesscited by 3
  13. 2023Simple, Scalable and Effective Clustering via One-Dimensional Projectionscited by 2
  14. 2024Conditional Mean and Variance Estimation via textitk-NN Algorithm with Automated Variance Selectioncited by 2
  15. 2024Gini Coefficient as a Unified Metric for Evaluating Many-versus-Many Similarity in Vector Spacescited by 2
  16. 2022Unsupervised Space Partitioning for Nearest Neighbor Searchcited by 1
  17. 2026DASH-KV: Accelerating Long-Context LLM Inference via Asymmetric KV Cache Hashingcited by 1
  18. 2021Nearest Neighbor Search Under Uncertaintycited by 0
  19. 2022Addressing Bias in Face Detectors using Decentralised Data collection with incentivescited by 0
  20. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0
  21. 2024Scalable Density-based Clustering with Random Projectionscited by 0
  22. 2024Discovering Data Structures: Nearest Neighbor Search and Beyondcited by 0
  23. 2025Beyond Worst-Case Dimensionality Reduction for Sparse Vectorscited by 0
  24. 2025GARLIC: GAussian Representation LearnIng for spaCe partitioningcited by 0
  25. 2025Lightweight Relevance Grader in RAGcited by 0
  26. 2025A Hybrid Framework for Subject Analysis: Integrating Embedding-Based Regression Models with Large Language Modelscited by 0
  27. 2025Enhancing Serendipity Recommendation System by Constructing Dynamic User Knowledge Graphs with Large Language Modelscited by 0
  28. 2025Stack Trace-Based Crash Deduplication with Transformer Adaptationcited by 0
  29. 2025Multimedia-Aware Question Answering: A Review of Retrieval and Cross-Modal Reasoning Architecturescited by 0
  30. 2025Graph-based Nearest Neighbors with Dynamic Updates via Random Walkscited by 0
  31. 2026Progressive Searching for Retrieval in RAGcited by 0
  32. 2026Learning Partition Trees for Nearest Neighbor Searchcited by 0
  33. 2026Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificatescited by 0
  34. 2026Multimodal Dual-Encoder Retrieval for Automated ICD Codingcited by 0
  35. 2026Efficient Test-time Adaptation through Candidate Verification and Divergence Shiftscited by 0