| Nearest neighbor search originated in the field of document retrieval and is used to search similar documents.With the development of information and retrieval requirements,nearest neighbor search is gradually being applied to more fields,including database systems,image search,recommendation systems and so on,to retrieve the results most similar to given data.However,with the rapid development of the Internet,the scale of data has been increasing,from millions to tens of millions,and even to billions,which undoubtedly brings great challenges to nearest neighbor search.For massive and high-dimensional data,the ANNS algorithm improves retrieval efficiency at the expense of certain accuracy,and is widely used because of its fast retrieval speed and small memory usage.Therefore,ANNS gradually replaces the exact nearest neighbor search and becomes one of the necessary means for retrieving information.In the field of approximate nearest neighbor search,the ways to accelerate the search include building inverted index and graph-based index.In the search algorithm using the inverted index,the query point only searches for the closest type of data,thereby reducing the number of retrieved data points;the graph-based index uses the neighbor relationship between the data to build a neighbor graph,which can quickly find the query point when searching nearest neighbor.However,in the current approximate nearest neighbor search algorithm based on inverted index and graph-based index structure,since all query points use fixed termination conditions,some query points access unnecessary data points on the search path,resulting in average search time increases and search performance decreases.Therefore,this paper analyzes the termination conditions of all data points on the index structure of the IVF-HNSW algorithm for the four billion-scale data sets released publicly,and proposes an adaptive search algorithm based on query vector features and k-means features.Establishing and training the neural network regression model according to the characteristics of the data and the actual minimum number of access points,and dynamically predicting the number of inverted lists that need to be searched for each query point in IVF through the model,thereby reducing the query time required for the overall search.The main contributions of this paper are as follows:Firstly,predicting termination conditions for data points by querying vector features.The adaptive search algorithm based on query vector features first needs to collect training samples,the input data of the model uses the training data itself,and the output data is the actual minimum number of access points of the training data in the index structure.Then,the training data is used to train the neural network regression model.At the last,the termination condition of the query vector is predicted according to the neural network regression model,so as to speed up the search and achieve more efficient query.Secondly,predicting the termination conditions of data points by k-means features.The adaptive search algorithm based on the k-means feature first clusters the training data through the k-means method,and calculates the ratio between the distance from the data point to the 5th,10 th,15th,20 th cluster center and the distance from the data point to the 1st cluster center.The ratio is used as the k-means feature.Then,the k-means feature and the minimum number of access points are respectively used as input data and output data to train the neural network regression model.At the last,according to the k-means feature of the query vector,offline prediction its termination condition and realizes adaptive search,so that each data point stops searching under the corresponding termination condition,thereby reducing unnecessary search time.Finally,experiments are carried out on four publicly available billion-scale datasets,and the proposed two algorithms are fully verified.The experimental results show that the average search time can be reduced by up to 16.49% and 26.9% respectively under the same recall rate compared with the benchmark algorithm based on query vector features and k-means features,which fully proves that the use of query vector features and k-means features predict the effectiveness of the termination condition. |
