Data-Aware Locality-Sensitive Hashing with Theoretical Guarantees for Approximate Nearest Neighbor Search

Locality-sensitive hashing (LSH) has been widely used for c-approximate nearest neighbor search (c-ANNS) in high-dimensional spaces. However, its retrieval performance degrades as the dataset size grows. To address this limitation, we propose a data-dependent hashing framework called data-aware locality-sensitive hashing (DASH). DASH exploits the quantization properties of product quantization (PQ) to learn a data-aware residual prior, enabling adaptive, data-sensitive LSH. By converting exact Euclidean distance computations into efficient table lookup operations, DASH reduces computational costs and enhances retrieval efficiency. Based on the residual prior, DASH provides a theoretical performance guarantee comparable to that of standard LSH. Extensive experiments on multiple benchmark datasets demonstrate that DASH consistently achieves superior search accuracy and efficiency, yielding up to 40× speedups over various state-of-the-art baselines.