Towards Accurate Distance Estimation for Distribution-Aware c-ANN Search

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.