Exploiting lower bounds to accelerate approximate nearest neighbor search on high-dimensional data

According to the extensive experiments on real data sets, we demonstrate that our lower bounds are able to obviously accelerate ANN search of the existing indexing methods, and our lower bounds outperform the existing lower bounds by a significant margin, due to their strong pruning powers. Especially, AQD speedups the state-of-the-art indexing method HNSW (Malkov and Yashunin, 2016) 1.9 times for a high recall 0.95. As to other indexing methods, the speedups of AQD are even higher, because they need to access more candidates than HNSW.