Google Inc.

David Morris Simcha

Sanjiv Kumar

Ruiqi Guo

Xiang Wu

Xinnan Yu

Ananda Theertha Suresh

Daniel Holtmann-Rice

Quan Geng

Felix Chern

Krzysztof Marcin Choromanski

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.

Local orthogonal decomposition for maximum inner product search

Implementations provide an efficient system for calculating inner products between high-dimensionality vectors. An example method includes clustering database items represented as vectors, selecting a cluster center for each cluster, and storing the cluster center as an entry in a first layer codebook. The method also includes, for each database item, calculating a residual based on the cluster center for the cluster the database item is assigned to and projecting the residual into subspaces. The method also includes determining, for each of the subspaces, an entry in a second layer codebook for the subspace, and storing the entry in the first layer codebook and the respective entry in the second layer codebook for each of the subspaces as a quantized vector for the database item. The entry can be used to categorize an item represented by a query vector or to provide database items responsive to a query vector.

Hierarchical quantization for fast inner product search

Implementations provide an improved system for efficiently calculating inner products between a query item and a database of items. An example method includes generating a plurality of subspaces from search items in a database, the search items being represented as vectors of elements, a subspace being a block of elements from each search item that occur at the same vector position, generating a codebook for each subspace within soft constraints that are based on example queries, assigning each subspace of each search item an entry in the codebook for the subspace, the assignments for all subspaces of a search item representing a quantized search item, and storing the codebooks and the quantized search items. Generating a codebook for a particular subspace can include clustering the search item subspaces that correspond to the particular subspace, finding a cluster center for each cluster, and storing the cluster center as the codebook entry.

Growing community of inventors

Jersey City, NJ, United States of America

David Morris Simcha