Quantization-based fast inner product search

• US 10,255,323 B1
• Filed: 10/08/2015
• Issued: 04/09/2019
• Est. Priority Date: 08/31/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Guo, Ruiqi, Kumar, Sanjiv, Choromanski, Krzysztof Marcin, Simcha, David Morris
• Primary Examiner(s): Aspinwall, Evan
• Application Number:
  US14/878,357
• Time in Patent Office: 1,279 Days
• Field of Search: 707713
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

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.

Claims

1. A computer system comprising:

at least one processor; and

memory storing;

a database of search items, each of the search items being represented by a respective vector of d elements, and

instructions that, when executed by the at least one processor, cause the system to;

re-order the d vector elements of each search item using a random rotation,

project each re-ordered search item vector into K subspaces of i elements,

generate a codebook for each subspace, each entry in each codebook being a vector with i elements, the codebook being generated within constraints based on example queries,

assign 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

store the codebooks and the quantized search items in the memory.

2. The system of claim 1, wherein assigning each subspace of each search item an entry in the codebook includes generating an assignment vector with exactly one vector element being a 1 and remaining vector elements being 0, the 1 corresponding to an entry in the codebook.

3. The system of claim 1, wherein the memory further stores instructions that, when executed by the at least one processor, cause the system to:

re-order the elements of a query vector using the random rotation,

project the re-ordered elements of the query vector into the K subspaces;

for each search item;

calculate, for each subspace, an inner product between the query vector and the entry in the codebook assigned to the corresponding subspace of the search item, and

calculate a similarity score between the query and the search item by adding together the inner product for each subspace; and

provide at least the search item with the highest similarity score.

4. The system of claim 3, wherein the memory further stores instructions that, when executed by the at least one processor, cause the system to:

generate a table that stores, for each subspace, an inner product between the query vector and each entry in the codebook assigned to the corresponding sub space,

wherein calculating the inner product between the query and a search item includes using the codebook assignment of each subspace to fetch the inner product from the table.

5. The system of claim 1, wherein generating a codebook for each subspace includes:

clustering the search item subspaces corresponding to the codebook;

finding a cluster center for each cluster, the cluster center being the elements of the subspace of one of the search items; and

storing, for each cluster, a codebook entry, the codebook entry being the cluster center.

6. The system of claim 5, wherein the clustering uses Mahalanobis distance using a query covariance matrix generated from the example queries.

7. The system of claim 5, wherein the clustering occurs using a task-dependent objective function trained to predict clusters using the example queries.

8. The system of claim 7, wherein generating the codebook within constraints based on the example queries includes:

identifying a set of violated constraints for an example query;

adjusting the codebook for each subspace entries that includes a violated constraint; and

adjusting the cluster assignments.

9. The system of claim 8, wherein training occurs in iterations and each iteration identifies a maximum number of violated constraints.

10. A method comprising:

for each respective search item of search items in a database, each search item being represented as a vector of elements, re-ordering the elements of the vector using a random permutation,

generating a plurality of subspaces from the search items, a subspace being a block of elements from each search item that occur at the same vector positions;

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.

11. The method of claim 10, wherein assigning each subspace of each search item an entry in the codebook includes generating a one-hot assignment vector for the search item.

12. The method of claim 10, further comprising:

re-ordering the elements of a query vector using the random permutation,

projecting the re-ordered elements of the query vector into the plurality of subspaces;

for each search item;

calculating, for each subspace, an inner product between the query vector and the entry in the codebook assigned to the corresponding subspace of the search item, and

calculating a similarity score between the query and the search item by adding together the inner product for each subspace; and

providing at least the search item with the highest similarity score.

13. The method of claim 12, further comprising:

generating a table that stores, for each subspace, an inner product between the query vector and each entry in the codebook assigned to the corresponding sub space,

wherein calculating the inner product between the query and a search item includes using the codebook assignment of each subspace of the search item to fetch the inner product from the table.

14. The method of claim 10, wherein generating a codebook for a particular subspace includes:

clustering the search item subspaces that correspond to the particular subspace;

finding a cluster center for each cluster; and

storing, for each cluster, the cluster center as the codebook entry.

15. The method of claim 14, wherein the clustering uses Mahalanobis distance using a non-centered query covariance matrix generated from the example queries.

16. The method of claim 14, wherein the clustering occurs using optimization of a task-dependent objective function trained to use the example queries to provide soft constraints while minimizing expected quantization error.

17. The method of claim 16, wherein generating the codebook within constraints based on the example queries includes:

identifying a set of violated constraints for an example query;

adjusting the codebook for each subspace entries that includes a violated constraint; and

adjusting the cluster assignments.

18. A method comprising:

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 occurs at the same vector positions;

learning a codebook for each subspace by optimizing a task-dependent objective function that minimizes quantization error within soft constraints established by example queries, wherein the example queries are used to identify violated constraints and adjust the codebooks over iterative rounds, the learning resulting in assignment of each block of elements for each search item to an entry in the codebook, generating a quantized search item;

projecting a query vector into the plurality of subspaces;

using the query vector, the quantized search items and the codebooks to perform an inner product search for search items responsive to the query; and

providing at least the search item with the highest similarity score as responsive to the query.

19. The method of claim 18, further comprising:

generating a table that stores, for each subspace, an inner product between the query vector and each entry in the codebook assigned to the subspace,

wherein using the quantized search item and the codebooks to perform an inner product search includes using the codebook assignment of each subspace of the quantized search item to fetch the inner product from the table.

20. The method of claim 18, wherein at least three search items with the highest similarity scores are chosen search items and providing at least the search item with the highest similarity score includes:

determining, for each chosen search item, an actual dot product score for the chosen search item and the query vector;

ranking the chosen search items using the actual dot product score; and

providing at least the highest ranked chosen search item as responsive to the query.