Multiscale quantization for fast similarity search

A computer-implemented method to perform machine learning, the method comprising:

• obtaining, by a computing system, a quantization model that includes a vector quantizer, a rotation matrix, a product quantizer that employs one or more product quantization codebooks, and a scalar quantizer that employs a scalar quantizer codebook;
• determining, by the computing system, a gradient of an objective function for one or more examples;
• and
• jointly training, by the computing system, the vector quantizer, the rotation matrix, the product quantizer, and the scalar quantizer based at least in part on the gradient of the objective function, wherein training the product quantizer comprises unit normalizing residual vectors associated with training data.

A computer system, comprising:

• one or more processors;
• and
• one or more non-transitory computer-readable media that, when executed by the one or more processors, cause the computer system to perform operations, the operations comprising:
• obtaining a dataset that includes a plurality of datapoints;
• performing reparameterization of each datapoint in the dataset into a unit-normalized direction component and a scale component, wherein the unit-normalized direction component has been normalized such that a variance of norms of the dataset is reduced;
• performing, by the computing system, product quantization of the unit-normalized direction components of the datapoints;
• performing, by the computing system, scalar quantization of the scale components of the datapoints;
• and
• performing an approximate nearest neighbor search for a query relative to the at least some of the plurality of reparametrized datapoints.