Tuning approximate nearest neighbor search engines for speed-recall tradeoffs via lagrange multiplier methods

Abstract

Example quantization-based approximate nearest neighbors (ANN) search methods and systems (e.g., search engines) are tuned to perform at the speed-recall pareto frontier. With a desired search cost or recall as input, embodiments employ Lagrangian-based methods to perform constrained optimization on theoretically-grounded search cost and recall models. The resulting tunings, when paired with the efficient quantization-based ANN implementation of the embodiments, exhibit excellent performance on standard benchmarks while requiring minimal tuning or configuration complexity.