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

• DOI: 10.48550/arxiv.2303.09855
• Publication Date: 2023-01-01
• Authors: Jianyang Gao; Cheng Long
• Keywords: Best bin first; Fixed-radius near neighbors

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 dominated by distance comparison operations (DCOs). For each operation, it scans full dimensions an object thus, runs linear wrt dimensionality. To speed up, we propose randomized algorithm named ADSampling which logarithmic to dimensionality for majority DCOs succeeds with high probability. In addition, based on develop one general two algorithm-specific techniques as plugins enhance existing algorithms. Both theoretical empirical studies confirm that: (1) our introduce no accuracy loss (2) they consistently improve efficiency.