Automating Nearest Neighbor Search Configuration with Constrained Optimization
This addresses the obstacle to ANN adoption by automating parameter tuning, making it more accessible for real-world machine learning applications, though it is incremental as it builds on existing quantization-based methods.
The paper tackles the problem of manually tuning parameters for approximate nearest neighbor (ANN) search algorithms, which affects speed-recall tradeoffs, by proposing a constrained optimization-based approach that automatically generates tunings close to the Pareto frontier and achieves leading performance on standard benchmarks.
The approximate nearest neighbor (ANN) search problem is fundamental to efficiently serving many real-world machine learning applications. A number of techniques have been developed for ANN search that are efficient, accurate, and scalable. However, such techniques typically have a number of parameters that affect the speed-recall tradeoff, and exhibit poor performance when such parameters aren't properly set. Tuning these parameters has traditionally been a manual process, demanding in-depth knowledge of the underlying search algorithm. This is becoming an increasingly unrealistic demand as ANN search grows in popularity. To tackle this obstacle to ANN adoption, this work proposes a constrained optimization-based approach to tuning quantization-based ANN algorithms. Our technique takes just a desired search cost or recall as input, and then generates tunings that, empirically, are very close to the speed-recall Pareto frontier and give leading performance on standard benchmarks.