Approximate Nearest Neighbor Search Based on Neighbor Graphs with Parameter Adaptation

Approximate Nearest Neighbor Search(ANNS) algorithms based on neighbor graphs typically organize vectors in a database into a neighbor graph structure and obtain the Approximate Nearest Neighbor(ANN) of the query vector by leveraging user-specified search parameter configurations.An adaptive method named AdaptNNS is proposed to improve the search efficiency of ANNS algorithms based on neighbor graphs given specific recall rate requirements.First, AdaptNNS samples vectors in the database and clusters the sampling results.Second, AdaptNNS uses centroids as nearest neighbor classifiers to extract query load features.Finally, AdaptNNS concatenates different recall rate targets and features from the query load to create a model input, which it then uses to train a Gradient Boosting Decision Tree(GBDT) model.During the query processing phase, AdaptNNS obtains input features of the trained model with queries and specified recall rate values and improves the throughput of the ANNS by predicting optimal search parameters. Experiments are performed on Text-to-Image, DEEP, and Turing-ANNS datasets using DiskANN and HNSW algorithms.The results show that AdaptNNS can increase the throughput by a maximum of 1.3 times as compared with the Baseline method when the same target recall rate is reached.Thus, AdaptNNS searches ANNs more efficiently.