Google Inc.

Xiang Wu

Sanjiv Kumar

Ruiqi Guo

David Morris Simcha

Xinnan Yu

Ananda Theertha Suresh

Daniel Holtmann-Rice

Quan Geng

Felix Chern

Dave Dopson

Generally, the present disclosure is directed to systems and methods of quantizing a database with respect to a novel loss or quantization error function which applies a weight to an error measurement of quantized elements respectively corresponding to the datapoints in the database. The weight is determined based on the magnitude of an inner product between the respective datapoints and a query compared therewith. In contrast to previous work, embodiments of the proposed loss function are responsive to the expected magnitude of an inner product between the respective datapoints and a query compared therewith and can prioritize error reduction for higher-ranked pairings of the query and the datapoints. Thus, the systems and methods of the present disclosure provide solutions to some of the problems with traditional quantization approaches, which regard all error as equally impactful.

Systems and methods for weighted quantization

The present disclosure provides systems and methods that include or otherwise leverage use of a multiscale quantization model that is configured to provide a quantized dataset. In particular, the multiscale quantization model can receive and perform vector quantization of a first dataset. The multiscale quantization model can generate a residual dataset based at least in part on a result of the vector quantization. The multiscale quantization model can apply a rotation matrix to the residual dataset to generate a rotated residual dataset that includes a plurality of rotated residuals. The multiscale quantization model can perform reparameterization of each rotated residual in the rotated residual dataset into a direction component and a scale component. The multiscale quantization model can perform product quantization of the direction components of the plurality of rotated residuals, and perform scalar quantization of the scale components of the plurality of rotated residuals.

Multiscale quantization for fast similarity search

A systems and method for providing various improvements in the computing time and accuracy for finding items using a hybrid vector space inner-product search are described. In one example implementation, a computer system comprising: at least one processor; and a data store of hybrid records, each hybrid record in the data store including a dense component and a sparse component memory storing instructions that, when executed by the at least one processor, cause the system to: receive a query request that includes a query vector; generate a dense query component and a sparse query component from the query vector; determine dense component similarity values between the dense query component and dense components of at least some of the hybrid records; determine sparse component similarity values using the sparse query component and sparse components of at least some of the hybrid records; select an initial set of hybrid records from the data store based on the dense component similarity values and the sparse component similarity values; and respond to the query request with at least some of the records from the initial set of hybrid records, is described.

Efficient inner product operations

Techniques of indexing a database and processing a query involve decomposing the residual term according to a projection matrix that is based on a given direction v. For example, for each database element of a partition, the residual for that database element is split into a component parallel to a given direction and a component perpendicular to that direction. The parallel component lies in a one-dimensional subspace spanned by the direction and may be efficiently quantized with a scalar quantization. The perpendicular component is quantized using multiscale quantization techniques. The quantized residual components and the center elements of each partition define the indexed database. Upon receipt of a query from a user, the inner products of q with the residual may be computed efficiently using the quantized residual components. From these inner products, the database elements that are most similar to the query are selected and returned to the user.

Growing community of inventors

Piscataway, NJ, United States of America

Xiang Wu