Hypersphere-Based Adaptive Filtration for Approximate Nearest Neighbor Search

Existing inverted index-based approximate nearest neighbor search methods are hindered by the necessity for manual adjustment of the quantity of inverted lists and the presence of negative similar results in the candidate set. These limitations inevitably restrict both search efficiency and generalization. To address these issues, we propose two ANNS methods based on adaptive hypersphere filtration, consisting of 3 steps: obtaining the candidate set, adaptive hypersphere filtration, and reranking. For this purpose, a hypersphere learning model is developed by adopting a fully connected neural network, which is independent of the vector dimension. Then, this model can be compatible with vectors of different dimensions without any architectural modifications. Each query vector is associated with an adaptive size hypersphere. In the procedure of obtaining the candidate set, only the inverted lists associated with the corresponding centroid located inside the hypersphere are employed to construct the candidate set. In the filtration stage, the hypersphere is employed to eliminate vectors dissimilar to the query vectors from the candidate set, thereby decreasing the number of candidate vectors taken into reranking. Experimental results on three public datasets demonstrate that two ANNS methods based on adaptive hypersphere filtration can effectively enhance the retrieval efficiency without weakening retrieval accuracy.