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

2023/03/17 by Jianyang Gao, Gao, Jianyang, Cheng Long +1 · 17 citations
Computer Science · #Advanced Image and Video Retrieval Techniques #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #H.2 #H.3.3 #Human Pose and Action Recognition #Information Retrieval (cs.IR) #Video Surveillance and Tracking Methods

paper · pdf · doi:10.48550/arxiv.2303.09855

openalex publication_date 2023/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Trading Vector Data in Vector Databases
• Five-Minute Rule 40 Years Later: A First-Principles Revisit for Modern Memory Hierarchy
• Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search
• Approximate Nearest Neighbor Search of Large Scale Vectors on Distributed Storage
• Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search
• Panorama: Fast-Track Nearest Neighbors
• Dynamic Exploration Graph: A Novel Approach for Efficient Nearest Neighbor Search in Evolving Multimedia Datasets
• SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation
• Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation
• Gorgeous: Revisiting the Data Layout for Disk-Resident High-Dimensional Vector Search
• CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search
• GoVector: An I/O-Efficient Caching Strategy for High-Dimensional Vector Nearest Neighbor Search
• WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search
• Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search
• Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search
• PathWeaver: A High-Throughput Multi-GPU System for Graph-Based Approximate Nearest Neighbor Search
• SIEVE: Effective Filtered Vector Search with Collection of Indexes

Related

• Effective and General Distance Computation for Approximate Nearest Neighbor Search
• Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search
• Leveraging Reinforcement Learning for evaluating Robustness of KNN Search Algorithms
• Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)
• Dimensionality-Reduction Techniques for Approximate Nearest Neighbor Search: A Survey and Evaluation