Hashing is a popular solution to approximate nearest neighbor search, and appears in two variants: indexing data items in hash tables, or representing items by short binary codes and using these compact representations to approximate distances. We focus on the second approach, and more specifically on methods that learn codes from the data distribution.

We then present methods based on vector quantization, which are a natural generalization. In particular, we discuss exhaustive and non-exhaustive variants of product quantization including recent optimizations, as well as additive quantization. Finally, we explore the opposite direction, that of using nearest neighbor search to speed up vector quantization itself.

Yannis Avrithis, invited talk at Laboratory of Algebraic and Geometric Algorithms, University of Athens, 26 March 2015 [Slides]