mlsanityData to 7 Oct 2026

High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations

arXiv 2303.09855 ↗First posted 17 Mar 2023cs.DS cs.DB cs.IRcited by 25

Not on the map. Why?

Abstract (arXiv)

Approximate K nearest neighbor (AKNN) search is a fundamental and challenging problem. We observe that in high-dimensional space, the time consumption of nearly all AKNN algorithms is dominated by that of the distance comparison operations (DCOs). For each operation, it scans full dimensions of an object and thus, runs in linear time wrt the dimensionality. To speed it up, we propose a randomized algorithm named ADSampling which runs in logarithmic time wrt to the dimensionality for the majority of DCOs and succeeds with high probability. In addition, based on ADSampling we develop one general and two algorithm-specific techniques as plugins to enhance existing AKNN algorithms. Both theoretical and empirical studies confirm that: (1) our techniques introduce nearly no accuracy loss and (2) they consistently improve the efficiency.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). First posted on arXiv 17 Mar 2023.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 4; 2025: 10; 2026: 9.

25 papers.

Sort:

By area:

  1. 2023A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challengecited by 55
  2. 2023Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Modelscited by 23
  3. 2025RAGO: Systematic Performance Optimization for Retrieval-Augmented Generation Servingcited by 18
  4. 2024RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Searchcited by 12
  5. 2025PDX: A Data Layout for Vector Similarity Searchcited by 8
  6. 2024CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestioncited by 4
  7. 2025LEANN: A Low-Storage Vector Indexcited by 4
  8. 2025Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Searchcited by 4
  9. 2024Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Searchcited by 3
  10. 2025HAKES: Scalable Vector Database for Embedding Search Servicecited by 2
  11. 2025Probabilistic Kernel Function for Fast Angle Testingcited by 2
  12. 2025Panorama: Fast-Track Nearest Neighborscited by 2
13 more
  1. 2026A Super Fast K-means for Indexing Vector Embeddingscited by 2
  2. 2025Bang for the Buck: Vector Search on Cloud CPUscited by 1
  3. 2024UpANNS: Enhancing Billion-Scale ANNS Efficiency with Real-World PIM Architecturecited by 0
  4. 2025Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Searchcited by 0
  5. 2025Trading Vector Data in Vector Databasescited by 0
  6. 2026Efficient K-generalizable Learned Searchcited by 0
  7. 2026Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approachcited by 0
  8. 2026CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Datacited by 0
  9. 2026NasZip: Software and Hardware Co-Design to Accelerate Approximate Nearest Neighbor Search with DIMM-Based Near-Data Processingcited by 0
  10. 2026ANN Search: Recall What Matterscited by 0
  11. 2026HNSW with Accuracy Guarantees Using Graph Spannerscited by 0
  12. 2026Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddingscited by 0
  13. 2026A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Searchcited by 0