FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search
This work addresses a performance bottleneck in graph-based search for applications like two-tower deep learning models, offering a significant speed improvement but is incremental as it builds on existing methods like HNSW.
The paper tackled the problem of inefficient distance computations in graph-based approximate nearest neighbor search by proposing FINGER, a fast inference method that approximates distances to bypass unnecessary calculations, resulting in 20%-60% faster searches compared to existing methods on benchmark datasets.
Approximate K-Nearest Neighbor Search (AKNNS) has now become ubiquitous in modern applications, for example, as a fast search procedure with two tower deep learning models. Graph-based methods for AKNNS in particular have received great attention due to their superior performance. These methods rely on greedy graph search to traverse the data points as embedding vectors in a database. Under this greedy search scheme, we make a key observation: many distance computations do not influence search updates so these computations can be approximated without hurting performance. As a result, we propose FINGER, a fast inference method to achieve efficient graph search. FINGER approximates the distance function by estimating angles between neighboring residual vectors with low-rank bases and distribution matching. The approximated distance can be used to bypass unnecessary computations, which leads to faster searches. Empirically, accelerating a popular graph-based method named HNSW by FINGER is shown to outperform existing graph-based methods by 20%-60% across different benchmark datasets.