mlsanityData to 7 Oct 2026

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

arXiv 1610.02455 ↗First posted 8 Oct 2016cs.DBcited by 44

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 4; 2023: 13; 2024: 16; 2025: 1; 2026: 1.

44 papers.

Sort:

By area:

  1. 2021Hyperdimensional computing as a framework for systematic aggregation of image descriptorscited by 32
  2. 2023Visual Place Recognition: A Tutorialcited by 31
  3. 2023CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUscited by 22
  4. 2023Similarity search in the blink of an eye with compressed indicescited by 20
  5. 2023Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitationscited by 20
  6. 2022Distill-VQ: Learning Retrieval Oriented Vector Quantization By Distilling Knowledge from Dense Embeddingscited by 17
  7. 2021What makes visual place recognition easy or hard?cited by 14
  8. 2023Pre-trained Embeddings for Entity Resolution: An Experimental Analysis [Experiment, Analysis & Benchmark]cited by 13
  9. 2024Auto-Formula: Recommend Formulas in Spreadsheets using Contrastive Learning for Table Representationscited by 12
  10. 2024RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Searchcited by 12
  11. 2024Generative Dense Retrieval: Memory Can Be a Burdencited by 11
  12. 2021Data Twinningcited by 10
32 more
  1. 2024Locally-Adaptive Quantization for Streaming Vector Searchcited by 10
  2. 2021Mask-GVAE: Blind Denoising Graphs via Partitioncited by 9
  3. 2022TaDaa: real time Ticket Assignment Deep learning Auto Advisor for customer support, help desk, and issue ticketing systemscited by 7
  4. 2024Multi-Label Plant Species Classification with Self-Supervised Vision Transformerscited by 7
  5. 2021Beyond ANN: Exploiting Structural Knowledge for Efficient Place Recognitioncited by 6
  6. 2023Track Mix Generation on Music Streaming Services using Transformerscited by 6
  7. 2023Cross Modal Data Discovery over Structured and Unstructured Data Lakescited by 5
  8. 2024VDTuner: Automated Performance Tuning for Vector Data Management Systemscited by 5
  9. 2022Reducing Training Sample Memorization in GANs by Training with Memorization Rejectioncited by 4
  10. 2024Evaluation of Semantic Search and its Role in Retrieved-Augmented-Generation (RAG) for Arabic Languagecited by 4
  11. 2024CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestioncited by 4
  12. 2024LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Searchcited by 4
  13. 2023AdANNS: A Framework for Adaptive Semantic Searchcited by 2
  14. 2023K-Nearest-Neighbor Resampling for Off-Policy Evaluation in Stochastic Controlcited by 2
  15. 2023MultiEM: Efficient and Effective Unsupervised Multi-Table Entity Matchingcited by 2
  16. 2023Locally Adaptive and Differentiable Regressioncited by 2
  17. 2024Approximate Nearest Neighbour Search on Dynamic Datasets: An Investigationcited by 2
  18. 2024ChipExpert: The Open-Source Integrated-Circuit-Design-Specific Large Language Modelcited by 2
  19. 2023EHI: End-to-end Learning of Hierarchical Index for Efficient Dense Retrievalcited by 1
  20. 2024ChatGraph: Chat with Your Graphscited by 1
  21. 2024Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Searchcited by 1
  22. 2024Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoderscited by 1
  23. 2021Instance-based learning using the Half-Space Proximal Graphcited by 0
  24. 2021A multimodal deep learning framework for scalable content based visual media retrievalcited by 0
  25. 2021A Simple Generative Networkcited by 0
  26. 2021Scalable Reverse Image Search Engine for NASAWorldviewcited by 0
  27. 2022Learned k-NN Distance Estimationcited by 0
  28. 2023Fast Locality Sensitive Hashing with Theoretical Guaranteecited by 0
  29. 2024Exploring the Meaningfulness of Nearest Neighbor Search in High-Dimensional Spacecited by 0
  30. 2024Online and Offline Evaluations of Collaborative Filtering and Content Based Recommender Systemscited by 0
  31. 2025Bidding-Aware Retrieval for Multi-Stage Consistency in Online Advertisingcited by 0
  32. 2026Progressive Searching for Retrieval in RAGcited by 0