Angular Distance-Guided Neighbor Selection for Graph-Based Approximate Nearest Neighbor Search

Abstract

Graph-based approximate nearest neighbor search (ANNS) algorithms are widely used to identify the most similar vectors to a given query vector. Graph-based ANNS consists of two stages: constructing a graph and searching on the graph for a given query vector. While reducing the query response time is of great practical importance, less attention has been paid to improving the online search method than the offline graph construction method. This paper provides an extensive experimental analysis on the popular greedy search and other search optimization strategies. We also propose a novel angular distance-guided search method for graph-based ANNS (ADA-NNS) to improve search efficiency. The key innovation of ADA-NNS is introducing a low-cost neighbor selection mechanism based on an approximate similarity score derived from angular distance estimation, which effectively filters out less relevant neighbors. We compare state-of-the-art search techniques, including FINGER, on six datasets using different similarity metrics. It provides a comprehensive perspective on their tradeoffs in terms of throughput, latency, and recall. Our evaluation shows that ADA-NNS achieves 34%-107% higher queries per second (QPS) than the greedy search at 95% recall@10 on HNSW, one of the most popular graph structures for ANNS.