Locality sensitive hashing (LSH) is a representative approach for nearest neighbor (NN) search in high-dimensional spaces, which is able to answer c-approximate NN (c-ANN) queries in sublinear time with constant probability. Existing advanced LSH methods leverage a plurality of novel techniques such as query-aware dynamic bucketing, virtual rehashing, and efficient indexing to achieve state-of-the-art performance. However, they rely on similar random LSH functions, which provides distance estimations that are irrelevant to the given data distribution. Therefore, the quality of the searched candi-dates is suboptimal. In this study, we reformulate the c-ANN query from the perspective of data distribution. Specifically, we propose a novel distribution-aware c-ANN query, which can guarantee the quality of searched results from the query distribution perspective. We introduce an accurately unbiased distance estimator into LSH methods, which can provide more precise distance estimations by modeling the data distribution. We also conduct rigorous theoretical analysis to prove that our methods can correctly answer the distribution-aware c-ANN query with at least a constant probability. Experiments on seven real datasets with different sizes and dimensionalities indicate that the proposed method can achieve better performance than existing LSH methods in terms of efficiency and effectiveness.

Approximate nearest neighbor search is fundamental in information retrieval. Previous partition-based methods enhance search efficiency by probing partial partitions, yet they face two common issues. In the query phase, a common strategy is to probe partitions based on the distance ranks of a query to partition centroids, which inevitably probes irrelevant partitions as it ignores data distribution. In the partition construction phase, all partition-based methods face the boundary problem that separates a query's nearest neighbors to multiple partitions, resulting in a long-tailed kNN distribution and degrading the optimal nprobe (i.e., the number of probing partitions). To address this gap, we propose LIRA, a LearnIng-based queRy-aware pArtition framework. Specifically, we propose a probing model to directly probe the partitions containing the kNN of a query, which can reduce probing waste and allow for query-aware probing with nprobe individually. Moreover, we incorporate the probing model into a learning-based redundancy strategy to mitigate the adverse impact of the long-tailed kNN distribution on search efficiency. Extensive experiments on real-world vector datasets demonstrate the superiority of LIRA in the trade-off among accuracy, latency, and query fan-out. The codes are available at https://github.com/SimoneZeng/LIRA-ANN-search.

High-dimensional approximate K nearest neighbor search (AKNN) is a fundamental task for various applications, including information retrieval. Most existing algorithms for AKNN can be decomposed into two main components, i.e., candidate generation and distance comparison operations (DCOs). While different methods have unique ways of generating candidates, they all share the same DCO process. In this study, we focus on accelerating the process of DCOs that dominates the time cost in most existing AKNN algorithms. To achieve this, we propose an Data-Aware Distance Estimation approach, called DADE , which approximates the exact distance in a lower-dimensional space. We theoretically prove that the distance estimation in DADE is unbiased in terms of data distribution. Furthermore, we propose an optimized estimation based on the unbiased distance estimation formulation. In addition, we propose a hypothesis testing approach to adaptively determine the number of dimensions needed to estimate the exact distance with sufficient confidence. We integrate DADE into widely-used AKNN search algorithms, e.g., IVF and HNSW , and conduct extensive experiments to demonstrate the superiority.