Skip to yearly menu bar Skip to main content


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

[ ] [ Project Page ]
Fri 18 Jul 1:45 p.m. PDT — 3 p.m. PDT

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.