Graph based nearest neighbor search needs extra points for fast queries
On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search
Data Structures and AlgorithmsMachine Learning
Summary
Finding nearest neighbors in large datasets is often done by searching through graphs, but these methods lack guarantees that queries will be fast in all cases. The authors show that usual graph-based searches can’t always answer queries quickly, even if you allow very rough approximations. However, if you add special extra points called Steiner points to the graph, sublinear query times become achievable. Their experiments show how to add these points to existing methods to potentially speed up searches.
What this means in practice
- •For machine learning engineers: Design faster approximate nearest neighbor searches by incorporating Steiner points into graph-based index structures.
- •For computer vision teams: Improve image retrieval speed in large databases by using graph search methods enhanced with additional Steiner nodes.
A theory result. No direct application yet.
Authors
Majid Daliri, Mohammadreza Daneshvaramoli, Purna Dutta, Edo Liberty, Cameron Musco, Christopher Musco, Torsten Suel
Abstract
Graph-based nearest neighbor search algorithms like HNSW, DiskANN, NSG, and others have surged in popularity in recent years due to their excellent empirical performance in comparison to space-partitioning methods like IVF data structures and Locality Sensitive Hashing (LSH). However, in contrast to LSH and related methods, obtaining strong worst-case theoretical guarantees for graph-based search has proven challenging. In this paper, we prove a strong lower bound that helps explain the lack of progress towards such guarantees. We show that no standard graph-based method (any that runs a variant of greedy search on a flat or hierarchical graph) can achieve sublinear query time for approximate nearest neighbor search in Euclidean space, even for an arbitrarily large approximation factor. On the other hand, we prove that sublinear query time is possible if we allow for Steiner points in the search graph. We obtain bounds comparable to LSH, showing e.g., that graph-based search with Steiner points can solve $c$-approximate nearest neighbor search in Euclidean space with query time $\tilde{O}(n^{1/(c-1)})$. We complement this result with initial experiments exploring how Steiner points can be incorporated into practical graph-based methods.