  Quantization based techniques are the current state-of-the-art for scaling
maximum inner product search to massive databases. Traditional approaches to
quantization aim to minimize the reconstruction error of the database points.
Based on the observation that for a given query, the database points that have
the largest inner products are more relevant, we develop a family of
anisotropic quantization loss functions. Under natural statistical assumptions,
we show that quantization with these loss functions leads to a new variant of
vector quantization that more greatly penalizes the parallel component of a
datapoint's residual relative to its orthogonal component. The proposed
approach achieves state-of-the-art results on the public benchmarks available
at \url{ann-benchmarks.com}.
