Effective Probabilistic Feature for Adaptive Learning Model to Accelerate Approximate Nearest Neighbor Search

The quantization-based approaches are the effective methods for solving the problems of approximate nearest neighbor search. However, many quantization-based approaches usually employ an uniformed number of nProbes as termination condition to performing search process for each query. This will result in extra time consumption due to the fact that the search for many queries is terminated rapidly before completely retrieve the points contained in its nProbes nearest subspace. To this end, we propose to train an uniformed learning prediction model using effective input features generated by locality sensitive hashing, such that adaptively predicts the termination condition for each query to speedup the query process. Many experiments show that our proposal is superior to other state-of-the-art methods.