Poster
in
Workshop: The 1st Workshop on Vector Databases
Scaling Laws for Nearest Neighbor Search
Philip Sun · Felix Chern · Yaroslav Akhremtsev · Ruiqi Guo · David Simcha · Sanjiv Kumar
Abstract:
This paper investigates the scaling laws that characterize the performance of various nearest neighbor search algorithms across a number of operational scenarios. We analyze the asymptotic costs of indexing, storage, and compute for the three dominant paradigms in nearest neighbor search algorithms: brute-force, partitioning-based, and graph-based. We find that these three families of algorithms make fundamentally different tradeoffs between the three costs, leading to each algorithm having its own advantages and disadvantages. Our work challenges prior notions of a single "best" nearest neighbor search algorithm, instead suggesting the optimum is setup-dependent.
Chat is not available.